秀爾演算法

Template:NoteTA 秀爾演算法（Template:Lang-en）是一個于1994年發現的，以數學家彼得·秀爾命名，針對整數分解題目的的量子演算法（在量子計算機上面運作的演算法）。不正式地說，它解決的題目是：給定一個整數 $N$，找出它的質因數。在一個量子計算機上面，要分解整數$N$，秀爾演算法的運作需要多項式時間（時間是 $\log N$的某個多項式這麼長，$\log N$ 在這裡的意義是輸入的檔案長度）。准确来说，该演算法花費 $O((\log N{)}^3)$ 的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類BQP裡面。這比傳統上已知的最快的因數分解演算法普通數域篩選法所花費的次指數時間——大約 $O(e^{1.9(\log N{)}^{\frac{1}{3}}(\log \log N{)}^{\frac{2}{3}}})$還要快了一個指數。

秀爾演算法非常重要，它意味着：假如有可用的量子計算機，我們可以破解基于公開密鑰加密的算法（比如RSA加密演算法）。RSA演算法的基礎在於假設了我們不能有效率的分解一個已知的整數。就目前所知，這假設對傳統（即非量子）的電腦為真；沒有已知的傳統演算法可以在多項式時間內解決這個問題。但秀爾演算法展示了因數分解問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於建立量子計算機和研究新的量子計算機演算法是一個强大的動力。

2001年，IBM的一個小組展示了秀爾演算法的實例，使用NMR實驗的量子計算機及7個量子位元，將15分解成3×5。不过，对于IBM的實驗是否是量子計算的真實展示，有一些疑慮出現，因為沒有发现纏結現象。IBM的實驗之後，也有其他的團隊以光學量子位元實驗秀爾演算法，並強調可觀察到其纏結現象。

程序

試著解決的問題是：給定一個合成數$N$，找到整數$p$在$1$和$N$之間且不包含$1$和$N$，並且$N$整除於$p$。

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

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

傳統部份

1. 選擇任意數字$a$ < $N$
2. 計算gcd（ $a$ , $N$ ）。這裡可以使用輾轉相除法來計算。
3. 若gcd( $a$ , $N$ ) ≠ 1，則我們有了一個 $N$ 非平凡的因數，因此這部份結束了。
4. 否則，利用下面的週期尋找子程序（Period-finding subroutine，下面會列出）來找出下面這個函數的週期 $r$ ：

   $f(x)=a^x\text{mod}N$,

   換句話說，找出$a$在${\mathbb{Z}}_N$裡面的階$r$，或者最小的正整數 $r$ 令 $f(x+r)=f(x)$。
5. 若 $r$ 是奇數，回到第一步。
6. 若 $a$ ^{$r$ /2} ≡ -1 (mod $N$ ),回到第一步。
7. gcd(a ^{$r$ /2}+1, $N$ )與gcd(a ^{$r$ /2}-1, $N$ )至少有一個是 $N$ 非平凡的因數。分解完成。

量子部份：週期尋找子程序（Period-finding subroutine）

這個演算法使用的量子線路是為了在給定一個固定常數 $N$ 以及一個任意常數 $a$ 之下，找出$f(x)=a^{x}modN$ 所設定的。給定 $N$ ,找出 $Q$ = 2 ^$q$ 且合乎$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}|x⟩|0⟩$

   $x$ 從0到 $Q$ − 1。所以這一個初始態是 $Q$ 個狀態的疊加。
2. 建立量子函式版本的 $f$ ( $x$ )，並且應用於上面的疊加態，得到

   $Q^{-1/2}\sum _x|x⟩|f(x)⟩$.

   這裡仍舊是 $Q$ 個狀態的疊加。
3. 對輸入暫存器進行量子傅立葉變換。這個變換（操作於二的冪次—— $Q=2^q$ 個疊加態上面） 使用一個 $Q$次單位根例如$\omega =e^{2\pi i/Q}$將任意給定態$|x⟩$的振幅平均分佈在所有 $Q$ 個$|y⟩$態上。另一個方法是對於每個不同的 $x$ ：

   $U_{QFT}|x⟩=Q^{-1/2}\sum _y{\omega }^{xy}|y⟩$。

   由此得到最終狀態：

   $Q^{-1}\sum _x\sum _y{\omega }^{xy}|y⟩|f(x)⟩$.

   這是一個遠多過 $Q$ 個狀態的疊加態，但是遠低過 $Q$ ²個。雖然在和中有 $Q$ ²項，但只要 $x_0$ 和 $x$ 的值相同，態$|y⟩|f(x_0)⟩$就可被提出來。令

   $\omega =e^{2\pi i/Q}$為 $Q^{th}$的一個單位根，

   $r$ 為 $f$ 的週期，

   $x$ ₀為一個產生相同 $f$ ( $x$ )的 $x$ 的集裡面的最小元素（我們已經有 $x$ ₀ < $r$ ），以及

   b在0到$\lfloor (Q-x_0-1)/r\rfloor$之間使得$x_0+rb<Q$。那麼${\omega }^{ry}$則是復平面的一個單位向量（$\omega$是一個單位根， $r$ 和y是整數），而$Q^{-1}|y⟩|f(x_0)⟩$在最終狀態下的係數則為

   $\sum _{x:f(x)=f(x_0)}{\omega }^{xy}=\sum _b{\omega }^{(x_0+rb)y}={\omega }^{x_{0}y}\sum _b{\omega }^{rby}$。這一求和的每一項代表一個獲得相同結果的不同路徑，而量子干涉發生。在單位向量${\omega }^{ryb}$幾乎與復平面指向同一方向（要求${\omega }^{ry}$指向正實數軸）時，干涉將是相長的。

4. 進行測量。我們由輸入寄存器取得結果y，由輸出寄存器取得$f(x_0)$。而既然 $f$ 是週期，對某對y和$f(x_0)$進行測量的概率則由

   ${\left|Q^{-1}\sum _{x:f(x)=f(x_0)}{\omega }^{xy}\right|}^2=Q^{-2}{\left|\sum _b{\omega }^{(x_0+rb)y}\right|}^2$

   給出。分析顯示這個概率越高，單位向量${\omega }^{ry}$就越接近正實數軸，或者$\frac{ry}{Q}$越接近一個整數。除非 $r$ 是2的乘方，否則它不會是$Q$的因子。
5. 對$\frac{y}{Q}$進行連分數展開來計算其近似值，並生成滿足下列兩個條件的$\frac{c}{r^{\prime }}$：

   $A:r^{\prime }<N$

   $B:|\frac{y}{Q}-\frac{c}{r^{\prime }}|<\frac{1}{2Q}$

   藉著滿足這一些條件， $r$ ′有很高的機率會是我們要找的週期 $r$ 。
6. 檢查 $f$ ( $x$ ) = $f$ ( $x$ + $r$ ′) $\iff$ $a^r\equiv 1(\mathrm{mod}N)$。如果成功了，我們就完成了。
7. 否則，以接近y左右的數值作為 $r$ 的候選，或者說多取幾個 $r^{\prime }$.如果任何候選成功了，我們就完成了。
8. 否則，回到第一步驟（也就是全部重新做一次）。

演算法的解釋

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

I.從週期得到因數

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

$a^r\equiv 1\text{mod}N.$

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

$a^r-1=(a^{r/2}-1)(a^{r/2}+1)\equiv 0\text{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）有一個非顯然的公因數。

證明：為了簡化，我們分別用u和v表示（a ^{r / 2} − 1）和（a ^{r / 2} + 1）。N | uv，故kN = uv（k是某個整數）。假設gcd(v, N) = 1：則必定存在某個整數m和n令mv + nN = 1 (這是最大公因數的一個性質)。兩邊同乘以u，我們得到mkN + nuN = u, 所以 N | u，从而產生矛盾（前文提到（a ^{r / 2} − 1）必定不能整除於N）。故假设不成立，即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 = 2^q）。

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

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

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

参见

• 泡利矩陣
• 量子退火

延伸閱讀

• Template:Citation.
• Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007, ISBN 019857049X
• "Explanation for the man in the street" Template:Wayback by Template:Tsl, "approved Template:Wayback" by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). Scott Aaronson suggests the following 12 references as further reading (out of "the 10¹⁰⁵⁰⁰⁰ quantum algorithm tutorials that are already on the web."):
• Template:Citation. Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
• Quantum Computing and Shor's Algorithm Template:Wayback, Matthew Hayward, 2005-02-17, imsa.edu, LaTeX2HTML version of the original 2750 line LaTeX document Template:Wayback, also available as a 61 page PDF Template:Wayback or postscript Template:Wayback document.
• Quantum Computation and Shor's Factoring Algorithm Template:Wayback, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
• Shor's Factoring Algorithm Template:Wayback, Notes from Lecture 9 of Berkeley CS 294-2, dated 4 Oct 2004, 7 page postscript document.
• Chapter 6 Quantum Computation Template:Wayback, 91 page postscript document, Caltech, Preskill, PH229.
• Quantum computation: a tutorial Template:Wayback by Samuel L. Braunstein.
• The Quantum States of Shor's Algorithm Template:Wayback, by Neal Young, Last modified: Tue May 21 11:47:38 1996.
• A now-circular reference via the Wikipedia copy of this article Template:Wayback; clearly Aaronson's link originally reached the 20 Feb 2007 version Template:Wayback.
• III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm Template:Wayback, LECTURE NOTES ON QUANTUM COMPUTATION, Cornell University, Physics 481-681, CS 483; Spring, 2006 by N. David Mermin. Last revised 2006-03-28, 30 page PDF document.
• arXiv quant-ph/0303175 Shor's Algorithm for Factoring Large Integers. C. Lavor, L.R.U. Manssur, R. Portugal Template:Wayback. Submitted on 29 Mar 2003. This work is a tutorial on Shor's factoring algorithm by means of a worked out example. Some basic concepts of Quantum Mechanics and quantum circuits are reviewed. It is intended for non-specialists which have basic knowledge on undergraduate Linear Algebra. 25 pages, 14 figures, introductory review.
• arXiv quant-ph/0010034 Shor's Quantum Factoring Algorithm, Samuel J. Lomonaco, Jr Template:Wayback, Submitted on 9 Oct 2000, This paper is a written version of a one hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
• Chapter 20 Quantum Computation Template:Wayback, from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Comments welcome!, Sanjeev Arora and Boaz Barak, Princeton University.