秀尔演算法

秀尔演算法（英语：Shor's algorithm）是一个于1994年发现的，以数学家彼得·秀尔命名，针对整数分解题目的的量子演算法（在量子计算机上面运作的演算法）。不正式地说，它解决的题目是：给定一个整数 ${\displaystyle N}$，找出它的质因数。在一个量子计算机上面，要分解整数${\displaystyle N}$，秀尔演算法的运作需要多项式时间（时间是 ${\displaystyle \log N}$的某个多项式这么长，${\displaystyle \log N}$ 在这里的意义是输入的档案长度）。准确来说，该演算法花费 ${\displaystyle O((\log N)^{3})}$ 的时间，展示出质因数分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类BQP里面。这比传统上已知的最快的因数分解演算法普通数域筛选法所花费的次指数时间——大约 ${\displaystyle 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。^[1]不过，对于IBM的实验是否是量子计算的真实展示，有一些疑虑出现，因为没有发现缠结现象。^[2]IBM的实验之后，也有其他的团队以光学量子位元实验秀尔演算法，并强调可观察到其缠结现象。^[3][4]

程序

试著解决的问题是：给定一个合成数${\displaystyle N}$，找到整数${\displaystyle p}$在${\displaystyle 1}$和${\displaystyle N}$之间且不包含${\displaystyle 1}$和${\displaystyle N}$，并且${\displaystyle N}$整除于${\displaystyle p}$。

秀尔演算法包含两个部份：

1. 一个以传统电脑运作的简化演算法，将因数分解简化成搜寻阶问题。
2. 一个量子演算法，解决搜寻阶问题。

传统部份

1. 选择任意数字${\displaystyle a}$ < ${\displaystyle N}$
2. 计算gcd（ ${\displaystyle a}$ , ${\displaystyle N}$ ）。这里可以使用辗转相除法来计算。
3. 若gcd( ${\displaystyle a}$ , ${\displaystyle N}$ ) ≠ 1，则我们有了一个 ${\displaystyle N}$ 非平凡的因数，因此这部份结束了。
4. 否则，利用下面的周期寻找子程序（Period-finding subroutine，下面会列出）来找出下面这个函数的周期 ${\displaystyle r}$ ：

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

   换句话说，找出${\displaystyle a}$在${\displaystyle \mathbb {Z} _{N}}$里面的阶${\displaystyle r}$，或者最小的正整数 ${\displaystyle r}$ 令 ${\displaystyle f(x+r)=f(x)}$。
5. 若 ${\displaystyle r}$ 是奇数，回到第一步。
6. 若 ${\displaystyle a}$ ^{${\displaystyle r}$ /2} ≡ -1 (mod ${\displaystyle N}$ ),回到第一步。
7. gcd(a ^{${\displaystyle r}$ /2}+1, ${\displaystyle N}$ )与gcd(a ^{${\displaystyle r}$ /2}-1, ${\displaystyle N}$ )至少有一个是 ${\displaystyle N}$ 非平凡的因数。分解完成。

量子部份：周期寻找子程序（Period-finding subroutine）

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

程序如下：

1. 将暂存器初始化成

   ${\displaystyle Q^{-1/2}\sum _{x=0}^{Q-1}\left|x\right\rangle \left|0\right\rangle }$

   ${\displaystyle x}$ 从0到 ${\displaystyle Q}$ − 1。所以这一个初始态是 ${\displaystyle Q}$ 个状态的叠加。
2. 建立量子函式版本的 ${\displaystyle f}$ ( ${\displaystyle x}$ )，并且应用于上面的叠加态，得到

   ${\displaystyle Q^{-1/2}\sum _{x}\left|x\right\rangle \left|f(x)\right\rangle }$.

   这里仍旧是 ${\displaystyle Q}$ 个状态的叠加。
3. 对输入暂存器进行量子傅立叶变换。这个变换（操作于二的幂次—— ${\displaystyle Q=2^{q}}$ 个叠加态上面） 使用一个 ${\displaystyle Q}$次单位根例如${\displaystyle \omega =e^{2\pi i/Q}}$将任意给定态${\displaystyle \left|x\right\rangle }$的振幅平均分布在所有 ${\displaystyle Q}$ 个${\displaystyle \left|y\right\rangle }$态上。另一个方法是对于每个不同的 ${\displaystyle x}$ ：

   ${\displaystyle U_{QFT}\left|x\right\rangle =Q^{-1/2}\sum _{y}\omega ^{xy}\left|y\right\rangle }$。

   由此得到最终状态：

   ${\displaystyle Q^{-1}\sum _{x}\sum _{y}\omega ^{xy}\left|y\right\rangle \left|f(x)\right\rangle }$.

   这是一个远多过 ${\displaystyle Q}$ 个状态的叠加态，但是远低过 ${\displaystyle Q}$ ²个。虽然在和中有 ${\displaystyle Q}$ ²项，但只要 ${\displaystyle x_{0}}$ 和 ${\displaystyle x}$ 的值相同，态${\displaystyle \left|y\right\rangle \left|f(x_{0})\right\rangle }$就可被提出来。令

   ${\displaystyle \omega =e^{2\pi i/Q}}$为 ${\displaystyle Q^{th}}$的一个单位根，

   ${\displaystyle r}$ 为 ${\displaystyle f}$ 的周期，

   ${\displaystyle x}$ ₀为一个产生相同 ${\displaystyle f}$ ( ${\displaystyle x}$ )的 ${\displaystyle x}$ 的集里面的最小元素（我们已经有 ${\displaystyle x}$ ₀ < ${\displaystyle r}$ ），以及

   b在0到${\displaystyle \lfloor (Q-x_{0}-1)/r\rfloor }$之间使得${\displaystyle x_{0}+rb<Q}$。那么${\displaystyle \omega ^{ry}}$则是复平面的一个单位向量（${\displaystyle \omega }$是一个单位根， ${\displaystyle r}$ 和y是整数），而${\displaystyle Q^{-1}\left|y\right\rangle \left|f(x_{0})\right\rangle }$在最终状态下的系数则为

   ${\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}}$。这一求和的每一项代表一个获得相同结果的不同路径，而量子干涉发生。在单位向量${\displaystyle \omega ^{ryb}}$几乎与复平面指向同一方向（要求${\displaystyle \omega ^{ry}}$指向正实数轴）时，干涉将是相长的。

4. 进行测量。我们由输入寄存器取得结果y，由输出寄存器取得${\displaystyle f(x_{0})}$。而既然 ${\displaystyle f}$ 是周期，对某对y和${\displaystyle f(x_{0})}$进行测量的概率则由

   ${\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}}$

   给出。分析显示这个概率越高，单位向量${\displaystyle \omega ^{ry}}$就越接近正实数轴，或者${\displaystyle {\frac {ry}{Q}}}$越接近一个整数。除非 ${\displaystyle r}$ 是2的乘方，否则它不会是${\displaystyle Q}$的因子。
5. 对${\displaystyle {\frac {y}{Q}}}$进行连分数展开来计算其近似值，并生成满足下列两个条件的${\displaystyle {\frac {c}{r'}}}$：

   ${\displaystyle A:r'<N}$

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

   藉著满足这一些条件， ${\displaystyle r}$ ′有很高的机率会是我们要找的周期 ${\displaystyle r}$ 。
6. 检查 ${\displaystyle f}$ ( ${\displaystyle x}$ ) = ${\displaystyle f}$ ( ${\displaystyle x}$ + ${\displaystyle r}$ ′) ${\displaystyle \Leftrightarrow }$ ${\displaystyle a^{r}\equiv 1{\pmod {N}}}$。如果成功了，我们就完成了。
7. 否则，以接近y左右的数值作为 ${\displaystyle r}$ 的候选，或者说多取几个 ${\displaystyle r'}$.如果任何候选成功了，我们就完成了。
8. 否则，回到第一步骤（也就是全部重新做一次）。

演算法的解释

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

I.从周期得到因数

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

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

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

${\displaystyle a^{r}-1=(a^{r/2}-1)(a^{r/2}+1)\equiv 0\ {\mbox{mod}}\ N}$

${\displaystyle \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，由此推导出周期来。因为我们不能复制完全相同的量子状态，这个方法行不通。因此在这里我们需要小心的转变叠加态，使其成为可以以高机率回传正确答案的状态。这可使用量子傅立叶变换来达成。

因此秀尔在这里必须解决三个“实作”的问题，而且速度必须够快，也就是可这些问题可以用量子闸个数为${\displaystyle \log N}$的多项式来实作。

1. 制造状态的叠加。 这可以藉著对所有输入的量子位元使用哈达玛闸（Hadamard gate）来达成。另一个方法是使用量子傅立叶变换（如下述）。
2. 以量子变换实作函数f。 要达成这件事情，秀尔使用了反复平方以完成模的取幂变换。值得注意的是，这一个步骤比起量子傅立叶变换还难以实作，需要更多辅助的量子位元以及明显更多的闸来完成。
3. 进行量子傅立叶变换。 利用受控旋转闸（controlled rotation gate）和哈达玛闸，秀尔设计了一个量子傅立叶变换的线路，只使用了${\displaystyle q(q-1)/2=O((\log Q)^{2})}$个闸（Q = 2^q）。^[5]

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

${\displaystyle e^{-2\pi ibyr/Q}=1}$。因此Q/r的平方能告诉我们测量y的概率，因为b大致上取Q/r个值，因此概率为${\displaystyle 1/r^{2}}$。有r个y使得yr/Q为整数，${\displaystyle 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 quantum 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页.

延伸阅读

• 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 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.