秀爾演算法- 维基百科，自由的百科全书

秀爾演算法（英語：Shor's algorithm）是一個于1994年發現的，以數學家彼得·秀爾命名，針對整數分解題目的的量子演算法（在量子計算機上面運作的演算法）。

秀爾演算法 維基百科，自由的百科全書 跳至導覽 跳至搜尋 秀爾演算法（英語：Shor'salgorithm）是一個於1994年發現的，以數學家彼得·秀爾命名，針對整數分解題目的的量子演算法（在量子計算機上面運作的演算法）。

不正式地說，它解決的題目是：給定一個整數 N {\displaystyleN} ，找出他的質因數。

在一個量子計算機上面，要分解整數 N {\displaystyleN} ，秀爾演算法的運作需要多項式時間（時間是 log ⁡ N {\displaystyle\logN} 的某個多項式這麼長， log ⁡ N {\displaystyle\logN} 在這裡的意義是輸入的檔案長度）。

準確來說，該演算法花費 O ( ( log ⁡ N ) 3 ) {\displaystyleO((\logN)^{3})} 的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類BQP裡面。

這比傳統上已知的最快的因數分解演算法普通數域篩選法所花費的次指數時間——大約 O ( e 1.9 ( log ⁡ N ) 1 3 ( log ⁡ log ⁡ N ) 2 3 ) {\displaystyleO(e^{1.9(\logN)^{\frac{1}{3}}(\log\logN)^{\frac{2}{3}})}} 還要快了一個指數。

秀爾演算法非常重要，它意味著：假如有可用的量子計算機，我們可以破解基於公開密鑰加密的演算法（比如RSA加密演算法）。

RSA演算法的基礎在於假設了我們不能有效率的分解一個已知的整數。

就目前所知，這假設對傳統（即非量子）的電腦為真；沒有已知的傳統演算法可以在多項式時間內解決這個問題。

但秀爾演算法展示了因數分解問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。

這對於建立量子計算機和研究新的量子計算機演算法是一個強大的動力。

2001年，IBM的一個小組展示了秀爾演算法的實例，使用NMR實驗的量子計算機及7個量子位元，將15分解成3×5。

[1]不過，對於IBM的實驗是否是量子計算的真實展示，有一些疑慮出現，因為沒有發現纏結現象。

[2]IBM的實驗之後，也有其他的團隊以光學量子位元實驗秀爾演算法，並強調可觀察到其纏結現象。

[3][4] 目次 1程序 1.1傳統部份 1.2量子部份：週期尋找子程序（Period-findingsubroutine） 2演算法的解釋 2.1I.從週期得到因數 2.2II.找尋週期 3參見 4參考資料 5延伸閱讀 程式[編輯] 試著解決的問題是：給定一個合成數 N {\displaystyleN} ，找到整數 p {\displaystylep} 在 1 {\displaystyle1} 和 N {\displaystyleN} 之間且不包含 1 {\displaystyle1} 和 N {\displaystyleN} ，並且 N {\displaystyleN} 整除於 p {\displaystylep} 。

秀爾演算法包含兩個部份： 一個以傳統電腦運作的簡化演算法，將因數分解簡化成搜尋階問題。

一個量子演算法，解決搜尋階問題。

傳統部份[編輯] 選擇任意數字 a {\displaystylea} < N {\displaystyleN} 計算gcd（ a {\displaystylea} , N {\displaystyleN} ）。

這裡可以使用輾轉相除法來計算。

若gcd( a {\displaystylea} , N {\displaystyleN} )≠1，則我們有了一個 N {\displaystyleN} 非平凡的因數，因此這部份結束了。

否則，利用下面的週期尋找子程式（Period-findingsubroutine，下面會列出）來找出下面這個函式的週期 r {\displaystyler} ： f ( x ) = a x   mod   N {\displaystylef(x)=a^{x}\{\mbox{mod}}\N} , 換句話說，找出 a {\displaystylea} 在 Z N {\displaystyle\mathbb{Z}_{N}} 裡面的階 r {\displaystyler} ，或者最小的正整數 r {\displaystyler} 令 f ( x + r ) = f ( x ) {\displaystylef(x+r)=f(x)} 。

若 r {\displaystyler} 是奇數，回到第一步。

若 a {\displaystylea} r {\displaystyler} /2≡-1(mod N {\displaystyleN} ),回到第一步。

gcd(a r {\displaystyler} /2+1, N {\displaystyleN} )與gcd(a r {\displaystyler} /2-1, N {\displaystyleN} )至少有一個是 N {\displaystyleN} 非平凡的因數。

分解完成。

量子部份：週期尋找子程式（Period-findingsubroutine）[編輯] 這個演算法使用的量子線路是為了在給定一個固定常數 N {\displaystyleN} 以及一個任意常數 a {\displaystylea} 之下，找出 f ( x ) = a x mod N {\displaystylef(x)=a^{x}\mod{N}} 所設定的。

給定 N {\displaystyleN} ,找出 Q {\displaystyleQ} =2 q {\displaystyleq} 且合乎 N 2 ≤ Q < 2 N 2 {\displaystyleN^{2}\leqQ<2N^{2}} （這同時表示 Q / r > N {\displaystyleQ/r>N} ）。

輸入和輸出量子位元暫存器需要儲存從0到 Q {\displaystyleQ} -1所有值的疊加態，因此分別需要 q {\displaystyleq} 個量子位元。

這裡使用看起來比所需的數量還要更多一倍的量子位元，保證了即使週期 r {\displaystyler} 的大小逼近 N {\displaystyleN} /2，也至少有 N {\displaystyleN} 個不同的 x {\displaystylex} 會產生相同的 f ( x ) {\displaystylef(x)} 。

程式如下： 將暫存器初始化成 Q − 1 / 2 ∑ x = 0 Q − 1 | x ⟩ | 0 ⟩ {\displaystyleQ^{-1/2}\sum_{x=0}^{Q-1}\left|x\right\rangle\left|0\right\rangle} x {\displaystylex} 從0到 Q {\displaystyleQ} −1。

所以這一個初始態是 Q {\displaystyleQ} 個狀態的疊加。

建立量子函式版本的 f {\displaystylef} ( x {\displaystylex} )，並且應用於上面的疊加態，得到 Q − 1 / 2 ∑ x | x ⟩ | f ( x ) ⟩ {\displaystyleQ^{-1/2}\sum_{x}\left|x\right\rangle\left|f(x)\right\rangle} . 這裡仍舊是 Q {\displaystyleQ} 個狀態的疊加。

對輸入暫存器進行量子傅立葉變換。

這個變換（操作於二的冪次—— Q = 2 q {\displaystyleQ=2^{q}} 個疊加態上面） 使用一個 Q {\displaystyleQ} 次單位根例如 ω = e 2 π i / Q {\displaystyle\omega=e^{2\pii/Q}} 將任意給定態 | x ⟩ {\displaystyle\left|x\right\rangle} 的振幅平均分佈在所有 Q {\displaystyleQ} 個 | y ⟩ {\displaystyle\left|y\right\rangle} 態上。

另一個方法是對於每個不同的 x {\displaystylex} ： U Q F T | x ⟩ = Q − 1 / 2 ∑ y ω x y | y ⟩ {\displaystyleU_{QFT}\left|x\right\rangle=Q^{-1/2}\sum_{y}\omega^{xy}\left|y\right\rangle} 。

由此得到最終狀態： Q − 1 ∑ x ∑ y ω x y | y ⟩ | f ( x ) ⟩ {\displaystyleQ^{-1}\sum_{x}\sum_{y}\omega^{xy}\left|y\right\rangle\left|f(x)\right\rangle} . 這是一個遠多過 Q {\displaystyleQ} 個狀態的疊加態，但是遠低過 Q {\displaystyleQ} 2個。

雖然在和中有 Q {\displaystyleQ} 2項，但只要 x 0 {\displaystylex_{0}} 和 x {\displaystylex} 的值相同，態 | y ⟩ | f ( x 0 ) ⟩ {\displaystyle\left|y\right\rangle\left|f(x_{0})\right\rangle} 就可被提出來。

令 ω = e 2 π i / Q {\displaystyle\omega=e^{2\pii/Q}} 為 Q t h {\displaystyleQ^{th}} 的一個單位根， r {\displaystyler} 為 f {\displaystylef} 的週期， x {\displaystylex} 0為一個產生相同 f {\displaystylef} ( x {\displaystylex} )的 x {\displaystylex} 的集裡面的最小元素（我們已經有 x {\displaystylex} 0< r {\displaystyler} ），以及 b在0到 ⌊ ( Q − x 0 − 1 ) / r ⌋ {\displaystyle\lfloor(Q-x_{0}-1)/r\rfloor} 之間使得 x 0 + r b < Q {\displaystylex_{0}+rb