2. 量子算法: Deutsch-Jozsa / Grover / Shor
TL;DR
叠加 + 纠缠给了量子计算机新能力，但测量会坍缩——所以算法必须设计成"把正确答案的概率放大"。这一章讲三个代表性算法，从教学（Deutsch-Jozsa）到实用（Grover）到威胁经典密码（Shor），理解"快在哪、为什么快、代价是什么"。
读完应能：
- 理解量子并行与"读一次"的张力（为什么算法要巧妙放大概率）。
- 讲清 Deutsch-Jozsa：用 1 次查询判定函数性质，经典要 2ⁿ⁻¹+1 次。
- 讲清 Grover：无序搜索 √N，知道为什么是平方级不是指数级。
- 讲清 Shor：把因式分解归约到"找周期"（量子优势所在），知道为什么威胁 RSA。
- 知道这些算法分别的复杂度对比与适用边界。
一、量子并行与"读一次"的张力
1.1 量子并行
对 $n$ 个 qubit 做 H 变换到全叠加：
$$|\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |x\rangle$$
一次酉计算 $U_f$ 同时作用于所有 $2^n$ 个基态 → 指数级并行。
1.2 但测量只给一个结果
U_f 叠加了 2^n 个结果, 但:
测量 → 坍缩到 1 个, 概率 = |振幅|²
→ 直接读 = 随机采样, 不是答案!
结论：量子算法的全部艺术在于——用干涉（相位）把答案振幅放大、错误振幅抵消，让测量更可能给出答案。经典算法读结果，量子算法"培养概率"。
二、Deutsch-Jozsa 算法
2.1 问题
给定黑盒函数 $f: {0,1}^n \to {0,1}$，承诺它要么常量（全 0 或全 1），要么平衡（一半 0 一半 1）。判断是哪种。
- 经典：最坏要 $2^{n-1} + 1$ 次查询。
- 量子：1 次查询。
2.2 直觉
利用"相位编码"：让函数作为相位翻转作用在叠加态上，不同函数类型产生不同干涉 → 测量结果区分。
关键点（简化）：
对叠加态 |+...⟩ 应用 U_f
常量函数 → 相位整体不翻 → 测量得到 |0...0⟩
平衡函数 → 相位部分翻 → 干涉掉 |0...0⟩ 分量 → 测不到 |0...0⟩
- 这就是"量子干涉"：相位差导致振幅增强/抵消。
- 它不直接给出"f 是什么"，而是给出"f 是不是常量"——用 1 次查询完成分类。
2.3 为什么意义重大
教学意义 > 实用意义：第一个严格证明量子比经典有指数优势的算法（虽然问题本身人为）。它展示的"叠加 → 相位干涉 → 测量"模式是所有量子算法的骨架。
三、Grover 搜索
3.1 问题
在 $N = 2^n$ 个元素的无序集合里找目标（假设恰一个解）。经典线性搜索 $O(N)$；Grover 给出 $O(\sqrt N)$。
3.2 直觉（振幅放大）
1. 全叠加: |ψ⟩ = (1/√N) Σ|x⟩ (每个解概率 1/N, 太小)
2. 反复迭代"振幅放大":
① 标记目标: 翻转目标态的相位 (它"变负")
② 绕均值反转: 把振幅往均值对称翻转 → 目标振幅被放大
3. 迭代 ~√N 次后, 目标态振幅 → ~1 → 测量大概率命中
每次迭代把目标的振幅放大，同时其他态被压缩——这就是Grover 迭代（反射 + 反射）。
3.3 复杂度
- 查询数：$O(\sqrt N)$（经典 $O(N)$）→ 平方级加速，不是指数。
- 最优性（Bennett 1997）：量子搜索的查询下界就是 $\Omega(\sqrt N)$——Grover 已是最优。
note
Grover 是"平方加速"的代表。它不像 Shor 给指数加速，但通用——任何 $O(N)$ 搜索问题都能用 Grover 加速到 $O(\sqrt N)$。密码学意义：穷举密钥 $2^k$ → $2^{k/2}$（所以 AES 密钥要加倍长，见附录 Y2Q）。
四、Shor 算法（威胁 RSA）
4.1 问题
大整数因式分解。经典最好（数域筛法）亚指数 $O(\exp(c (\log N)^{1/3}))$——RSA 就建立在"难分解"上。Shor 给出多项式时间。
4.2 核心：把分解归约到"找周期"
Shor 的两步：
Step 1 (经典): 因式分解问题 → 找"阶"(order/周期) 问题
- 随机选 a, 求最小的 r 使 a^r ≡ 1 (mod N) ← 找周期
- 用 gcd(a^{r/2} ± 1, N) 得到因子
Step 2 (量子): 用量子傅里叶变换 (QFT) 找周期 r
- 这是唯一"量子有指数优势"的一步
4.3 为什么量子快
**量子傅里叶变换（QFT）**在 $O(\log^2 N)$ 步内找到函数的周期——经典找周期需要指数步。
经典找周期: 试 r=1,2,3,... (指数)
QFT 找周期: 一次变换, 频率峰 → 周期
- 周期 $r$ 在频域里对应一个峰——QFT 用干涉把"周期频率"放大，一次测量读出。
- 这正是 Deutsch-Jozsa 的"相位干涉"思路的规模化。
4.4 对 RSA 的威胁
- RSA 的安全 = "分解 N 难"。Shor 多项式分解 → RSA / DH / ECC 全破（只要 Shor 在足够大的数上能跑）。
- 这推动 后量子密码（PQC）：基于格/哈希/多变量的抗量子方案（NIST 已定 Kyber/Dilithium 等）。
- 但 Shor 需要大量物理 qubit + 完美纠错（见下一章），短期不现实。
warning
别混：Shor 威胁的是 RSA/ECC/DH（基于分解/离散对数），不威胁 AES 对称加密（AES 受 Grover 影响，密钥加倍即可）。量子安全的核心问题是"公钥密码要换"，不是"所有密码都要换"。
五、复杂度对比表
| 算法 | 问题 | 经典 | 量子 | 加速 |
|---|---|---|---|---|
| Deutsch-Jozsa | 常量 vs 平衡 | $2^{n-1}+1$ | 1 | 指数 |
| Grover | 无序搜索 | $O(N)$ | $O(\sqrt N)$ | 平方 |
| Shor | 大数分解 | 亚指数 | 多项式 | 指数 |
| Shor | 离散对数 | 亚指数 | 多项式 | 指数 |
| 量子模拟 | 量子系统 | 指数 | 多项式 | 指数（实用价值最大的方向） |
note
量子模拟（Feynman 1982 的原始动机）可能比 Shor 更早产生实际价值：模拟分子/材料/化学（量子系统天然指数难，经典算不动）——量子计算机用自己模拟自己，是"天然匹配"。
六、算法骨架统一
所有量子算法共享的骨架：
1. 叠加: H⊗n 造全叠加 (指数并行)
2. 干涉: U_f + 相位旋转 (放大目标 / 抵消噪声)
3. 变换: QFT 或其他 (把"想知道的"转到可测的基)
4. 测量: 高概率读出答案
理解了这个骨架，读任何量子算法 paper 都不会迷路。
七、结束 + 速查表
tip
一页快速唤回：
- 量子并行：$n$ qubit 叠加 $2^n$ 态；但测量只读一个 → 算法要放大概率。
- 干涉：相位差 → 振幅增强/抵消（所有算法的核心）。
- Deutsch-Jozsa：1 次查询判常量/平衡（经典 $2^{n-1}+1$），教学意义。
- Grover：无序搜索 $\sqrt N$（平方加速，最优）；密码穷举 $2^k → 2^{k/2}$。
- Shor：分解 → 找周期 → QFT 一次读周期（指数加速）；威胁 RSA/ECC/DH，不威胁 AES。
- PQC：后量子密码（Kyber/Dilithium）为 Shor 时代的准备。
- 量子模拟：最可能先实用（分子/材料）。
- 骨架：叠加 → 干涉 → 变换 → 测量。