秀尔算法

试着解决的问题是：给定一个合成数${\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 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）

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:另一种解释秀尔算法的方式是将之视为是乔装过后的量子相位估计算法。

• 泡利矩阵
• 量子退火