Shor 算法思想

Grover 的结尾指了条路：要指数加速，得找有结构的问题。 1994 年 Peter Shor 找到了那个问题——大数因数分解。 它的结构是一种隐藏的周期性，而「用干涉找周期」， 从双缝实验起就是量子力学的看家本领。 这一节不深入数论证明，但把整条逻辑链和量子部分算透。

问题开门：一道乘法容易、除法要命的算术题

$3\times5=15$，口算。反过来「15 = ? × ?」也不难。 但把数字换成 617 位（2048 比特）：两个千位大素数相乘，电脑毫秒级完成； 从乘积反推两个因子,用已知最快的经典算法（数域筛）， 需要的时间量级是

$$\exp\!\left[c\,(\ln N)^{1/3}(\ln\ln N)^{2/3}\right],\qquad c\approx1.9\tag{9.9.1}$$

——亚指数：比多项式糟得多。对 2048 位的 $N$， 今天全球算力加起来也要以千年计。RSA 公钥密码的安全性正是押在这条单行道上： 公钥里明晃晃写着 $N$，谁能分解它谁就能读一切密文。

第一级跳：分解 ⇒ 求周期（经典数论，只用结论）

Shor 的第一步是把问题改写。随便挑一个与 $N$ 互素的 $a$，考察模幂函数

$$f(x)=a^x \bmod N\tag{9.9.2}$$

它必然是周期的：$f(x+r)=f(x)$，最小正周期 $r$ 叫 $a$ 的阶。 数论给出一座桥（陈述不证）：

若 $r$ 是偶数，且 $a^{r/2}\not\equiv-1\pmod N$，则 $\gcd(a^{r/2}-1,\,N)$ 与 $\gcd(a^{r/2}+1,\,N)$ 给出 $N$ 的非平凡因子。

直觉一句话：$a^r\equiv1$ 意味着 $(a^{r/2}-1)(a^{r/2}+1)\equiv0\pmod N$—— $N$ 整除这个乘积却（在条件下）不整除任一因子， 所以 $N$ 的素因子被拆开分给了两边，用 $\gcd$（辗转相除，快得很）各领回一个。 随机选 $a$ 时条件以至少 $1/2$ 的概率满足，不满足就换个 $a$ 重来。

手算 $N=15$，取 $a=7$：

$$7^1=7,\quad 7^2=49\equiv4,\quad 7^3\equiv28\equiv13,\quad 7^4\equiv91\equiv1\pmod{15}\tag{9.9.3}$$

周期 $r=4$，偶数，且 $7^2\equiv4\not\equiv-1$。于是

$$\gcd(7^2-1,15)=\gcd(48,15)=3,\qquad \gcd(7^2+1,15)=\gcd(50,15)=5\tag{9.9.4}$$

$15=3\times5$，成功。整个算法里唯一困难的步骤只剩：求周期 $r$。 经典地求周期不比直接分解便宜（要把 $f$ 算到上万亿步才见一个循环）； 量子力学接手的正是这一步。

第二级跳：把周期装进叠加态

照 DJ 的方子开场：第一寄存器（$t$ 个 qubit，$Q=2^t\gg r^2$）打满 $H$， 对每个 $x$ 并行算模幂，写入第二寄存器：

$$\frac{1}{\sqrt Q}\sum_{x=0}^{Q-1}\ket{x}\ket{a^x\bmod N}\tag{9.9.5}$$

现在测量第二寄存器（也可以不测，只是讲解方便），得到某个值 $f_0$。 第一寄存器随之塌缩到所有给出该值的 $x$ 的等权叠加—— 而这些 $x$ 恰好构成一个等差数列 $x_0,\ x_0+r,\ x_0+2r,\dots$：

$$\ket{\Psi}=\frac{1}{\sqrt m}\sum_{j=0}^{m-1}\ket{x_0+jr},\qquad m\approx Q/r\tag{9.9.6}$$

周期已经刻进态里，但直接测量只会随机吐出一个 $x_0+jr$—— 随机起点 $x_0$ 把周期信息搅浑了（每轮重跑 $x_0$ 都不同）。老问题： 装进去的信息取不出来。老答案：干涉。这次的干涉机器是量子傅里叶变换。

第三级跳：QFT 把周期变成峰

量子傅里叶变换（QFT）是 DJ 里那排 $H$ 的豪华版——把「按位相位」升级为「连续相位」：

$$\mathrm{QFT}\ket{x}=\frac{1}{\sqrt Q}\sum_{y=0}^{Q-1} \ee^{2\pi\ii xy/Q}\ket{y}\tag{9.9.7}$$

（$H^{\otimes n}$ 的相位只有 $\pm1$；QFT 的相位在单位圆上取 $Q$ 个刻度。 它可用 $O(t^2)$ 个门实现——$H$ 加受控相位旋转，本节不展开线路。）

QFT 之后测量：为什么峰落在 Q/r 的整数倍上进阶~9 min展开

第 1 步：对周期态作 QFT。 把 $\ket{\Psi}$ 代入定义：

$$\mathrm{QFT}\ket{\Psi} =\frac{1}{\sqrt{mQ}}\sum_{y=0}^{Q-1} \left[\sum_{j=0}^{m-1}\ee^{2\pi\ii(x_0+jr)y/Q}\right]\ket{y}\tag{9.9.8}$$

第 2 步：把随机起点拆出去。 提出因子 $\ee^{2\pi\ii x_0y/Q}$—— 它只贡献相位，模方里消失：讨厌的 $x_0$ 就此退场。测得 $y$ 的概率

$$P(y)=\frac{1}{mQ}\left|\sum_{j=0}^{m-1}\ee^{2\pi\ii jry/Q}\right|^2\tag{9.9.9}$$

第 3 步：看几何级数何时相长。 括号里是公比 $\ee^{2\pi\ii ry/Q}$ 的等比数列。

• 若 $ry/Q$ 恰为整数，即 $y=k\,Q/r$：每项都是 1，和为 $m$， $P(y)=m/Q\approx1/r$——尖峰；
• 否则相位在单位圆上转圈，首尾相接近乎抵消，$P(y)\approx0$。

$r$ 个尖峰均匀立在 $y=0,\ \tfrac{Q}{r},\ \tfrac{2Q}{r},\dots$ 处,总概率约 1。 （$r$ 不整除 $Q$ 时峰略有宽度、位置取最近整数，结论不变——这正是要求 $Q\gg r^2$ 的原因：峰宽比峰距小得多。）

第 4 步：从读数反解 $r$。 测得某个 $y\approx kQ/r$，即

$$\frac{y}{Q}\approx\frac{k}{r}\tag{9.9.10}$$

左边是已知的读数,右边是待求的分数。用连分数展开找出分母不超过 $N$ 的 最佳有理逼近，即得 $r$ 的候选（$k$ 与 $r$ 不互素时得到 $r$ 的因子， 重跑一两次取最小公倍数即可）。代回第一级跳的 $\gcd$，分解完成。

微型示例核对（$N=15,a=7,r=4$，取 $Q=16$）：峰应在 $y=0,4,8,12$。 比如测得 $y=12$：$\tfrac{12}{16}=\tfrac34$，连分数给 $k/r=3/4$，$r=4$。✓

∎本节关键公式

• 归约链

  $$N=pq\ \Rightarrow\ r=\mathrm{ord}_N(a)\ \Rightarrow\ \gcd(a^{r/2}\pm1,N)$$

  分解 → 求周期 → 最大公约数；仅中间一步需要量子

• QFT

  $$\mathrm{QFT}\ket{x}=\frac{1}{\sqrt Q}\sum_y \ee^{2\pi\ii xy/Q}\ket{y}$$

  H^{⊗n} 的连续相位版；O(t²) 个门可实现

• 峰位置

  $$P(y)\ \text{峰值在}\ y\approx k\,Q/r$$

  周期叠加经 QFT 干涉；随机起点 x₀ 只留相位、不进概率

• 复杂度对比

  $$O(n^3)\ \text{vs}\ \exp[O(n^{1/3}(\log n)^{2/3})]$$

  多项式 vs 亚指数：对 RSA 是原理性威胁

?自测共 4 题

1. 1.

   N = 21，取 a = 2。函数 2^x mod 21 的周期 r 是多少？（逐次平方：2, 4, 8, 16, …）

   允许 0% 相对误差

   提交
2. 2.

   Shor 算法中，量子计算机真正负责的是哪一步？

   • 求模幂函数 a^x mod N 的周期 r
   • 计算最大公约数 gcd
   • 把 N 归约为周期问题的数论推导
   • 逐一试除所有可能的因子

   提交
3. 3.

   QFT 之前若直接测量第一寄存器（处于周期叠加 Σ∣x₀ + jr⟩），会得到什么？

   • 一个随机的 x₀ + jr，且 x₀ 每轮不同，无法从中稳定提取 r
   • 直接得到周期 r
   • 得到 Q/r 的某个整数倍
   • 得到 N 的一个因子

   提交
4. 4.

   关于 Shor 算法对密码学的影响，正确的是？（多选）

   多选题

   • RSA 与椭圆曲线等公钥体系受到原理性威胁
   • 「先囤后解」使得迁移必须在大型量子计算机出现之前完成
   • AES 等对称密码同样被指数级击穿
   • NIST 已标准化基于格等数学难题的抗量子算法

   提交

接下来

Shor 需要万亿级的门操作接连不出错，而真实的 qubit 娇气得很： 门误差百分之一都算优秀,放着不动也会悄悄漂移。 经典计算机靠冗余备份纠错,可是量子态不可克隆（9.5 节）、 一测就塌（9.1 节）——还怎么备份、怎么发现错误？ 下一节是本章压轴：量子纠错。它的答案漂亮得出人意料， 而且正是这章所有概念——纠缠、测量、稳定的关联——的一次总集合。