第四章 核心量子算法

第 4 章 · 核心量子算法

章节摘要：本章是全册的主峰：沿难度阶梯依次登顶四个算法——用一次查询分辨函数性质的 Deutsch-Jozsa、平方级加速搜索的 Grover、指数级加速分解的 Shor、面向近期硬件的变分算法 VQE 与 QAOA。我们不满足于"知道有这么个算法"：每个算法都给出线路、关键步演算和复杂度账单，全部演算只用第 2、3 章建立的工具。读完本章，"量子加速"对你就不再是一个形容词，而是可以逐行验证的振幅账目。

学习目标

1. 推导 Deutsch-Jozsa 算法，解释常数与平衡函数各自的振幅去向；
2. 说出 Grover 算法 oracle 与扩散变换的作用，对任意 N 估算所需迭代次数（约 π√N/4）；
3. 完整手算 Shor 算法在 N=15、a=7 时的经典前处理与后处理，讲清量子部分承担哪一步；
4. 解释 VQE 的"量子制备、经典优化"分工，以及 QAOA 与 Grover 的结构亲缘；
5. 对一个新问题，判断它是否属于"已知量子加速"的适用结构。

核心概念速览

一句金句：量子算法不是"把所有答案都算一遍"，而是精心安排一场让错误答案自我湮灭的干涉仪式。

子章节导航

• 4.1 Deutsch-Jozsa：量子加速的第一课：最小的指数加速演示，全程无纠缠，把 3.4 节的相位回踢用满。
• 4.2 Grover 算法：振幅放大的平方级加速：oracle 反转 + 扩散变换的几何图像，N=10000 只需约百次迭代的账本。
• 4.3 Shor 算法：从周期寻找到因数分解：分解如何转化为周期查找，量子部分与经典部分的分工，N=15 全流程手算。
• 4.4 VQE 与 QAOA：近期设备上的变分算法：噪声时代的务实路线，量子制备试探态、经典优化参数。

子章节之间的逻辑关系

[4.1 DJ] 教学算法：看清干涉加速的最小样本
   → [4.2 Grover] 迭代化：把单次干涉重复成振幅放大
   → [4.3 Shor] 登峰：傅里叶变换读取周期，数学转化最深
   → [4.4 VQE/QAOA] 落地：在噪声预算内收割现有加速
​

四节的深度递增、工程务实性也递增：4.1 纯教学，4.2 有独立应用价值，4.3 承载密码学叙事，4.4 是当下设备上真正跑得动的路线。

前置知识与后续延伸

本章完全建立在第 2、3 章之上：单比特门矩阵（2.5）、CNOT 与贝尔态（3.1/3.2）、三段式骨架（3.4）。4.3 节用到一点初等数论（最大公约数、连分数），现场给结论并示范用法，不要求数论背景。读完本章，第 5 章回答"这些算法在什么硬件上跑、跑不动时怎么办"，第 6 章回答"跑得动之后对哪些行业意味着什么"。

本章自测清单

1. DJ 算法里辅助位为什么要固定在 |−⟩？如果用 |+⟩ 会发生什么？（答案：相位回踢失效，oracle 只改变辅助位，输入寄存器不含 f 的信息，测量无区分度。）
2. N=16、目标唯一时，Grover 理论迭代几轮？（答案：约 π/4·4 ≈ 3.14 → 取 3 轮，正文 N=16 图给出两轮已达 96%。）
3. Shor 算法里哪一步是量子必须出场的？把这一步换成经典可行吗？
4. VQE 为什么保证收敛结果不低于真基态能量？这个保证的边界条件是什么？
5. 四个算法各用什么当"干涉引擎"？（答案：H 层、扩散变换、QFT、经典优化器调参下的层叠相位。）

四个算法的学习路径建议

按难度与独立性排：4.1 必须精读到每一步振幅（它是相位回踢的字典）；4.2 重点吃透几何图像与迭代次数公式，线路细节可粗；4.3 先通读两次转化再看量子部分，数论链条断了会全程发懵；4.4 与第 5 章硬件对照着读，理解"为什么当下跑它"。常见误区预警：把 DJ 的指数加速外推成"量子全面超越"（错误，承诺问题特殊）；把 Grover 的平方加速说成"指数级"（错误，方向相反的两种加速别混）；把 Shor 的威胁说成"今天就能破 RSA"（错误，4.3 节与 7.1 节的两笔账都过不了）。