3. 量子计算基础速览

Shor因数分解算法之所以能在多项式时间内完成大整数分解，根本原因在于它把“找因子”这个数论问题转化成了“找周期”这个量子相位估计问题。要真正读懂后续的量子线路实现，必须先建立一套与Shor算法直接对应的量子计算语言。本节只讲与Shor算法强相关的部分：量子比特如何表示、叠加如何让量子寄存器同时承载大量输入、纠缠如何把函数求值与输入绑定、量子门如何构造模幂运算与量子傅里叶变换、测量如何把量子态坍缩成可读出的周期信息。

量子比特：从经典位到复振幅

经典比特只能取0或1，而一个量子比特（qubit）的状态是二维复希尔伯特空间中的单位向量，写作

|ψ⟩ = α|0⟩ + β|1⟩，其中 α、β 为复数且 |α|² + |β|² = 1。

这里 α、β 称为概率幅，|α|² 和 |β|² 分别是测量得到0和1的概率。与经典概率不同的是，概率幅带相位，相位在后续干涉中会起作用——这正是Shor算法能够提取周期的物理基础。在Shor算法中，我们通常需要两个寄存器：第一个寄存器存放指数 x 的叠加态，宽度 n = ⌈2log₂N⌉ 个量子比特；第二个寄存器存放模幂结果 a^x mod N，宽度约为 log₂N 个量子比特。例如分解 N = 15 时，n = 8，第一寄存器8个量子比特，第二寄存器4个量子比特，共12个量子比特即可演示。

叠加：一次制备，批量输入

对每个量子比特施加哈达玛门 H，可以把 |0⟩ 变成 (|0⟩+|1⟩)/√2。对 n 个初态为 |0⟩ 的量子比特全部施加 H，得到

(1/√2ⁿ) Σ_x=0^2ⁿ−1 |x⟩

也就是说，一个 n 比特寄存器在叠加态下同时“包含”了 0 到 2ⁿ−1 的全部输入。Shor算法的第一步正是用 H 门把第一寄存器制备成这样的均匀叠加态，从而让后续的模幂运算一次性作用在所有 x 上。需要强调的是，叠加并不意味着能同时读出所有结果；读出仍受测量规则限制，叠加的价值在于让量子门对全部输入并行施加线性变换，再通过干涉把目标信息集中到少数可测状态上。

纠缠：把输入与函数值绑定

Shor算法的核心操作是计算 f(x) = a^x mod N。在量子线路中，这一步通过受控模幂运算实现：以第一寄存器的每个比特为控制位，在第二寄存器上执行相应的模乘。由于第一寄存器处于叠加态，运算完成后两个寄存器进入纠缠态

(1/√2ⁿ) Σ_x |x⟩|a^x mod N⟩

此时第二寄存器的值不再独立，而是与第一寄存器的 x 一一对应。纠缠在这里的作用是“把函数求值结果写进量子态”，使得后续对第二寄存器测量时，第一寄存器会坍缩到与某个函数值对应的 x 子集上——这些 x 恰好构成等差数列，公差就是我们要找的周期 r。这正是Shor算法把函数周期信息“编码”进量子态的关键机制。

量子门：构造模幂与傅里叶变换

Shor线路中真正“干活”的门主要有三类。第一类是单比特门 H，用于制备叠加态。第二类是受控模乘门，实现 |x⟩|y⟩ → |x⟩|y·a^(2ⁱ) mod N⟩，其中 i 为控制位序号；把 a^(2ⁱ) mod N 预先算成经典常数，再实现对应的模乘线路，是编译阶段的主要工作。第三类是量子傅里叶变换 QFT，它由 H 门和受控相位门 R_k 组合而成，作用是把周期为 r 的态变换成频率域上的尖峰。以 N = 15、a = 7 为例，7ˣ mod 15 的序列为 1, 7, 4, 13, 1, 7, 4, 13…，周期 r = 4；QFT 后测量第一寄存器，会以较大概率得到与 k/r（k = 0,1,2,3）对应的整数 c，再用连分数展开 c/2ⁿ 恢复出 r = 4。

测量：把量子信息转成经典结果

测量是Shor算法中唯一把量子态转成经典比特的环节，也是理解算法“为什么只测一次就够”的关键。对第二寄存器测量后，第一寄存器坍缩为 {x₀, x₀+r, x₀+2r, …} 的等间隔叠加；此时对它做 QFT，等间隔序列会在频率域形成间隔为 2ⁿ/r 的峰。测量第一寄存器得到某个 c 后，计算 c/2ⁿ 的连分数展开，取分母不超过 N 的收敛子作为 r 的候选。若 r 为偶数且 a^(r/2) mod N ≠ ±1，则 gcd(a^(r/2)−1, N) 与 gcd(a^(r/2)+1, N) 给出非平凡因子；否则换一个 a 重新运行。这个“测量—连分数—gcd—验证”的收尾逻辑，正是后续实现章节要反复调试的部分。

与经典计算的关键差异

经典算法求周期需要逐个计算 f(x) 并比较，复杂度随 N 指数增长；Shor算法用一次受控模幂把全部 x 的函数值编码进纠缠态，再用 QFT 让周期信息以干涉峰的形式出现，从而把周期提取的代价降到多项式级。需要清醒认识的是：量子部分只负责“找周期”，因子提取、连分数展开、gcd 计算仍是经典运算；量子优势来自叠加与干涉，而不是“同时算出所有答案并直接读出”。这也解释了为什么实现 Shor算法时，模幂线路的深度和量子比特数才是真正的工程瓶颈。