- 選擇任意數字
< ![{\displaystyle N}](//wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
- 計算gcd(
,
)。這裡可以使用輾轉相除法來計算。
- 若gcd(
,
) ≠ 1,則我們有了一個
非平凡的因數,因此這部份結束了。
- 否則,利用下面的週期尋找子程序(Period-finding subroutine,下面會列出)來找出下面這個函數的週期
:
,
換句話說,找出
在
裡面的階
,或者最小的正整數
令
。
- 若
是奇數,回到第一步。
- 若
/2 ≡ -1 (mod
),回到第一步。
- gcd(a
/2+1,
)與gcd(a
/2-1,
)至少有一個是
非平凡的因數。分解完成。
此演算法包含兩個部份。演算法的第一部份是將因數分解問題轉成尋找一個函式的週期,而且這部份可以用傳統方式實作。第二部份則是使用量子傅立葉變換來搜尋這個函式的週期,而且這一部份是量子加速這整個演算法的理由。
小於N且互質於N的整數組成一個有限大,且對乘法同餘N的群。在步驟3之後,我們有一個屬於這個群的整數a。既然這個群是有限的,a必有一個有限大的階r,也就是最小的正整數令
![{\displaystyle a^{r}\equiv 1\ {\mbox{mod}}\ N.\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/2d2097f747c3b4a12429199331a8d2821bcb1161)
因此可知,N是a r − 1的因數。先假設我們有能力獲得r,而且r是偶數。則
![{\displaystyle a^{r}-1=(a^{r/2}-1)(a^{r/2}+1)\equiv 0\ {\mbox{mod}}\ N}](//wikimedia.org/api/rest_v1/media/math/render/svg/7eb3353dad7ae4c20c460f915b3c2bdf5c7eb5bc)
![{\displaystyle \Rightarrow N\ |(a^{r/2}-1)(a^{r/2}+1).\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/864a1f07903a7f40fe400609304f87b7e8ce6a60)
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是兩個質數的乘積,則這是唯一可能的分解。
秀爾的週期尋找演算法非常倚賴量子計算機同時處於許多狀態的能力。物理學家稱呼這個特性為狀態的「疊加」。在計算函數f的週期時,我們會同時估計這個函數的所有點。
不過,量子物理不允許我們直接取得這些資訊。測量會令觀測結果塌陷到其中一個可能的結果,並摧毀所有其他可能。如果不是因為不可複製原理,我們可以先測量f(x)而非測量x,再製造幾個結果態的拷貝(將會是多個有著同樣的f(x)的態的疊加)。對這些態上的x的測量將會給出能給出相同f(x)的不同的x,由此推導出週期來。因為我們不能複製完全相同的量子狀態,這個方法行不通。因此在這裡我們需要小心的轉變疊加態,使其成為可以以高機率回傳正確答案的狀態。這可使用量子傅立葉變換來達成。
因此秀爾在這裡必須解決三個「實作」的問題,而且速度必須夠快,也就是可這些問題可以用量子閘個數為
的多項式來實作。
- 製造狀態的疊加。
這可以藉著對所有輸入的量子位元使用哈達瑪閘(Hadamard gate)來達成。另一個方法是使用量子傅立葉變換(如下述)。
- 以量子變換實作函數f。
要達成這件事情,秀爾使用了反覆平方以完成模的取幂變換。值得注意的是,這一個步驟比起量子傅立葉變換還難以實作,需要更多輔助的量子位元以及明顯更多的閘來完成。
- 進行量子傅立葉變換。
利用受控旋轉閘(controlled rotation gate)和哈達瑪閘,秀爾設計了一個量子傅立葉變換的線路,只使用了
個閘(Q = 2q)。[5]
在這一些變換之後,測量會給出週期r的近似值。為簡明起見,假設存在y令yr/Q是整數,則測量到y的機率是1(理論上)。要推導出這個,我們首先注意到對任何整數b,
。因此Q/r的平方能告訴我們測量y的概率,因為b大致上取Q/r個值,因此概率為
。有r個y使得yr/Q為整數,
也有r種可能,所以機率總和為1。
Note:另一種解釋秀爾演算法的方式是將之視為是喬裝過後的量子相位估計演算法。
Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H. & Chuang, Isaac L., Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance, Nature, 2001, 414 (6866): 883–887, doi:10.1038/414883a.
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
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
- Nielsen, Michael A. & Chuang, Isaac L., Quantum Computation and Quantum Information, Cambridge University Press, 2000.
- Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007, ISBN 019857049X
- "Explanation for the man in the street" (页面存档备份,存于互联网档案馆) by Scott Aaronson, "approved (页面存档备份,存于互联网档案馆)" 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 10105000 quantum algorithm tutorials that are already on the web."):
- Shor, Peter W., Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J.Sci.Statist.Comput., 1999, 41 (2): 303–332, doi:10.1137/S0036144598347011, . 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 (页面存档备份,存于互联网档案馆), Matthew Hayward, 2005-02-17, imsa.edu, LaTeX2HTML version of the original 2750 line LaTeX document (页面存档备份,存于互联网档案馆), also available as a 61 page PDF (页面存档备份,存于互联网档案馆) or postscript (页面存档备份,存于互联网档案馆) document.
- Quantum Computation and Shor's Factoring Algorithm (页面存档备份,存于互联网档案馆), Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
- Shor's Factoring Algorithm (页面存档备份,存于互联网档案馆), Notes from Lecture 9 of Berkeley CS 294-2, dated 4 Oct 2004, 7 page postscript document.
- Chapter 6 Quantum Computation (页面存档备份,存于互联网档案馆), 91 page postscript document, Caltech, Preskill, PH229.
- Quantum computation: a tutorial (页面存档备份,存于互联网档案馆) by Samuel L. Braunstein.
- The Quantum States of Shor's Algorithm (页面存档备份,存于互联网档案馆), by Neal Young, Last modified: Tue May 21 11:47:38 1996.
- A now-circular reference via the Wikipedia copy of this article (页面存档备份,存于互联网档案馆); clearly Aaronson's link originally reached the 20 Feb 2007 version (页面存档备份,存于互联网档案馆).
- III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm (页面存档备份,存于互联网档案馆), 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 (页面存档备份,存于互联网档案馆). 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 (页面存档备份,存于互联网档案馆), 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 (页面存档备份,存于互联网档案馆), from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Comments welcome!, Sanjeev Arora and Boaz Barak, Princeton University.