秀爾演算法

维基百科,自由的百科全书
跳转至: 导航搜索

秀爾演算法Shor算法),以數學家彼得·秀爾命名,是一個在1994年發現的,針對整數分解這題目的的量子演算法(在量子計算機上面運作的演算法)。比較不正式的說,它解決題目如下:給定一個整數N,找出他的質因數

在一個量子計算機上面,要分解整數N,秀爾演算法的運作需要多項式時間(時間是log N的某個多項式這麼長,log N在這裡的意義是輸入的檔案長度)。更精確的說,這個演算法花費O((log N)3)的時間,展示出質因數分解問題可以使用量子計算機以多項式時間解出,因此在複雜度類BQP裡面。這比起傳統已知最快的因數分解演算法,普通數域篩選法,其花費次指數時間 -- 大約O(e1.9 (log N)1/3 (log log N)2/3),還要快了一個指數的差異。

秀爾演算法非常重要,因為它代表使用量子計算機的話,我們可以用來破解已被廣泛使用的公開密鑰加密方法,也就是RSA加密演算法。RSA演算法的基礎在於假設了我們不能很有效率的分解一個已知的整數。就目前所知,這假設對傳統的(也就是非量子)電腦為真;沒有已知傳統的演算法可以在多項式時間內解決這個問題。然而,秀爾演算法展示了因數分解這問題在量子計算機上可以很有效率的解決,所以一個足夠大的量子計算機可以破解RSA。這對於鼓吹我們去建立量子計算機和去研究新的量子計算機演算法,是一個非常大的動力。

在2001年,IBM的一個小組展示了秀爾演算法的實做,使用NMR實做的量子計算機,以及7個量子位元,將15分解成3×5。[1]然而,對IBM的實驗的是否是量子計算的真實展示,則有一些疑慮出現,因為沒有纏結現象被發現。[2]在IBM的實做之後,有其他的團隊以光學量子位元實做秀爾演算法,並強調其纏結現象可被觀察到。[3][4]

程序[编辑]

我們要試著解決的問題是:給定一個合成數N,找到整數p1N之間且不包含1N,並且N整除於p

秀爾演算法包含兩個部份:

  1. 一個以傳統的電腦運作的簡化演算法,將因數分解簡化成搜尋的問題。
  2. 一個量子演算法,解決搜尋目的問題。

傳統部份[编辑]

  1. 選擇任意數字a < N
  2. 計算gcda, N)。這裡可以使用輾轉相除法來計算。
  3. 若gcd(a, N) ≠ 1,則我們有了一個N非平凡的因數,因此這部份結束了。
  4. 否則,利用下面的週期尋找副函式(Period-finding subroutine,下面會列出)來找出下面這個函數的週期r
    f(x) = a^x\ \mbox{mod}\ N,
    換句話說,找出a\mathbb{Z}_N裡面的r,或者最小的正整數rf(x+r) = f(x)
  5. r是奇數,回到第一步。
  6. a r /2 ≡ -1 (mod N),回到第一步。
  7. gcd(ar/2 ± 1, N)是N非平凡的一個因數。分解完成。

量子部份:週期尋找副函式(Period-finding subroutine)[编辑]

這個演算法使用的量子線路是為了在給定一個固定常數N以及一個任意常數a之下,找出f(x) = ax mod N所設定的。給定N,找出Q = 2q且合乎N^2 \le Q < 2N^2(這同時表示Q/r > N)。輸入和輸出量子位元暫存器需要儲存從0到Q-1所有值的疊加態,因此分別需要q個量子位元。這裡使用看起來比所需的數量還要更多一倍的量子位元,保證了即使週期r的大小逼近N/2,也至少有N個不同的x會產生相同的f(x)。

程序如下:

  1. 將暫存器初始化成
    Q^{-1/2} \sum_{x=0}^{Q-1} \left|x\right\rangle \left|0\right\rangle
    x從0到Q − 1。所以這一個初始態是Q個狀態的疊加。
  2. 建立量子函式版本的f(x),並且應用於上面的疊加態,得到
    Q^{-1/2} \sum_x \left|x\right\rangle \left|f(x)\right\rangle.
    這裡仍舊是Q個狀態的疊加。
  3. 對輸入暫存器進行量子傅立葉變換。這個變換(操作於二的冪次--Q = 2q個疊加態上面) 使用一個Qth 單位根例如\omega = e^{2 \pi i /Q}將任意給定態\left|x\right\rangle的振幅平均分佈在所有Q\left|y\right\rangle態上。另一個方法是對於每個不同的x
    U_{QFT} \left|x\right\rangle
= Q^{-1/2} \sum_y \omega^{x y} \left|y\right\rangle
    由此得到最終狀態:
     Q^{-1} \sum_x \sum_y \omega^{x y} \left|y\right\rangle \left|f(x)\right\rangle.
    這是一個遠多過Q個狀態的疊加態,但是遠低過Q2個。雖然在和中有Q2項,但只要x0x的值相同,態\left|y\right\rangle \left|f(x_0)\right\rangle就可被提出來。令
    \omega = e^{2 \pi i /Q}Qth的一個單位根,
    rf的週期,
    x0為一個產生相同f(x)的x的集裡面的最小元素(我們已經有x0 < r),以及
    b在0到\lfloor(Q-x_0-1)/r\rfloor之間使得x_0 + rb < Q。那麼\omega^{ry}則是復平面的一個單位向量(\omega是一個單位根,ry是整數),而Q^{-1}\left|y\right\rangle \left|f(x_0)\right\rangle在最終狀態下的係數則為
     \sum_{x:\, f(x)=f(x_0)} \omega^{x y} = \sum_{b} \omega^{(x_0 + r b) y} = \omega^{x_0y} \sum_{b} \omega^{r b y}。這一求和的每一項代表一個獲得相同結果的不同路徑,而量子干涉發生。在單位向量\omega^{ryb}幾乎與復平面指向同一方向(要求\omega^{ry}指向正實數軸)時,干涉將是相長的。
  4. 進行測量。我們由輸入寄存器取得結果y,由輸出寄存器取得f(x_0)。而既然f是週期,對某對yf(x_0)進行測量的概率則由
     \left| Q^{-1} \sum_{x:\, f(x)=f(x_0)} \omega^{x y} \right|^2
= Q^{-2} \left| \sum_{b} \omega^{(x_0 + r b) y} \right|^2
    給出。分析顯示這個概率越高,單位向量\omega^{ry}就越接近正實數軸,或者yr/Q就越接近一個整數。除非r是2的乘方,否則它不會是Q的因子。
  5. y/Q進行連分數展開來計算其近似值,並生成滿足下列兩個條件的c/r′:
    A: r′<N
    B: |y/Q - c/r′| < 1/2Q
    藉著滿足這一些條件,r′有很高的機率會是我們要找的週期r
  6. 檢查f(x) = f(x + r′) \Leftrightarrow a^r \equiv 1 \pmod{N}。如果成功了,我們就完成了。
  7. 否則,以接近y左右的數值作為r的候選,或者說多取幾個r′.如果任何候選成功了,我們就完成了。
  8. 否則,回到第一步驟(也就是全部重新作一次)。

演算法的解釋[编辑]

此演算法包含兩個部份。演算法的第一部份是將因數分解問題轉成尋找一個函式的週期,而且這部份可以用傳統方式實做。第二部份則是使用量子傅立葉變換來搜尋這個函式的週期,而且這一部份是量子加速這整個演算法的理由。

I.從週期得到因數[编辑]

小於N互質N的整數組成一個有限大,且對乘法同餘N。在步驟3之後,我們有一個屬於這個群的整數a。既然這個群是有限的,a必有一個有限大的目r,也就是最小的正整數令

a^r \equiv 1\ \mbox{mod}\ N.\,

因此可知,Na r − 1的因數。先假設我們有能力獲得r,而且r是偶數。則

a^r - 1 = (a^{r/2} - 1) (a^{r/2} + 1) \equiv 0\ \mbox{mod}\ N
\Rightarrow N\ | (a^{r/2} - 1) (a^{r/2} + 1).\,

r是令a r ≡ 1最小的正整數,所以(a r / 2 − 1)必定不能整除於N。若(a r / 2 + 1)也不整除於N的話,則N必定與(a r / 2 − 1)或者(a r / 2 + 1)有一個非顯然的公因數。

證明:為了簡化,我們分別用uv表示(a r / 2 − 1)和(a r / 2 + 1)。N | uv,故kN = uv(k是某個整數)。假設gcd(v, N) = 1:則必定存在某個整數mnmv + nN = 1 (這是最大公因數的一個性質)。兩邊同乘以u,我們得到mkN + nuN = u, so N | u。gcd(v, N) ≠ 1,故產生矛盾。用類似的方法,可以得知若(a r / 2 + 1)不能整除於N, gcd(u, N) ≠ 1。故得證u和v不同時與N互質。

這給予我們一個N的因數分解。若N是兩個質數的乘積,則這是唯一可能的分解。

II.找尋週期[编辑]

秀爾的週期尋找演算法非常倚賴量子計算機同時計算許多狀態的能力。物理學家稱呼這個特性為這一些狀態的"疊加"。在計算函數f的週期時,我們會同時估計這個函數的所有點。

不過,量子物理不允許我們直接取得這一些資訊。測量會令觀測結果塌陷到其中一個可能的結果,並摧毀其他可能性的存在。但是根據不可克隆原理,我們可以先測量f(x)而非測量x,再製造幾個結果態的拷貝(將會是多個有著同樣的f(x)的態的疊加)。對這些態上的x的測量將會給出能給出相同f(x)的不同的x,由此推導出週期來。因為我們不能複製完全相同的量子狀態,這個方法行不通。因此在這裡我們需要小心的將疊加態轉變成我們有辦法以很高的正確機率回答答案的狀態。在這裡我們使用量子傅立葉變換來達成。

因此秀爾在這裡必須解決三個"實做"的問題。這一些問題都必須要有很快的實做,或者說他們可以用\log N的多項式個數這麼多量子閘來實做。

  1. 製造狀態的疊加。 這可以藉著對所有輸入的量子位元使用哈達瑪閘(Hadamard gate)來達成。另一個方法是使用量子傅立葉變換(如下述)。
  2. 以量子變換實做函數f。 要達成這件事情,秀爾使用了反復平方以完成模的取幂變換。值得注意的是,這一個步驟比起量子傅立葉變換還難以實做,需要更多輔助的量子位元以及大體上更多的閘來完成。
  3. 進行量子傅立葉變換。 利用受控旋轉閘(controlled rotation gate)和哈達瑪閘,秀爾設計了一個量子傅立葉變換的線路,只有使用了q(q-1)/2 = O((\log Q)^2)個閘(Q = 2q)。[5]

在這一些變換之後,測量會逼近於週期r的近似值。為簡明起見,假設存在yyr/Q是整數,則測量到y的機率是1(理論上)。要推導出這個,我們首先注意到對任何整數b

e^{-2 \pi i b yr/Q} = 1。因此Q/r的平方能告訴我們測量y的概率,因為b大致上取Q/r個值,因此概率為1/r^2。有ry使得yr/Q為整數,f(x_0)也有r種可能,所以機率總和為1。

Note:另一種解釋秀爾演算法的方式是將之視為是喬裝過後的量子相位估計演算法

參考資料[编辑]

  1. ^ Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H. & Chuang, Isaac L., Experimental realization of Shor's量子factoring algorithm using nuclear magnetic resonance, Nature, 2001, 414 (6866): 883–887, doi:10.1038/414883a .
  2. ^ Braunstein, S. L.; Caves, C. M.; Jozsa, R.; Linden, N.; Popescu, S.; Schack, R., Separability of Very Noisy Mixed States and Implications for NMR Quantum Computing, Phys. Rev. Lett, 1999, 83 (5): 1054–1057, doi:10.1103/PhysRevLett.83.1054 
  3. ^ Lu, Chao-Yang; Browne, Daniel E.; Yang, Tao & Pan, Jian-Wei, Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits, Physical Review Letters, 2007, 99 (25): 250504, doi:10.1103/PhysRevLett.99.250504 
  4. ^ Lanyon, B. P.; Weinhold, T. J.; Langford, N. K.; Barbieri, M.; James, D. F. V.; Gilchrist, A. & White, A. G., Experimental Demonstration of a Compiled Version ofshor's algorithm with quantum Entanglement, Physical Review Letters, 2007, 99 (25): 250505, doi:10.1103/PhysRevLett.99.250505 
  5. ^ Shor 1999,第14页.

延伸閱讀[编辑]