程序

我们要试着解决的问题是：给定一个合成数 N ,找到整数 p 在 1 和 N 之间且不包含 1 和 N ,并且 N 整除于 p 。

秀尔算法包含两个部分：

一个以传统的电脑运作的简化算法，将因数分解简化成搜寻阶的问题。

一个量子算法，解决搜寻阶的问题。

传统部分

选择任意数字 a < N

计算gcd（ a , N ）。这里可以使用辗转相除法来计算。

若gcd( a , N ) ≠ 1，则我们有了一个 N 非平凡的因数，因此这部分结束了。

否则，利用下面的周期寻找副函式（Period-finding subroutine，下面会列出）来找出下面这个函数的周期 r ： f ( x ) = a x mod N {\displaystyle f(x)=a^{x}\ {\mbox{mod}}\ N} , 换句话说，找出 a {\displaystyle a} 在Z N {\displaystyle \mathbb {Z} _{N}}里面的阶 r {\displaystyle r} ，或者最小的正整数 r 令 f ( x + r ) = f ( x ) {\displaystyle f(x+r)=f(x)} 。

若 r 是奇数，回到第一步。

若 a ≡ -1 (mod N ),回到第一步。

gcd(a +1, N )与gcd(a -1, N )分别是 N 非平凡的因数。分解完成。

量子部分：周期寻找副函式（Period-finding subroutine）

这个算法使用的量子线路是为了在给定一个固定常数 N 以及一个任意常数 a 之下，找出 f ( x ) = a mod N 所设定的。给定 N ,找出 Q = 2 且合乎 N 2 ≤ ≤ --> Q < 2 N 2 {\displaystyle N^{2}\leq Q N {\displaystyle Q/r>N} ）。输入和输出量子位元暂存器需要储存从0到 Q -1所有值的叠加态，因此分别需要 q 个量子位元。这里使用看起来比所需的数量还要更多一倍的量子位元，保证了即使周期 r 的大近 N /2，也至少有 N 个不同的 x 会产生相同的 f ( x )。

程序如下：

将暂存器初始化成 Q − − --> 1 / 2 ∑ ∑ --> x = 0 Q − − --> 1 | x 〉 | 0 〉 {\displaystyle Q^{-1/2}\sum _{x=0}^{Q-1}\left|x\right\rangle \left|0\right\rangle } x 从0到 Q − 1。所以这一个初始态是 Q 个状态的叠加。

建立量子函式版本的 f ( x )，并且应用于上面的叠加态，得到 Q − − --> 1 / 2 ∑ ∑ --> x | x 〉 | f ( x ) 〉 {\displaystyle Q^{-1/2}\sum _{x}\left|x\right\rangle \left|f(x)\right\rangle } . 这里仍旧是 Q 个状态的叠加。

对输入暂存器进行量子傅立叶变换。这个变换（操作于二的幂次-- Q = 2 个叠加态上面） 使用一个 Q 单位根例如 ω ω --> = e 2 π π --> i / Q {\displaystyle \omega =e^{2\pi i/Q}} 将任意给定态 | x 〉 {\displaystyle \left|x\right\rangle } 的振幅平均分布在所有 Q 个 | y 〉 {\displaystyle \left|y\right\rangle } 态上。另一个方法是对于每个不同的 x ： U Q F T | x 〉 = Q − − --> 1 / 2 ∑ ∑ --> y ω ω --> x y | y 〉 {\displaystyle U_{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 ) 〉 {\displaystyle Q^{-1}\sum _{x}\sum _{y}\omega ^{xy}\left|y\right\rangle \left|f(x)\right\rangle } . 这是一个远多过 Q 个状态的叠加态，但是远低过 Q 个。虽然在和中有 Q 项，但只要 x 0 和 x 的值相同，态 | y 〉 | f ( x 0 ) 〉 {\displaystyle \left|y\right\rangle \left|f(x_{0})\right\rangle } 就可被提出来。令 ω ω --> = e 2 π π --> i / Q {\displaystyle \omega =e^{2\pi i/Q}} 为 Q 的一个单位根，r 为 f 的周期，x 0 为一个产生相同 f ( x )的 x 的集里面的最小元素（我们已经有 x 0 ( Q − − --> x 0 − − --> 1 ) / r ⌋ ⌋ --> {\displaystyle \lfloor (Q-x_{0}-1)/r\rfloor } 之间使得 x 0 + r b r y {\displaystyle \omega ^{ry}} 则是复平面的一个单位向量（ ω ω --> {\displaystyle \omega } 是一个单位根， r 和 y 是整数），而 Q − − --> 1 | y 〉 | f ( x 0 ) 〉 {\displaystyle Q^{-1}\left|y\right\rangle \left|f(x_{0})\right\rangle } 在最终状态下的系数则为∑ ∑ --> x : f ( x ) = f ( x 0 ) ω ω --> x y = ∑ ∑ --> b ω ω --> ( x 0 + r b ) y = ω ω --> x 0 y ∑ ∑ --> b ω ω --> r b y {\displaystyle \sum _{x:\,f(x)=f(x_{0})}\omega ^{xy}=\sum _{b}\omega ^{(x_{0}+rb)y}=\omega ^{x_{0}y}\sum _{b}\omega ^{rby}} 。这一求和的每一项代表 一个获得相同结果的不同路径 ，而量子干涉发生。在单位向量 ω ω --> r y b {\displaystyle \omega ^{ryb}} 几乎与复平面指向同一方向（要求 ω ω --> r y {\displaystyle \omega ^{ry}} 指向正实数轴）时，干涉将是相长的。

进行测量。我们由输入寄存器取得结果 y ，由输出寄存器取得 f ( x 0 ) {\displaystyle f(x_{0})} 。而既然 f 是周期，对某对 y 和 f ( x 0 ) {\displaystyle f(x_{0})} 进行测量的概率则由 | Q − − --> 1 ∑ ∑ --> x : f ( x ) = f ( x 0 ) ω ω --> x y | 2 = Q − − --> 2 | ∑ ∑ --> b ω ω --> ( x 0 + r b ) y | 2 {\displaystyle \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}} 给出。分析显示这个概率越高，单位向量 ω ω --> r y {\displaystyle \omega ^{ry}} 就越接近正实数轴，或者 yr/Q 就越接近一个整数。除非r是2的乘方，否则它不会是Q的因子。

对 y/Q 进行连分数展开来计算其近似值，并生成满足下列两个条件的 c/r ′： A: r′B: |y/Q - c/r′| < 1/2Q 借着满足这一些条件， r ′有很高的概率会是我们要找的周期 r 。

检查 f ( x ) = f ( x + r ′) ⇔ ⇔ --> {\displaystyle \Leftrightarrow } a r ≡ ≡ --> 1 ( mod N ) {\displaystyle a^{r}\equiv 1{\pmod {N}}} 。如果成功了，我们就完成了。

否则，以接近y左右的数值作为 r 的候选，或者说多取几个 r ′.如果任何候选成功了，我们就完成了。

否则，回到第一步骤（也就是全部重新作一次）。

算法的解释

此算法包含两个部分。算法的第一部分是将因数分解问题转成寻找一个函式的周期，而且这部分可以用传统方式实做。第二部分则是使用量子傅立叶变换来搜寻这个函式的周期，而且这一部分是量子加速这整个算法的理由。

I.从周期得到因数

小于 N 且互质于 N 的整数组成一个有限大，且对乘法同余 N 的群。在步骤3之后，我们有一个属于这个群的整数 a 。既然这个群是有限的， a 必有一个有限大的阶 r ,也就是最小的正整数令

因此可知， N 是 a − 1的因数。先假设我们有能力获得 r ，而且 r 是偶数。则

r 是令 a ≡ 1 最小的 正整数，所以（ a − 1）必定不能整除于 N 。若（ a + 1）也不整除于 N 的话，则 N 必定与（ a − 1）或者（ a + 1）有一个非显然的公因数。

证明： 为了简化，我们分别用 u 和 v 表示（ a − 1）和（ a + 1）。 N | uv ，故 kN = uv （k是某个整数）。假设gcd( v , N ) = 1：则必定存在某个整数 m 和 n 令 mv + nN = 1 (这是最大公因数的一个性质)。两边同乘以 u ，我们得到 mkN + nuN = u , so N | u 。gcd( v , N ) ≠ 1，故产生矛盾。用类似的方法，可以得知若（ a + 1）不能整除于 N , gcd( u , N ) ≠ 1。故得证u和v不同时与 N 互质。

这给予我们一个 N 的因数分解。若 N 是两个质数的乘积，则这是 唯一 可能的分解。

II.找寻周期

秀尔的周期寻找算法非常倚赖量子计算机同时计算许多状态的能力。物理学家称呼这个特性为这一些状态的"叠加"。在计算函数 f 的周期时，我们会同时估计这个函数的所有点。

不过，量子物理不允许我们直接取得这一些资讯。测量会令观测结果塌陷到其中一个可能的结果，并摧毁其他可能性的存在。但是根据不可克隆原理，我们可以先测量 f ( x )而非测量 x ，再制造几个结果态的拷贝（将会是多个有着同样的 f ( x )的态的叠加）。对这些态上的 x 的测量将会给出能给出相同 f ( x )的不同的 x ，由此推导出周期来。因为我们不能复制完全相同的量子状态，这个方法行不通。因此在这里我们需要小心的将叠加态转变成我们有办法以很高的正确概率回答答案的状态。在这里我们使用量子傅立叶变换来达成。

因此秀尔在这里必须解决三个"实做"的问题。这一些问题都必须要有很快的实做，或者说他们可以用 log ⁡ ⁡ --> N {\displaystyle \log N} 的多项式个数这么多量子闸来实做。

制造状态的叠加。 这可以借着对所有输入的量子位元使用哈达玛闸（Hadamard gate）来达成。另一个方法是使用量子傅立叶变换（如下述）。

以量子变换实做函数 f 。 要达成这件事情，秀尔使用了反复平方以完成模的取幂变换。值得注意的是，这一个步骤比起量子傅立叶变换还难以实做，需要更多辅助的量子位元以及大体上更多的闸来完成。

进行量子傅立叶变换。 利用受控旋转闸（controlled rotation gate）和哈达玛闸，秀尔设计了一个量子傅立叶变换的线路，只有使用了 q ( q − − --> 1 ) / 2 = O ( ( log ⁡ ⁡ --> Q ) 2 ) {\displaystyle q(q-1)/2=O((\log Q)^{2})} 个闸（ Q = 2 ）。

在这一些变换之后，测量会逼近于周期 r 的近似值。为简明起见，假设存在 y 令 yr/Q 是整数，则测量到 y 的概率是1（理论上）。要推导出这个，我们首先注意到对任何整数 b ，

Note:另一种解释秀尔算法的方式是将之视为是乔装过后的量子相位估计算法。

延伸阅读

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 （ 英语 ： 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 10 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 ,arXiv:quant-ph/9508027v2 . 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 original2750 line LaTeX document, also available as a 61 pagePDForpostscriptdocument.

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 tutorialbySamuel 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 ofthis article; clearly Aaronson"s link originally reachedthe 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 cirts 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.

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。