量子計算 [7].ext

2021-05-04 12:46 作者:nyasyamorina 0人讀過 | 我要投稿

在本篇里討論了Shor算法的原理,? 在這里著手實(shí)現(xiàn)Shor算法.?[arxiv.org/abs/quant-ph/0205095]

在下面將會大量用到QFT,? 為了文本的簡潔,? 記

$QFT%3A%5Cbigotimes%5Cnolimits_%7Bl%3Dn%7D%5E1%7Cj_l%5Crangle%5Crightarrow2%5E%7B-%5Cfrac%7Bn%7D%7B2%7D%7D%5Cbigotimes%5Cnolimits_%7Bl%3Dn%7D%5E1(%7C0%5Crangle%2Bexp(2%5E%7B1-l%7D%5Cpi%20i(%5Csum_%7Bk%3D1%7D%5En2%5E%7Bk-1%7Dj_k))%7C1%5Crangle)$

為 $QFT%3A%7Cj%5Crangle%5Crightarrow%7C%5Cphi(j)%5Crangle$ .? 注意這里QFT的定義為沒有SWAP門.

并且會用到大量量子加法,? 在給出一個已知的[或者說電子邏輯表示的]整數(shù)a,? 有

$%5CPhi_a%3A%7C%5Cphi(x)%5Crangle%5Crightarrow%7C%5Cphi(a%2Bx)%5Crangle$

以及它的逆操作 $%5CPhi_a%5E%7B-1%7D$ .

下面開始正式構(gòu)造Shor算法的量子電路.

Shor算法在第一版解釋為對模冪函數(shù)進(jìn)行周期分析,? 但在第二版開始解釋為對模乘函數(shù)進(jìn)行相位估計.? 兩種解釋只在"解釋"會有差異,? 計算結(jié)果是一樣的.? 因?yàn)闀簳r不存在很好的量子模冪位門,? 所以使用第二種解釋可以很大程度上化簡電路 [化簡版的相位估計].? 那么構(gòu)造一個模乘位門? $U_%7Ba%2CN%7D%3A%7Cx%5Crangle%5Crightarrow%7C(ax)%5C%25N%5Crangle$ ?即代表成功.

萬物起源于微積分加法,? 所以第一件事就是找到可行的模加位門

$%5CPhi_%7Ba%2C%5C%25N%7D%3A%7C%5Cphi(x)%5Crangle%5Crightarrow%7C%5Cphi((a%2Bx)%5C%25N)%5Crangle$

這并不是一件簡單的事情,? 因?yàn)槟６x為全體整數(shù)到 [0,N) 的映射,? 這明顯是不可逆的.? 為了保證模加位門的可逆性,? 規(guī)定條件? $a%2Cx%5Cin%5B0%2CN)$ ,? 這時候 (a+x)%N 化簡為?如果a+x<N, 則返回a+x;? 否則返回a+x-N.? 不難知道在給出a,N時,? 這是一個x從[0,N)到[0,N)的滿映射,? 也就說這是可逆的.

如此,? 可以先計算a+x-N,? 如果計算結(jié)果小于0,? 則加上N.? 因?yàn)橛嬎阃局锌赡軙霈F(xiàn)負(fù)數(shù),? 需要使用額外的量子位來儲存溢出[即電子計算機(jī)里整數(shù)的符號位].? 另外還需要一個量子位保存a+x-N小于0的結(jié)果再控制最后加上N的操作.? 對于額外引入的兩個量子位,? 儲存溢出的位還有使命仍未完成,? 而控制加N操作的位在控制完之后需要被還原為|0?.? 又因?yàn)榧臃ㄓ嬎闶窃谙辔簧系?? 為了提取溢出位的結(jié)果,? IQFT是必須的.? 綜上所述,? 模加位門的構(gòu)造為

紅色部分計算(a+x)%N,? 藍(lán)色部分是為了還原最頂上的量子位.? 實(shí)際上我們需要的 $%5CPhi_%7Ba%2C%5C%25N%7D$ 為紅色和藍(lán)色框,? 框外的QFT只是表示輸入和輸出的形式.? 下面給出模加位門的實(shí)現(xiàn)

模乘函數(shù) $(ax)%5C%25N$ ,? 可以分解為 $(a%5Ctimes(2%5E%7Bn-1%7Dx_n%2B%5Ccdots%2B2%5E0x_1))%5C%25N$ ,? 又因?yàn)?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=(x%2By)%5C%25N" alt="(x%2By)%5C%25N"> = $(x%5C%25N%2By%5C%25N)%5C%25N$ ,? 所以模乘函數(shù)可以寫為

$(ax)%5C%25N%3D(((2%5E0ax_1)%5C%25N%2B2%5E1ax_2)%5C%25N%5Ccdots%2B2%5E%7Bn-1%7Dax_n)%5C%25N$

當(dāng)某一步的 $x_l$ 為0時,? 這步模加可以忽略不記,? 所以可以簡單地使用 $%7Cx_l%5Crangle$ 控制模加位門 $%5CPhi_%7B2%5E%7Bl-1%7Da%2C%5C%25N%7D$ 達(dá)到 $%7Cb%5Crangle%5Crightarrow%7C(b%2B2%5E%7Bl-1%7Dax_l)%5C%25N%5Crangle$ ,? 如此得到模乘位門 $M_%7Ba%2CN%7D%3A%7Cx%5Crangle%7Cb%5Crangle%5Crightarrow%7Cx%5Crangle%7C(ax%2Bb)%5C%25N%5Crangle$

需要注意的是這里輸入的|b?是含有溢出量子位的.? 盡管溢出量子位在輸入和輸出都為|0?.

現(xiàn)在離成功已經(jīng)非常接近了,? 如果模乘位門里的第二個寄存器為|0?,? 則有 $%7Cx%5Crangle%7C0%5Crangle%5Crightarrow%7Cx%5Crangle%7C(ax)%5C%25N%5Crangle$ ,? 可以看到所需的答案儲存在第二個寄存器里,? 而相位評估需要的位門必須是輸出結(jié)果儲存在輸入寄存器里,? 通過SWAP門可以將兩個寄存器的信息交換.? 交換完后需要對第二個寄存器進(jìn)行還原,? 否則它將帶著錯誤的狀態(tài)[不是0]進(jìn)行下一次模乘.

因?yàn)槟３宋婚T的逆為 $M_%7Ba%2CN%7D%5E%7B-1%7D%3A%7Cx%5Crangle%7Cb%5Crangle%5Crightarrow%7Cx%5Crangle%7C(b-ax)%5C%25N%5Crangle$ ,??并且 $0%3Dx-a%5E%7B-1%7Dax$ ,? 所以還原第二個寄存器需要執(zhí)行以a的逆元為基礎(chǔ)的模乘位門的逆,? 即 $M_%7Ba%5E%7B-1%7D%2CN%7D%5E%7B-1%7D%3A%7C(ax)%5C%25N%5Crangle%7Cx%5Crangle%5Crightarrow%7C(ax)%5C%25N%5Crangle%7C0%5Crangle$

于是相位評估里需要的模乘位門 $U_%7Ba%2CN%7D%3A%7Cx%5Crangle%5Crightarrow%7C(ax)%5C%25N%5Crangle$ 為

使用疊加特征態(tài) $%7C1%5Crangle$ 對 $U_%7Ba%2CN%7D$ 進(jìn)行相位估計,? 就可以測得 $j_s%2F2%5En%5Capprox%20s%2Fr%2C%20s%5Cin%5B0%2Cr)%5Ccap%5Cmathbb%20Z$ ,? 求得r后就可以分解整數(shù)N了.

在相位估計里需要控制位門 $U%5E%7B2%5E%7Bl%7D%7D$ ,? 在無法進(jìn)行化簡的情況下,? 這意味著需要運(yùn)行 $2%5El$ 次位門U,? 在精度要求比較高的情況下無疑會花費(fèi)巨量的時間.? 但對于多重模乘位門,? 這是可以化簡的:

$U_%7Ba%2CN%7D%5E%7B2%5El%7D%7Cx%5Crangle%3D%7C(%5Cunderbrace%7Ba%5Ccdots%20a%7D_%7B2%5El%7D%5Ctimes%20x%20)%5C%25N%5Crangle%3D%7C(a%5E%7B2%5El%7Dx)%5C%25N%5Crangle%3DU_%7Ba%5E%7B2%5El%7D%2CN%7D%7Cx%5Crangle$

在模乘位門里用到了a的逆元,? 但直接計算1/a必定是小數(shù),? 而上述算法只能在整數(shù)下計算.

假設(shè)有一個整數(shù)b,? 滿足 $ab%5Cequiv1(%5C%25N)$ ,? 則稱b為a在模N下的模逆元.? 整數(shù)a有模逆元的充分必要條件為gcd(a,N)=1.

給出任意整數(shù)α和β,? 使用擴(kuò)展歐幾里得算法可以在多項(xiàng)式時間里找到x, y和gcd(α,β),? 并且滿足 $%5Calpha%20x%2B%5Cbeta%20y%3Dgcd(%5Calpha%2C%5Cbeta)$ ,? 也就是 $%5Calpha%20x%5Cequiv%20gcd(%5Calpha%2C%5Cbeta)(%5C%25%5Cbeta)$ ,? 利用這個性質(zhì)可以快速求得a在模N下的模逆元.? 下面為求模逆元的算法 [實(shí)質(zhì)上就是砍掉一部分的擴(kuò)展歐幾里得算法]

在Shor算法里有個挺嚴(yán)重的問題就是測量結(jié)果約為s/r,? 在本篇里說過可以使用連分?jǐn)?shù)展開去估計r的值.? 但找了一圈都沒有發(fā)現(xiàn)有什么比較直接的方法求得r,? 下面是一種自制的暴力歷遍的方法,? 如果有什么更有效的方法歡迎在評論區(qū)補(bǔ)充.

首先需要分式和連分式互相轉(zhuǎn)化的方法,? 下面是一種可能的實(shí)現(xiàn)方法[只保證可以運(yùn)行, 不保證效率.]

測量之后已知的數(shù)據(jù)有:? 測量結(jié)果j,??測量精度n,? 需要分解的整數(shù)N;? 已知的條件為?r<N [嘗試了幾十種不同的a和N, 發(fā)現(xiàn)都有r<N/2, 是有什么我不知道的定理, 或者只是巧合?].? 對 $j%2F2%5En$ 進(jìn)行連分式展開,? 并逐段截斷,? 截斷得到的分式的分母即有可能為r.? 另外,? 由于s/r有可能不是最簡分式,??截斷連分式得到的分母為r的概率約為φ(r)/r,? φ(·)為歐拉函數(shù),? 即與r互質(zhì)并且小于r的數(shù)字?jǐn)?shù)量.? It's that good enough?? 確實(shí),? 對截斷后的分母再乘上一些整數(shù)可以繼續(xù)擴(kuò)大r的候選列表,? 但因?yàn)椴糠址帜副容^小,? 把它的所有可能的整數(shù)倍[記得r<N]都放入候選列表之后,? 雖然增加了單次運(yùn)行量子程序得到r的概率,? 但是花費(fèi)在電子電路上的時間很有可能遠(yuǎn)遠(yuǎn)大于再次運(yùn)行量子程序的時間,? 并且很有可能引發(fā)新的問題[見下],? 下面就是這一段昏睡咒語的代碼實(shí)現(xiàn)

需要注意的是,? 這里輸出的列表的r的候選列表,? 其中絕大部分都不是a(%N)的階,? 也就是說可能造成 $gcd(a%5E%7Br_%7B'%7D%2F2%7D-1%2CN)%3D1$ ,? 其中 $r_%7B'%7D$ 是上面函數(shù)輸出的候選列表.? 另外,? 因?yàn)楹蜻x列表里可能含有階r,? 如果把候選列表里的數(shù)字乘上整數(shù)再放入候選列表[為了應(yīng)對s/r不是最簡分式的情況],? 就會出現(xiàn) $r_%7B'%7D%3D2r$ ,? 這時候計算 $gcd(a%5E%7Br_%7B'%7D%2F2%7D-1%2CN)%3DN$ ,? 因?yàn)?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=a%5Er%5Cequiv1(%5C%25N)" alt="a%5Er%5Cequiv1(%5C%25N)">.

結(jié)合上面所有知識,? 最后可以構(gòu)造出Shor算法.? 其實(shí)差了一步對 $N%3Dp%5Eq$ 特攻的傳統(tǒng)算法,? 就算不對這種情況過濾,? 選取隨機(jī)數(shù)時也有至少 $1%2F%5Csqrt%20N$ 的概率求得p的整數(shù)倍從而在計算gcd(a,N)時得到p.? 如果有大佬知道p^q如何用傳統(tǒng)算法求解的話,? 歡迎在評論區(qū)補(bǔ)充.

整個程序已放到github上:

github.com/nyasyamorina/nyasQuantumCalculate/blob/main/examples/8-ShorAlgorithm.py

$%5Cmathfrak%7BEnd.%7D%20$

上面給出的代碼是對篇幅優(yōu)化的代碼,? 僅供參考.

關(guān)于后續(xù)計劃:? 原本我學(xué)習(xí)量子計算是以Shor算法為目標(biāo)的.? 在達(dá)成目標(biāo)的現(xiàn)在,? 請?jiān)试S我摸億會兒魚.? 當(dāng)然量子計算這個專欄集是還沒有完結(jié)的,? 等再屯一波新知識就開始再更新了.

日常推推瑟圖群: [274767696]

封面pid:?82387230

標(biāo)簽：

最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

量子計算 [7].ext

量子計算 [7].ext的評論 (共條)

你可能也喜歡這些文章

最新發(fā)布的文章

最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

量子計算 [7].ext

本文作者的其他文章

量子計算 [7].ext的評論 (共 條)

你可能也喜歡這些文章

最新發(fā)布的文章

量子計算 [7].ext的評論 (共條)