4.3 Shor 算法：从周期寻找到因数分解

4.3 Shor 算法：从周期寻找到因数分解

本节摘要：Shor 算法证明量子计算机可把大数分解从"亚指数难度"降到多项式时间，直指 RSA 密码的数学地基。它的结构是一套精巧的接力：经典数学把"分解 N"转化为"求函数 a^x mod N 的周期 r"，量子部分只负责一件事——用叠加与量子傅里叶变换高效读出 r，其余全由经典后处理收尾。本节用 N=15、a=7 把整条链手工走通，你看完就能向任何人完整复述这个算法为什么成立。

转化一：分解问题变成互质问题

输入奇合数 N（既非素数也不含小因子）。随机挑一个 a，先求 gcd(a, N)——这步可能直接中大奖（比如挑到与 N 有公因子的 a），概率不低，撞上就完事。没中大奖时 gcd(a, N)=1，a 与 N 互质，此时有一条初等数论结论派上用场：

定义 f(x) = a^x mod N
f 是周期函数：存在最小正整数 r 使 f(x + r) = f(x) 对一切 x 成立
等价说法：a^r ≡ 1 (mod N)
​

直觉：a 的各次幂对 N 取余，余数必然在有限个值里打转，迟早回到起点。r 就是这个回转周期（数学上叫 a 模 N 的乘法阶）。

转化二：周期变成因子

拿到偶数周期 r 后，分解只剩一步初等代数。记 y = a^(r/2)，由 a^r ≡ 1 得 y² ≡ 1 (mod N)，即：

y² − 1 ≡ 0 (mod N) → (y−1)(y+1) ≡ 0 (mod N) → N 整除 (y−1)(y+1)
​

N 整除两数乘积，却（在不平凡的情形下）既不整除 y−1 也不整除 y+1——那 N 的因子必然"分家"，一部分落在 y−1 里、一部分落在 y+1 里。于是 gcd(y−1, N) 与 gcd(y+1, N) 就是非平凡因子。整条经典的账，欧几里得辗转相除就能清完。

量子部分：一次叠加，一场傅里叶

整条算法里，唯一经典算不动的是找 r。朴素做法要从 x=1 逐个算 a^x mod N 直到余数回到 1——r 可以大到与 N 同阶，N 是几百位数时这条就是天文路。Shor 的量子部分把它变成干涉问题：

第一寄存器（t 位，Q = 2^t ≈ N²）：全部铺 H
  → (1/√Q) Σ_{x=0}^{Q−1} |x⟩

第二寄存器：受控计算 a^x mod N（可逆电路，经典可构造）
  → (1/√Q) Σ_x |x⟩|a^x mod N⟩

测量第二寄存器：坍缩到某个余数值 k
  第一寄存器只剩那些 x 满足 a^x ≡ k 的项——它们以 r 为周期散布
  → (1/√m) Σ_{j} |x0 + j·r⟩ ⊗ |k⟩

对第一寄存器做量子傅里叶变换（QFT）：周期信号变成频谱尖峰
  → 测量以高概率得到接近 Q/r 整数倍的读数
​

三段各司其职：铺开制造"所有指数同时在场"；受控模乘把周期信息写进振幅分布（3.4 节说的"编码"）；QFT 是干涉引擎，把"每 r 个出现一次"这种节律兑换成可测的频率尖峰。QFT 深度 O(t²)，比经典 FFT 的 O(Q log Q) 省出指数级——省的正是"全谱同时计算"这一步。

图：Shor 算法全链路——周期寻找到因数分解

复杂度账单与 RSA 的时间刻度

Shor 的总复杂度（含模乘电路优化）约 O((log N)³)，对比经典最快的通用数域筛法（亚指数 exp(O((log N)^{1/3}))）——大数增长下这是碾压级的差距。落到人们熟悉的刻度上：2048 位 RSA 的分解，超算按现有算法要按"宇宙年龄"计；同等规模若用容错量子机，工程估算折算到数十小时级。数字随硬件假设浮动，但量级差距是数学保证的，不随工程进步缩水——这正是后量子密码迁移（第 6.1 节）被视为"现在就要动"的原因。

演练与三个必答问

把 N=21 交给读者当练习：取 a=2，写出 2^x mod 21 的序列（2, 4, 8, 16, 11, 1），得 r=6，验证 gcd(2³+1, 21)=gcd(9,21)=3、gcd(7,21)=7。整条经典链条 30 秒走完，难的只剩量子读数——这正是算法的设计哲学：把不可破的经典难题转化为量子擅长的周期测量。

问一：量子部分出错怎么办？ 测量读数只是"大概率"落在理想倍数附近，且 r 可能是奇数或 y 平凡。工程答案是失败重来：多测几发、连分数交叉验证，单轮成功概率有正的常数下界，期望几轮内收敛。

问二：QFT 和经典 FFT 差在哪？ 功能相同、代价结构相反：经典 FFT 处理 Q 个点要 Q log Q 时间，QFT 对 2^t 维矢量只要 t² 个门——因为它不是"算出谱"，而是让谱"自己干涉成型"。

问三：什么时候真能威胁 RSA？ 拦路虎是纠错：分解 2048 位数需要数千个逻辑量子比特，按当前表面码开销折算数百万物理比特（第 5.3 节给这笔账）。实验室已演示的最小案例正是本节手算的 N=15——从 15 到 2048 位，隔着整个容错量子计算的工程史。

本节要点回顾

• 两次转化：分解 → 互质周期（数论），周期 → 因子（gcd 代数），量子只承包周期寻找。
• 量子三段：铺开、受控模乘编码、QFT 干涉读出，全程多项式深度。
• N=15 手算链：序列 7-4-13-1 得 r=4，gcd 得 3 与 5——完整可复述的最小样本。
• 威胁是数学上的确定、工程上的遥远：复杂度差距不缩水，兑现取决于容错硬件。

Shor 与 Grover 都是"问题喂给量子、答案一次读出"的完美算法。但当下真实设备噪声大到撑不起深线路，于是出现了另一条务实路线——把部分工作交还给经典优化器。最后一节看这条变分路线怎么走。

常见疑问与加练

问题一：为什么第一寄存器要取约 N² 那么大

读出的频率尖峰必须能区分出"周期 r"的信息。第一寄存器的 Q 个采样点里要装下整数个完整周期（否则周期读不准），同时 QFT 后的分辨粒度是 Q——Q 至少要大于 N²，测得读数的连分数展开才能唯一锁定真正的 r。这是"采样定理"思想在量子寄存器上的翻版：想分辨细结构，采样窗就得够宽。代价只是多几十个比特与几层 QFT 门，多项式级，完全付得起。

问题二：受控模乘电路凭什么能造出来

因为模乘可以分解为"移位 + 加法 + 取模"的组合，而加法器有成熟的可逆电路实现（如以 CNOT 与 Toffoli 门搭的进位加法器）。整条模乘是 O((log N)²) 量级的门数——电路工程学问题，不是原理问题。4.3 节说"量子部分只管周期"，确切说是"量子部分管叠加与 QFT，中间那座模乘电路是编译器帮你砌的墙"。

加练：完整跑一遍 N=35

取 a=13（与 35 互质）。序列：13¹=13，13²=169≡29，13³≡8，13⁴≡19，13⁵≡22，13⁶≡21，13⁷≡18，13⁸≡4，13⁹≡17，13¹⁰≡16，13¹¹≡3，13¹²≡6，13¹³≡8——出现重复，回头精确核对得周期 r=12。r 是偶数，y=13⁶ mod 35=21，gcd(21+1,35)=gcd(22,35)=1（平凡，本轮失败），gcd(20,35)=5——中一个因子！换 a 重来或接受"单轮一半成功率"的统计性质。这个练习的价值：让你亲手体验"失败轮次"是算法的一部分，工程实现里必须按期望轮数预算时间。