量子計算 [7] -- Shor算法

2021-05-01 20:24 作者:nyasyamorina 0人讀過 | 我要投稿

本文是對Shor算法的原理進行討論,? 至于算法實現(xiàn)應(yīng)該是放在附章里的.

Shor算法是一個在多項式時間內(nèi)進行整數(shù)分解的算法.? 整數(shù)分解就是給出一個整數(shù)N,? 找到兩個整數(shù)相乘后等于N.? 在電子計算機里,? 目前最好的方法依然需要指數(shù)時間對整數(shù)進行分解.? 至于可以快速進行整數(shù)分解對密碼學有什么影響這里也不說了,? 看膩了好吧.

下面將會大量用到模運算和最大公因數(shù)兩個概念,? 簡單復習一下.

在小學學習的除法定義為 a÷b=c...d,? 其中a,b,c,d都為整數(shù),? 并且d<b.? 則模運算定義為 a%b=d[其實應(yīng)該寫為 `a mod b = d`,? 這里用python的模運算符號`%`代替`mod`了].

a與b的最大公因數(shù)(greatest common divisor)定義為同時整除a和b的最大數(shù)字,? 寫為gcd(a,b).? gcd可以使用歐幾里得算法快速求得.? 這里也不詳細敘述......ffffine,? 下面貼出gcd的python代碼

量子計算機并不能直接地對整數(shù)進行分解,? Shor算法是把整數(shù)分解轉(zhuǎn)化為求階問題.

但在使用量子算法求階之前,? 符合某些條件的數(shù)字可以由傳統(tǒng)算法很快地分解.??比如說如果數(shù)字的二進制表示的最小位為0,? 那么這個數(shù)字是偶數(shù),? 2必定是它的因數(shù).? 還有對于整數(shù) $N%3Dp%5Eq$ ; $p%5Cgeq1%2Cq%5Cgeq2$ ,? 使用傳統(tǒng)算法可以以多項式時間求出因數(shù)p? [具體實現(xiàn)我也不太清楚, 歡迎大佬在評論區(qū)補充].? 經(jīng)過篩選之后,? 剩下的就是Shor算法的討論范圍了.

記需要分解的整數(shù)為N,? 給出一個整數(shù) $a%5Cin%5B2%2CN)$ ,? 并且滿足 $gcd(a%2CN)%3D1$ ,? 那么 $a(%5C%25N)$ 的階r定義為函數(shù) $f(x)%3Da%5Ex%5C%25N$ 的最小正周期,? 其中 $x%5Cin%5Cmathbb%20Z$ .

因為r為f(x)的周期,? 則有 $a%5Er%5Cequiv%20a%5E0%5Cequiv1(%5C%25N)$ ??? $(a%5Er-1)%5C%25N%3D0$ ,? 也就是說 $a%5Er-1$ 可以被N整除.

如果r為偶數(shù),? 有 $a%5Er-1%3D(a%5E%7Br%2F2%7D-1)(a%5E%7Br%2F2%7D%2B1)$ ,? 那么 $gcd(a%5E%7Br%2F2%7D-1%2CN)$ 和 $gcd(a%5E%7Br%2F2%7D%2B1%2CN)$ 都為N的因數(shù).? 其中 $gcd(a%5E%7Br%2F2%7D-1%2CN)$ ? $%5Cneq%20N$ ,? 如果 $gcd(a%5E%7Br%2F2%7D-1%2CN)$ ? $%3DN$ ,? 則有 $(a%5E%7Br%2F2%7D-1)%5C%25N%3D0$ ?? $a%5E%7Br%2F2%7D%5C%25N%3D1$ ,? 這與階r的定義沖突:? r為f(x)的最小正周期.? 如果 $gcd(a%5E%7Br%2F2%7D-1%2CN)$ ? $%3D1$ ,??因為 $(a%5E%7Br%2F2%7D-1)(a%5E%7Br%2F2%7D%2B1)%5Cequiv0(%5C%25N)$ ,? 則有 $a%5E%7Br%2F2%7D%2B1%5Cequiv0(%5C%25N)$ ?? $a%5E%7Br%2F2%7D%5Cequiv-1%5Cequiv%20N-1(%5C%25N)$ .

根據(jù)上面的推論,? Shor算法過程為:

隨機在 $%5B2%2CN-1)$ 中選擇一個數(shù)字a
計算gcd(a,N),? 如果不等于1, 則得到N的一個因數(shù): $gcd(a%2CN)$
使用量子計算機得出a(%N)的階r
如果r為奇數(shù),? 或 $a%5E%7Br%2F2%7D%5C%25N%3DN-1$ ,? 則返回第1步
得到 $N$ 的兩個因數(shù):? $gcd(a%5E%7Br%2F2%7D-1%2CN)$ ?和 $gcd(a%5E%7Br%2F2%7D%2B1%2CN)$

把 $N$ 寫為質(zhì)數(shù)的乘積,? 即 $N%3D%5Cprod%5Cnolimits_%7Bi%3D1%7D%5Emp_i%5E%7Bq_i%7D$ ,? 其中 $p_i$ 為質(zhì)數(shù),? $q_i%5Cgeq1$ .? 記r_i為 $a(%5C%25p_i%5E%7Bq_i%7D)$ 的階,? 那么r為r_i的最小公倍數(shù)(least common multiple).? 如果r_i全部都為奇數(shù),? 那么r也為奇數(shù),? 即r/2不存在[應(yīng)該說不是整數(shù)];? 如果r_i全部都為偶數(shù),? 因為 $a%5E%7Br_i%2F2%7D%5Cequiv-1(%5C%25p_i%5E%7Bq_i%7D)$ ,? 有 $a%5E%7Br%2F2%7D%5Cequiv-1(%5C%25N)$ .? r_i同時全為奇數(shù)或偶數(shù)的概率為 $%5Cfrac%7B1%7D%7B2%5E%7Bm-1%7D%7D$ ,? 也就是算法的成功率為 $1-%5Cfrac%7B1%7D%7B2%5E%7Bm-1%7D%7D$ .? 當m=1時,? 算法成功率為0,? 也就是說最開始使用傳統(tǒng)算法把 $N%3Dp%5Eq$ 篩選掉是必須的.

下面來討論Shor算法里的第三步 -- 使用量子計算機得出a(%N)的階r

考慮模乘函數(shù) $(ay)%5C%25N$ ,? 并有相應(yīng)的位門 $U_%7Ba%2CN%7D%3A%7Cy%5Crangle%5Crightarrow%7C(ay)%5C%25N%5Crangle$ ,? 為了滿足可逆條件,? 規(guī)定 $y%3CN$ .? 對于 $y%5Cgeq%20N$ ,? 有 $U_%7Ba%2CN%7D%3A%7Cy%5Crangle%5Crightarrow%7Cy%5Crangle$ . [一般來說不考慮y>=N的情況]

觀察下面電路,? 并分析態(tài) $%7Cy%5Crangle$ 的變化,? $y%5Cleq%20N$ :

$%5Cbegin%7Barray%7D%7B9%7D%7Cy%5Crangle%5Crightarrow%20U%5E%7Bx_12%5E0%7D_%7Ba%2CN%7D%7Cy%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%3D%7C(a%5E%7Bx_12%5E0%7Dy)%5C%25N%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5Crightarrow%20U%5E%7Bx_22%5E1%7D_%7Ba%2CN%7D%7C(a%5E%7Bx_12%5E0%7Dy)%5C%25N%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%3D%7C(a%5E%7Bx_22%5E1%7Da%5E%7Bx_12%5E0%7Dy)%5C%25N%5Crangle%20%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5Cvdots%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5Crightarrow%20U%5E%7Bx_n2%5E%7Bn-1%7D%7D_%7Ba%2CN%7D%7C(%5Ccdots%20a%5E%7Bx_22%5E1%7Da%5E%7Bx_12%5E0%7Dy)%5C%25N%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%3D%7C(a%5E%7Bx_n2%5E%7Bn-1%7D%7D%5Ccdots%20a%5E%7Bx_22%5E1%7Da%5E%7Bx_12%5E0%7Dy)%5C%25N%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%3D%7C(a%5E%7Bx_n2%5E%7Bn-1%7D%2B%5Ccdots%2Bx_22%5E1%2Bx_12%5E0%7Dy)%5C%25N%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%3D%7C(a%5Exy)%5C%25N%5Crangle%5Cend%7Barray%7D$

可以看到這個電路等價于模冪位門? $%7Cx%5Crangle%7Cy%5Crangle%5Crightarrow%7Cx%5Crangle%7C(a%5Exy)%5C%25N%5Crangle$ .

構(gòu)造一個態(tài)? $%7Cu_s%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt%20r%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D%7Ca%5Ek%5C%25N%5Crangle$ ,? $s%5Cin%5B0%2Cr)%5Ccap%5Cmathbb%20Z$ ,? 其中r為 $a(%5C%25N)$ 的階,? 容易證明這個態(tài)是位門 $U_%7Ba%2CN%7D$ 的特征態(tài):? $U_%7Ba%2CN%7D%7Cu_s%5Crangle$ = $%5Cfrac%7B1%7D%7B%5Csqrt%20r%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D%7C(a%5Ccdot%20a%5Ek)%5C%25N%5Crangle$ = $%5Cfrac%7B1%7D%7B%5Csqrt%20r%7D%5Csum%5Cnolimits_%7Bk%3D1%7D%5E%7Br%7De%5E%7B-2%5Cpi%20i(k-1)sr%5E%7B-1%7D%7D%7Ca%5Ek%5C%25N%5Crangle$ = $%5Cfrac%7B1%7D%7B%5Csqrt%20r%7De%5E%7B2%5Cpi%20isr%5E%7B-1%7D%7D%5Csum%5Cnolimits_%7Bk%3D1%7D%5E%7Br%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D%7Ca%5Ek%5C%25N%5Crangle$ ,? 當k=r時,? 因為 $a%5Er%5Cequiv%20a%5E0(%5C%25N)$ ,? 則有 $e%5E%7B-2%5Cpi%20irsr%5E%7B-1%7D%7D%7Ca%5Er%5C%25N%5Crangle$ = $e%5E%7B-2%5Cpi%20i0sr%5E%7B-1%7D%7D%7Ca%5E0%5C%25N%5Crangle$ ,? 即 $U_%7Ba%2CN%7D%7Cu_s%5Crangle$ = $%5Cfrac%7B1%7D%7B%5Csqrt%20r%7De%5E%7B2%5Cpi%20isr%5E%7B-1%7D%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D%7Ca%5Ek%5C%25N%5Crangle$ = $e%5E%7B2%5Cpi%20isr%5E%7B-1%7D%7D%7Cu_s%5Crangle$ .? 從而得到特征值為 $e%5E%7B2%5Cpi%20isr%5E%7B-1%7D%7D$ .? 因為不知道r,? 所以任何獨立的特征態(tài)都是無法制備的.

把全部特征態(tài)疊加起來,? 得到 $%5Cfrac%7B1%7D%7B%5Csqrt%20r%7D%5Csum%5Cnolimits_%7Bs%3D0%7D%5E%7Br-1%7D%7Cu_s%5Crangle$ = $%5Cfrac%7B1%7D%7Br%7D%5Csum%5Cnolimits_%7Bs%3D0%7D%5E%7Br-1%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D%7Ca%5Ek%5C%25N%5Crangle$ = $%5Cfrac%7B1%7D%7Br%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7D%7Ca%5Ek%5C%25N%5Crangle%5Csum%5Cnolimits_%7Bs%3D0%7D%5E%7Br-1%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D$ 后面的累加由等比數(shù)列和求出,? 得 $%5Cfrac%7B1%7D%7Br%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7D%7Ca%5Ek%5C%25N%5Crangle%5Cfrac%7B1-e%5E%7B-2%5Cpi%20ik%7D%7D%7B1-e%5E%7B-2%5Cpi%20ikr%5E%7B-1%7D%7D%7D$ .? 在k=0時,? 分式未定義,? 對其取極限可以得到分式的值為 $r$ ?[不取極限, 直接計算累加式也可以得到相同的答案];? 而k≠0時,? 分子為0,? 由此化簡疊加態(tài)為 $%5Cfrac%7B1%7D%7Br%7D%7Ca%5Er%5C%25N%5Crangle%20r$ = $%7C1%5Crangle$ .

由上可得,? 以 $%7C1%5Crangle$ 為疊加特征態(tài),? 對位門 $U_%7Ba%2CN%7D%3A%7Cy%5Crangle%5Crightarrow%7C(ay)%5C%25N%5Crangle$ 進行相位估計可以測得s/r,? 其中 $s%5Cin%5B0%2Cr)%5Ccap%5Cmathbb%20Z$ .? 這Shor算法里的量子電路為

其中Modular Power為模冪位門: $%7Cx%5Crangle%7Cy%5Crangle%5Crightarrow%7Cx%5Crangle%7C(a%5Exy)%5C%25N%5Crangle$ ,? 并且 $m%3D%5Clceil%5Clog_2N%5Crceil$ ,? ??為向上取整.

因為測量量子位的結(jié)果為整數(shù),? 并且相位估計算法也有可能不會給出最佳近似值,? 所以測量結(jié)果與實際值之間會存在一定誤差.? 設(shè)測量結(jié)果為 $j_s$ ,? 那么有 $j_s%2F2%5En%5Capprox%20s%2Fr$ ,? 對 $j_s%2F2%5En$ 展開為連分數(shù),? 則在展開式的某一部分截斷可能會得到準確的s/r.? 并且注意到gcd(s,r)有可能不為1,? 也就是說分式s/r有可能不為最簡分式.? 為了提高算法成功率,? 可以對 $j_s-1$ 和 $j_s%2B1$ 也進行連分數(shù)展開.? 得到r后執(zhí)行Shor算法下面幾步即可以得到N的分解結(jié)果.

定理:? 如果滿足 $%7Cj_s%2F2%5En-s%2Fr%7C%5Cleq1%2F(2r%5E2)$ ,? 那么s/r是 $j_s%2F2%5En$ 連分數(shù)的一個漸進值.? 即 $2%5En%5Cgeq2r%5E2$ ,? 因為r<N,? 所以可以取 $2%5En%3D2N%5E2$ ,? 得到 $n%3D1%2B2%5Clog_2N%5Capprox1%2B2m$ .

是Shor算法的量子求階電路里,? 模冪位門的實現(xiàn)方法各種各樣,? 有時間復雜度低的方法,? 但使用了很多量子位;? 有使用少量量子位的,? 但時間復雜度很高.

附章將介紹一種只使用極少量子位的Shor算法實現(xiàn).? 因為在電子計算機上模擬量子計算所需的內(nèi)存是隨著量子位數(shù)量增長而指數(shù)增長的.? 使用盡可能少的量子位可以確保電子計算機也可以進行模擬.

在第一版Shor算法里, 模冪位門定義為 |x?|y??-> |x?|(y+a^x)%N?,? 則導致下面的量子位應(yīng)該初始化為|0?而不是|1?.? 這是因為第一版Shor算法并不是使用相位估計方法求階,? 而是直接對模冪函數(shù)進行周期分析.? 雖然兩個版本之間存在差異,? 但絕大部分都是一致的,? 并且都是求得s/r.

封面pid:?66444938

"""你已經(jīng)插入152張圖片了, 目前最多支持插入100張哦~""".? ?口區(qū)

標簽：

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

量子計算 [7] -- Shor算法

量子計算 [7] -- Shor算法的評論 (共條)

你可能也喜歡這些文章

最新發(fā)布的文章

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

量子計算 [7] -- Shor算法

本文作者的其他文章

量子計算 [7] -- Shor算法的評論 (共 條)

你可能也喜歡這些文章

最新發(fā)布的文章

量子計算 [7] -- Shor算法的評論 (共條)