秀爾算法(Shor）以應(yīng)用數(shù)學(xué)家彼得·秀爾(Peter Williston Shor?)命名，是一個(gè)在1994年發(fā)現(xiàn)的，針對整數(shù)分解問題的量子算法 (在量子計(jì)算機(jī)上面運(yùn)作的算法 )。

在一個(gè)量子計(jì)算機(jī)上面，要分解整數(shù)N,秀爾算法的運(yùn)作需要多項(xiàng)式時(shí)間（時(shí)間是log N的某個(gè)多項(xiàng)式這么長,log N在這里的意義是輸入的檔案長度）。更精確的說，這個(gè)算法花費(fèi)O((log N)3)的時(shí)間，展示出質(zhì)因數(shù)分解問題可以使用量子計(jì)算機(jī)以多項(xiàng)式時(shí)間解出，因此在復(fù)雜度類BQP里面。這比起傳統(tǒng)已知最快的因數(shù)分解算法，普通數(shù)域篩選法，其花費(fèi)次指數(shù)時(shí)間 -- 大約O(e1.9 (log N)1/3 (log log N)2/3)，還要快了一個(gè)指數(shù)的差異。

秀爾加密算法非常重要，因?yàn)樗硎褂昧孔佑?jì)算機(jī)的話，可以用來破解已被廣泛使用的公開密鑰加密方法，即RSA加密算法。RSA算法的基礎(chǔ)在于假設(shè)了我們不能很有效率的分解一個(gè)已知的整數(shù)。就目前所知，這假設(shè)對傳統(tǒng)的（也就是非量子）電腦為真；沒有已知傳統(tǒng)的算法可以在多項(xiàng)式時(shí)間內(nèi)解決這個(gè)問題。然而，Shor算法展示了因子分解這問題在量子計(jì)算機(jī)上可以很有效率的解決，所以一個(gè)足夠大的量子計(jì)算機(jī)可以破解RSA。這對于鼓吹我們?nèi)ソ⒘孔佑?jì)算機(jī)和去研究新的量子計(jì)算機(jī)算法，是一個(gè)非常大的動(dòng)力。

我們要試著解決的問題是：給定一個(gè)合成數(shù)N,找到整數(shù)p在1和N之間且不包含1和N,并且N整除于p。

秀爾加密算法包含兩個(gè)部分：

一個(gè)以傳統(tǒng)的電腦運(yùn)作的簡化算法，將因數(shù)分解簡化成搜尋目的問題。

一個(gè)量子算法，解決搜尋目的問題。

傳統(tǒng)部分：

1、選擇任意數(shù)字a < N

2、計(jì)算gcd（a, N）。這里可以使用輾轉(zhuǎn)相除法來計(jì)算。

3、若gcd(a, N) ≠ 1，則我們有了一個(gè)N非平凡的因數(shù)，因此這部分結(jié)束了。

4、否則，利用下面的周期尋找副函式（Period-finding subroutine，下面會(huì)列出）來找出下面這個(gè)函數(shù)的周期r：f (x) = ?a^x mod ?N,換句話說，找出a在Zn里面的階r，或者最小的正整數(shù)r令f(x+r)=f(x)。

5、若r是奇數(shù)，回到第一步。

6、若a ^{r /2} ≡ -1 (mod N),回到第一步。

7、gcd(ar/2+1, N)與gcd(ar/2-1, N)分別是N非平凡的因數(shù)。分解完成。

量子部分：

這個(gè)算法使用的量子線路是為了在給定一個(gè)固定常數(shù)N以及一個(gè)任意常數(shù)a之下，找出f(x) = ax mod N所設(shè)定的。給定N,找出Q = 2q且合乎N^2 大于等于 Q 小于2N^2（這同時(shí)表示 ?Q/r > N）。輸入和輸出量子位元暫存器需要儲(chǔ)存從0到Q-1所有值的疊加態(tài)，因此分別需要q個(gè)量子位元。這里使用看起來比所需的數(shù)量還要更多一倍的量子位元，保證了即使周期r的大小逼近N/2，也至少有N個(gè)不同的x會(huì)產(chǎn)生相同的f(x)。

1、將暫存器初始化成
x從0到Q ? 1。所以這一個(gè)初始態(tài)是Q個(gè)狀態(tài)的疊加。

2、建立量子函式版本的f(x)，并且應(yīng)用于上面的疊加態(tài)，得到

這里仍舊是Q個(gè)狀態(tài)的疊加。

3、對輸入暫存器進(jìn)行量子傅立葉變換。這個(gè)變換（操作于二的冪次--Q = 2^q個(gè)疊加態(tài)上面） 使用一個(gè)Q^th 單位根例如將任意給定態(tài)|x的振幅平均分布在所有Q個(gè)|y態(tài)上。另一個(gè)方法是對于每個(gè)不同的x：

由此得到最終狀態(tài)：

這是一個(gè)遠(yuǎn)多過Q個(gè)狀態(tài)的疊加態(tài)，但是遠(yuǎn)低過Q²個(gè)。雖然在和中有Q²項(xiàng)，但只要x₀和x的值相同，態(tài)|y|f(Xo)就可被提出來。令為Q^th的一個(gè)單位根，r為f的周期，x₀為一個(gè)產(chǎn)生相同f(x)的x的集里面的最小元素（我們已經(jīng)有x₀ < r），以及b在0到（Q-Xo-1）/r之間使得Xo+rb<Q.那么W^ry則是復(fù)平面的一個(gè)單位向量（w是一個(gè)單位根，r和y是整數(shù)），而Q-1|y|f(Xo)在最終狀態(tài)下的系數(shù)則為：

這一求和的每一項(xiàng)代表一個(gè)獲得相同結(jié)果的不同路徑，而量子干涉發(fā)生。在單位向量W^ryb幾乎與復(fù)平面指向同一方向（要求W^yb指向正實(shí)數(shù)軸）時(shí)，干涉將是相長的。

4、進(jìn)行測量。我們由輸入寄存器取得結(jié)果y，由輸出寄存器取得?f(X0)。而既然f是周期，對某對y和f(Xo)進(jìn)行測量的概率則由

給出。分析顯示這個(gè)概率越高，單位向量W^xy就越接近正實(shí)數(shù)軸，或者yr/Q就越接近一個(gè)整數(shù)。除非r是2的乘方，否則它不會(huì)是Q的因子。

5、對y/Q進(jìn)行連分?jǐn)?shù)展開來計(jì)算其近似值，并生成滿足下列兩個(gè)條件的c/r′：

A: r′<N

B: |y/Q - c/r′| < 1/2Q

借著滿足這一些條件，r′有很高的概率會(huì)是我們要找的周期r。

6、檢查f(x) = f(x + r′)雙向等于 a^r mod{N}。如果成功了，我們就完成了。

7、否則，以接近y左右的數(shù)值作為r的候選，或者說多取幾個(gè)r′.如果任何候選成功了，我們就完成了。否則，還是需要回到第一步驟，重新全部操作一次。

秀爾算法包含兩個(gè)部分。算法的第一部分是將因數(shù)分解問題轉(zhuǎn)成尋找一個(gè)函式的周期，而且這部分可以用傳統(tǒng)方式實(shí)做。第二部分則是使用量子傅立葉變換來搜尋這個(gè)函式的周期，而且這一部分是量子加速這整個(gè)算法的理由。

小于N且互質(zhì)于N的整數(shù)組成一個(gè)有限大，且對乘法同余N的群。在步驟3之后，我們有一個(gè)屬于這個(gè)群的整數(shù)a。既然這個(gè)群是有限的，a必有一個(gè)有限大的階r,也就是最小的正整數(shù)令a^r 等于 1 mod N.,因此可知，N是a r ? 1的因數(shù)。先假設(shè)我們有能力獲得r，而且r是偶數(shù)。則r是令a ^r ≡ 1最小的正整數(shù)，所以（a ^{r / 2} ? 1）必定不能整除于N。若（a ^{r / 2} + 1）也不整除于N的話，則N必定與（a ^{r / 2} ? 1）或者（a ^{r / 2} + 1）有一個(gè)非顯然的公因數(shù)。

證明：為了簡化，我們分別用u和v表示（a r / 2 ? 1）和（a r / 2 + 1）。N | uv，故kN = uv（k是某個(gè)整數(shù)）。假設(shè)gcd(v, N) = 1：則必定存在某個(gè)整數(shù)m和n令mv + nN = 1 (這是最大公因數(shù)的一個(gè)性質(zhì))。兩邊同乘以u，我們得到mkN + nuN = u, so N | u。gcd(v, N) ≠ 1，故產(chǎn)生矛盾。用類似的方法，可以得知若（a r / 2 + 1）不能整除于N, gcd(u, N) ≠ 1。故得證u和v不同時(shí)與N互質(zhì)。這給予我們一個(gè)N的因數(shù)分解。若N是兩個(gè)質(zhì)數(shù)的乘積，則這是唯一可能的分解。

ice

收藏 海報(bào)分享