Shor阶寻找与因子恢复

形式陈述

输入、输出与精度

给定整数 $N\ge2$ 、 $1\le a<N$ 且 $\gcd(a,N)=1$ ，求最小正整数

r=\operatorname{ord}_N(a)=\min\{t\ge1:a^t\equiv1\pmod N\}.

这里使用模同余。各个 $a^j$ 都是单位，有限置换的轨道必然回到 $1$ ，所以阶存在且 $r<N$ 。令 $n=\lceil\log_2N\rceil$ ， $K=2^m$ 为不小于 $N^2$ 的最小二次幂，故 $m=O(n)$ 且 $K>r^2$ 。

下面的阶算法允许失败符号，也可能输出错误的阶候选；给定 $0<\varepsilon<1$ ，固定重复次数后，正确输出精确 $r$ 的概率至少为 $1-\varepsilon$ 。证明先采用理想的可逆布尔门与精确角度 Fourier 门，最后另计固定门集近似误差。阶寻找的量子部分沿用相位估计，但特征态制备、受控幂和经典恢复都要在本页落实。[1, §6]

全空间上的模乘置换

对已知单位 $b\bmod N$ ，定义整个 $n$ qubit 寄存器上的置换

f_b(x)=\begin{cases}bx\bmod N,&0\le x<N,\\x,&N\le x<2^n,\end{cases} \qquad U_b|x\rangle=|f_b(x)\rangle.

前一块由乘 $b^{-1}$ 逆转，后一块恒等，所以 $U_b$ 确实酉。不能只写有效整数上的函数而遗漏其余计算基态。

经典重复平方预计算 $b_j=a^{2^j}\bmod N$ 。在整个空间上都有 $U_a^{2^j}=U_{b_j}$ 。因此第 $j$ 条控制线调用的是已知常数 $b_j$ 的受控模乘电路，并非重复执行 $U_a$ 共 $2^j$ 次。

直觉

模乘让轨道 $1,a,a^2,\ldots$ 循环移动。这个循环的 Fourier 特征态以不同速度积累相位，相位分别为 $s/r$ 。初态 $|1\rangle$ 自动在这些特征态上具有相等权重，因而不必先知道 $r$ 来制备它们。

量子测量只交出近似分数 $y/K$ 。经典端要先恢复其附近的小分母有理数，再判断分母与真实阶的关系。好样本可能约掉公因子，坏样本甚至可能给出阶的倍数；两种现象都必须进入成功率证明。

例子与边界

$N=21,a=2$ 的六点轨道

直接模乘得到

1\longrightarrow2\longrightarrow4\longrightarrow8 \longrightarrow16\longrightarrow11\longrightarrow1, \qquad r=6.

取 $K=512$ 。下表列出每个隐藏特征相位对应的最近网格输出；它不是说所有其他输出概率为零。

相位标签 $s$	最近输出 $y$	恢复的既约相位	分母 $q$	$2^q\bmod21$
0	0	$0/1$	1	2
1	85	$1/6$	6	1
2	171	$1/3$	3	8
3	256	$1/2$	2	4
4	341	$2/3$	3	8
5	427	$5/6$	6	1

例如

85/512=[0;6,42,2],\qquad427/512=[0;1,5,42,2].

两串连分数分别包含 $1/6$ 和 $5/6$ ，误差都是 $1/1536<1/1024=1/(2K)$ 。给定 $s=1$ 或 $5$ ，最近输出的概率约为 $0.6839189433$ 。这两项“隐藏标签及其最近输出”的联合概率之和为 $2\cdot0.6839189433/6\approx0.2279729811$ ；它不等于仅按测量值 $85,427$ 合并的边缘概率，后者还接收其他相位的贡献。

恢复 $r=6$ 后， $b=2^3\bmod21=8$ ，所以

\gcd(8-1,21)=7,\qquad\gcd(8+1,21)=3.

指数检验通过不等于已经证明最小阶

同一实验可能测得 $y=213$ ，其连分数为 $[0;2,2,2,10,4]$ ，包含 $5/12$ ，而

\left|\frac{213}{512}-\frac5{12}\right|=\frac1{1536}, \qquad 12<21,\qquad2^{12}\equiv1\pmod{21}.

这个结果的混合概率约为 $9.64618\times10^{-6}>0$ 。候选 $12$ 通过检验，却不是最小阶 $6$ 。因此算法不能一遇到通过项就把它当作确定正确的阶；下文使用固定次数采样后取最小通过项，并证明它以高概率等于 $r$ 。

对比 $N=15,a=2,r=4,K=256$ ：四个相位恰好落在网格上，测量值只有 $0,64,128,192$ ，各概率 $1/4$ 。其中两个既约分母为 $4$ ； $2^{4/2}=4$ 给出因子 $3,5$ 。整除网格的例子省去了尾部，不能替代一般情形分析。

模21六点轨道经相位采样与连分数恢复阶，再由平方根获得因子；检验通过的倍数不代表最小阶

推论与应用

清除辅助位的可逆模乘

一个大小 $O(n^2)$ 的经典布尔电路可计算 $f_b(x)$ ：以逐位移位加法求乘积并作长除法约减，另比较 $x<N$ 。将每个中间结果写入新辅助位、复制输出后反向撤销计算，得到

V_b:|x\rangle|y\rangle|0_{\rm work}\rangle \longmapsto|x\rangle|y\oplus f_b(x)\rangle|0_{\rm work}\rangle.

这里复制的是计算基标签的可逆 XOR，不是克隆未知量子态；对叠加按线性性作用。随后

|x,0\rangle\xrightarrow{V_b}|x,f_b(x)\rangle \xrightarrow{\rm SWAP}|f_b(x),x\rangle \xrightarrow{V_{b^{-1}}}|f_b(x),0\rangle.

最后一步用 $x\oplus f_{b^{-1}}(f_b(x))=0$ ，所有辅助位都清零。把外部控制加到各个固定大小可逆门上，只增加常数开销。[2, §3] 通用构造用 $O(n^2)$ 门和辅助位，每次 QPE 的 $m=O(n)$ 个乘法因而用 $O(n^3)$ 算术门；精确角度 QFT 另用 $O(n^2)$ 门。本页不宣称这个通用构造达到最优空间。

不制备特征态，仍得到均匀相位混合

在上述 $r$ 维轨道子空间中定义

|u_s\rangle=\frac1{\sqrt r}\sum_{j=0}^{r-1} e^{-2\pi isj/r}|a^j\bmod N\rangle,\qquad0\le s<r.

移位 $j\mapsto j+1$ 给出 $U_a|u_s\rangle=e^{2\pi is/r}|u_s\rangle$ 。单位根求和证明这些向量正交归一，并且

|1\rangle=\frac1{\sqrt r}\sum_s|u_s\rangle.

以此为目标寄存器做 QPE，最终联合态为

\frac1{\sqrt r}\sum_s\sum_{y=0}^{K-1}A_{s/r}(y)|y\rangle|u_s\rangle, \qquad A_\theta(y)=\frac1K\sum_{x=0}^{K-1}e^{2\pi ix(\theta-y/K)}.

忽略正交目标寄存器后，交叉项消失，所以

\Pr(Y=y)=\frac1r\sum_s|A_{s/r}(y)|^2.

这可分析成先均匀选隐藏 $s$ ，再按相位 $s/r$ 的 QPE 分布抽样；实验并未实际测量 $s$ ， $Y$ 也一般不均匀。

连分数为何恢复正确的小分母

取最近整数 $y_s=\operatorname{round}(Ks/r)$ ，并列时任选。 $s=0$ 给出 $0$ ；其余 $s/r$ 距离两端至少为 $1/r>1/(2K)$ ，因此这里不用绕过端点的圆周代表：

\left|y_s/K-s/r\right|\le1/(2K), \qquad \Pr(Y=y_s\mid s)\ge4/\pi^2.

第二式由相位估计页的有限几何级数界得到。约分 $s/r=t/q$ 后， $q=r/\gcd(s,r)\le r<N$ ，且

\left|y_s/K-t/q\right|\le1/(2K)<1/(2q^2).

用到的连分数判据是：若既约 $0<t/q<1$ 满足 $|x-t/q|<1/(2q^2)$ ，则它是 $x$ 的收敛分数。[3, §9.1] 这里给出该判据的局部证明。设 $t'/q'$ 是 $t/q$ 规范有限展开的前一个收敛分数，则 $0<q'<q$ 、 $|tq'-t'q|=1$ 。保留该展开为前缀、令下一完全商从 $1$ 变化到无穷，得到端点 $t/q$ 与 $(t+t')/(q+q')$ 之间的区间。另一份末项拆成“少一再接一”的展开，其前项是 $(t-t')/(q-q')$ ，给出另一侧端点 $(2t-t')/(2q-q')$ 。两个外端点距 $t/q$ 分别为

\frac1{q(q+q')},\qquad\frac1{q(2q-q')},

都严格大于 $1/(2q^2)$ 。区间内部有相应连分数前缀，故任何满足严格界的 $x$ 都保留 $t/q$ 为收敛分数； $x=t/q$ 时它是最后一项。相位零单独处理为 $0/1$ 。

对任意实际测量值 $y$ ，扫描其收敛分数，只保留

1\le q<N,\qquad |y/K-t/q|\le1/(2K).

这样的既约分数至多一个：不同 $t/q,t'/q'$ 相距至少 $1/(qq')>1/N^2$ ，却若都合格则相距至多 $1/K\le1/N^2$ ，矛盾。计算连分数、用整数交叉乘法检验误差和模幂均只需输入位数的多项式时间。

固定次数与最小通过候选

候选还须满足 $a^q\equiv1\pmod N$ 。由除法 $q=ur+v$ 、 $0\le v<r$ ，若检验通过则 $a^v=1$ ，阶的最小性迫使 $v=0$ ；因此每个通过项都是 $r$ 的倍数。

若最近网格事件同时满足 $\gcd(s,r)=1$ ，就得到 $q=r$ 。一次好事件概率至少

p_* =\frac4{\pi^2}\frac{\varphi(r)}r.

这里 $\varphi$ 是Euler函数。不需借用渐近解析数论即可给出足够的多项式界。对 $r>1$ ，将不同素因子排序为 $p_1<\cdots<p_k$ ，则 $p_i\ge i+1$ 且 $2^k\le r$ ，所以

\frac r{\varphi(r)}=\prod_i\frac{p_i}{p_i-1} \le\prod_i\frac{i+1}{i}=k+1\le1+\log_2r.

独立运行

T=\left\lceil\frac{\pi^2}{4}(1+\log_2N)\ln(1/\varepsilon)\right\rceil

次，返回所有通过分母的最小值；没有通过项就报失败。所有项都是 $r$ 的倍数，一旦有一次好事件，最小值就恰为 $r$ 。未出现好事件的概率至多 $(1-p_*)^T\le e^{-p_*T}\le\varepsilon$ 。 $r=1$ 即 $a=1$ 可直接返回。没有假设能高效分解候选 $q$ ，也没有把通过模幂检验称为确定的最小性证书。

从偶数阶到非平凡因子

分解时先处理偶数、素数和素数幂，只考虑有至少两个不同素因子的奇数 $N$ 。随机选 $1\le a<N$ ，先算 $\gcd(a,N)$ ；非单位直接给出因子。对单位求精确阶 $r$ ：若它为偶数，令 $b=a^{r/2}\bmod N$ ，则 $b^2=1$ ，最小性排除 $b=1$ 。若再有 $b\ne-1$ ，

d_- =\gcd(b-1,N),\qquad d_+=\gcd(b+1,N)

都是非平凡因子。例如 $d_-=1$ 会使 $b-1$ 可逆，由 $(b-1)(b+1)=0\pmod N$ 推出 $b=-1$ ，矛盾； $d_-=N$ 则意味着 $b=1$ 。另一个符号同理。两个 gcd 的公因子整除 $2$ ，而 $N$ 奇，故两者互素；其乘积为 $N$ 。

说明随机底数为何有常数成功率时，用整数中国剩余定理和标准的“奇素数幂单位群为循环群”定理。[2, §5] 写 $N=\prod_{i=1}^k p_i^{e_i}$ ， $k\ge2$ 。单位的各坐标独立均匀，设局部阶的二进制指数为 $t_i=v_2(r_i)$ 。在阶为 $2^{h_i}u_i$ 、 $u_i$ 奇的局部循环群中， $t_i=0$ 的概率为 $2^{-h_i}$ ， $t_i=t\ge1$ 的概率为 $2^{t-1-h_i}$ ，都不超过 $1/2$ 。

整体阶是局部阶的最小公倍数。全部 $t_i=0$ 时阶奇；全部相同且为正时 $b$ 在所有坐标都为 $-1$ ；指数不全相同时，最大指数坐标给 $-1$ ，较小指数坐标给 $+1$ ，形成非平凡平方根。因此坏底数恰是所有 $t_i$ 相同，概率至多 $2^{-(k-1)}\le1/2$ 。分解 $N$ 只出现在分析中，不是算法先验输入。

若阶子程序错误概率为 $\varepsilon<1/2$ ，一次随机底数尝试的成功率至少为 $1/2-\varepsilon$ 。输出前总是直接验证 $1<d<N$ 且 $d\mid N$ ；错误阶可能造成重试，却不会让错误因子通过验证。对任意通过的偶数候选 $q$ 使用平方根步骤时，要同时排除 $a^{q/2}=+1,-1$ 。

固定有限门集的实现先把重复次数公式中的 $\varepsilon$ 换成 $\varepsilon/2$ ，使理想采样错误至多 $\varepsilon/2$ ；再把这整个重复实验的门近似总预算设为 $\varepsilon/2$ 。门误差到测量总变差的证明保证经典后处理的成功事件概率再损失至多 $\varepsilon/2$ 。这补上精确旋转模型与有限门集之间的接口；不包含物理噪声或容错开销。

参考资料

[1] Richard Cleve, Artur Ekert, Chiara Macchiavello, Michele Mosca, Quantum Algorithms Revisited，v1，1997，§5，印刷 pp. 10–11：QPE；§6，pp. 12–13，式 (6.1)–(6.4)：阶的特征相位、初态及受控幂。本文额外明确坏测量尾部，并独立证明最小通过候选的保证。
[2] Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer，v2，1996，§3，印刷 pp. 9–12：可逆计算、重复平方与逆运算清除；§5，pp. 15–16：因子恢复和随机底数；pp. 18–19：连分数恢复。页码均为该预印本。
[3] Andrew M. Childs, Lecture Notes on Quantum Algorithms，2025-04-17，§9.1，印刷 pp. 37–39，尤其 p. 39 的连分数判据。本文的宽松重复次数界与 $21$ 的全部算例直接推导。

形式陈述 ​

输入、输出与精度 ​

全空间上的模乘置换 ​

N=21,a=2 的六点轨道 ​

指数检验通过不等于已经证明最小阶 ​

清除辅助位的可逆模乘 ​

不制备特征态，仍得到均匀相位混合 ​

连分数为何恢复正确的小分母 ​

固定次数与最小通过候选 ​

从偶数阶到非平凡因子 ​

反向链接