量子算法基础6：振幅放大与查询复杂度下界

前置阅读：Grover 算法（第 5 篇）。本篇把 Grover 的几何图像提炼成一般原理，并证明它是最优的。

课程目标：

  1. 把 Grover 迭代提炼为振幅放大 (Amplitude Amplification) 框架：任何"初始态中混有少量好分量"的场景都适用。

  2. 用几何语言（二维平面上的旋转）重新推导迭代公式，并精确计算最优迭代次数与成功概率。

  3. 学会把振幅放大与相位估计组合，得到振幅估计——量子对经典蒙特卡洛方法的二次加速。

  4. 证明非结构化搜索的 \(\Omega(\sqrt N)\) 查询下界（多项式方法），理解"Grover 型加速不可再改进"的含义。

1. 从 Grover 到一般框架

回顾 Grover 算法：\(N = 2^n\) 个候选中有 \(M\) 个"好"答案，我们要找到其中一个。Grover 选择"从均匀叠加开始、每轮查询一次预言机"。振幅放大把这套几何抽象出来：

设初态 \(|\psi\rangle = A|0\rangle^{\otimes n}\) 是任意易于制备的叠加态（\(A\) 是任意多项式规模的线路，Grover 取 \(A = H^{\otimes n}\)）。定义投影算符与两个"镜像"：

  • 好子空间投影：\(P_g = \sum_{x \in \text{好}} |x\rangle\langle x|\)；

  • 关于好子空间的反射（由预言机实现）：\(S_f = I - 2P_g\)，把好分量翻相位；

  • 关于初态的反射：\(S_\psi = I - 2|\psi\rangle\langle\psi|\)，由 \(-A S_0 A^\dagger\) 实现，其中 \(S_0 = I - 2|0\rangle\langle 0|\) 关于 \(|0\rangle\) 反射。

Grover 迭代算子定义为

\[ Q \;=\; -\,S_\psi\, S_f \;=\; -A\,(2|0\rangle\langle 0| - I)\,A^\dagger\,(2P_g - I). \]

"两次反射的复合是一个旋转"——这是群论里的经典结论，我们直接用它。

2. 几何推导：平面上的旋转

设 \(a = \langle\psi|P_g|\psi\rangle\) 是初态中好分量的权重（成功概率），令 \(\theta \in (0, \pi/2]\) 满足

\[ \sin\theta = \sqrt a, \qquad |\psi\rangle = \sin\theta\,|g\rangle + \cos\theta\,|b\rangle, \]

其中 \(|g\rangle = P_g|\psi\rangle/\sqrt a\) 是好分量的单位向量，\(|b\rangle\) 是坏分量方向。整个动力学被限制在由 \(\{|g\rangle, |b\rangle\}\) 张成的二维平面内。逐项核对两个反射的作用：

  • \(S_f\)：\(|g\rangle \mapsto -|g\rangle,\ |b\rangle \mapsto |b\rangle\)（关于 \(|b\rangle\) 轴的镜面反射）；

  • \(S_\psi\)：\(|\psi\rangle \mapsto -|\psi\rangle\)、且保持与 \(|\psi\rangle\) 正交的方向不变（关于 \(|\psi^\perp\rangle\) 轴的反射）。

几何课的结论：两个夹角为 \(\theta\) 的镜面反射之复合，是角度 \(2\theta\) 的旋转。因此

\[ Q^k |\psi\rangle = \sin\big((2k+1)\theta\big)\,|g\rangle + \cos\big((2k+1)\theta\big)\,|b\rangle . \]

一次查询让好分量的"幅角"从 \(\theta\) 走到 \(3\theta\)——前进 \(2\theta\)。要把幅角推到 \(\pi/2\)（纯好态），需要

\[ k \;\approx\; \frac{\pi/2 - \theta}{2\theta} \;=\; \frac{\pi}{4\theta} - \frac12 \;\approx\; \frac{\pi}{4\sqrt a} \qquad (\theta = \arcsin\sqrt a \approx \sqrt a,\ a \ll 1). \]

代入 Grover 设定 \(a = M/N\)：查询次数 \(O(\sqrt{N/M})\)，与第 5 篇的结论一致——但现在的推导对任意初态线路 \(A\) 与任意"好"判据都成立，而且给出了精确的振荡公式。

成功概率的精确表达式：\(k\) 次迭代后

\[ p_k = \sin^2\big((2k+1)\theta\big). \]

由于 \((2k+1)\theta\) 一般无法精确落在 \(\pi/2\)，\(p_k\) 会围绕 1 小幅振荡。取最接近 \((\pi/2-\theta)/(2\theta)\) 的整数 \(k^\ast\)，可证 \(| (2k^\ast+1)\theta - \pi/2 | \le \theta\)，于是

\[ p_{k^\ast} \ge \cos^2\theta = 1 - a \;\ge\; \frac34 \quad (a \le 1/4). \]

即最优迭代次数下成功率至少 \(1 - a\)；对 Grover 的 \(a = M/N \ll 1\)，成功率任意接近 1。（若必须精确成功，可以把 \(S_f\)、\(S_\psi\) 中的相位 \(-1\) 换成适当的一般相位 \(\phi\)，做"定点击穿"——不再展开。）

3. 应用一例：二次加速是通用的

振幅放大最实用的推论：任何"生成-检验"式的随机算法都能获得平方级量子加速。

  • 经典：反复制备 \(A|0\rangle\)、测量、检验好坏，期望 \(1/a\) 次尝试；

  • 量子：振幅放大只需 \(O(1/\sqrt a)\) 次 \(A\) 与预言机调用。

例子：把 \(A\) 取为"均匀随机猜测解"、预言机取为"验证解是否正确"，就回到 Grover；把 \(A\) 取为某个启发式采样线路，就得到对具体组合优化问题的量子加速；把"好坏"定义为业务指标的指示函数，就进入下一节的振幅估计。

4. 振幅估计：与相位估计合体

第 3 篇的相位估计 (QPE) 能把酉算子的本征相位读到 \(m\) 比特精度；而振幅放大算子 \(Q\) 的本征相位恰好携带 \(\theta\)（在二维平面里，转角 \(2\theta\) 的旋转的本征相位是 \(\pm 2\theta\)，与 \(\sin\theta\) 的关系是二次的）。把 QPE 套在 \(Q\) 上，就得到振幅估计 (Amplitude Estimation)：

\[ \hat a = \sin^2\!\left(\pi\, \frac{\tilde y}{M_{\text{QPE}}}\right), \]

其中 \(\tilde y\) 是 QPE 读出的相位估计。若用 \(m\) 个相位比特，则 \(\hat a\) 的误差为 \(O(2\pi/2^m)\) 量级——用 \(O(2^m)\) 次查询把 \(\sin\theta\) 估到 \(\varepsilon\) 精度：

\[ \text{量子：} O(1/\varepsilon) \text{ 次查询} \quad \text{vs} \quad \text{经典蒙特卡洛：} O(1/\varepsilon^2) \text{ 次采样}. \]

这就是"量子蒙特卡洛"二次加速的来源，在金融风险估计、求和与积分（第 6 章的线性方程组后处理里也会再次遇到它）中是标配 subroutine。顺带一提：现代容错算法（如第 6 章的特征值过滤）大量使用"无振幅估计"的变体来降低常数与线路深度，但原理仍是这一节。

5. 最优性：\(\Omega(\sqrt N)\) 下界的证明梗概

Grover 型加速还能更快吗？不能。我们给出多项式方法 (polynomial method) 的证明梗概，它只需一条经典不等式，很适合课堂。

设定。非结构化搜索：\(N\) 个候选、恰好一个标记项。预言机 \(O_x\) 由标记位置 \(x \in \{1,\ldots,N\}\) 编码（\(x\) 未标记时记 \(x=0\)）。设某量子算法总共查询预言机 \(k\) 次，成功（输出 \(x\)）概率记为 \(p(x)\)。

第一步：成功概率是低次多项式。跟踪密度矩阵对预言机条目的依赖可以发现：\(p(x)\) 是预言机输入变量的多项式，其次数至多 \(2k\)（每次查询给依赖关系增加一次幂，取迹不增加次数；对单标记搜索可收紧到 \(k\)，但 \(2k\) 已足够）。

第二步：对称化。由对称性可设算法对各标记位置一视同仁，于是只依赖"标记权重" \(w \in \{0,1,\ldots,N\}\)：\(p(x) = P(w)\)，\(P\) 是次数 \(\le 2k\) 的单变量多项式，且 \(0 \le P \le 1\)。有界错误要求

\[ P(0) \le \tfrac13 \ (\text{无标记时允许失败}), \qquad P(1) \ge \tfrac23 \ (\text{有标记时大概率成功}). \]

第三步：马尔可夫兄弟不等式收尾。区间 \([0, N]\) 上次数为 \(d\)、值域在 \([0,1]\) 的多项式，其导数满足

\[ \max_{[0,N]} |P'| \;\le\; \frac{2 d^2}{N}. \]

而由中值定理，\(P(1) - P(0) \ge 1/3\) 要求 \(\max |P'| \ge 1/3\)。代入 \(d = 2k\)：

\[ \frac13 \le \frac{2 (2k)^2}{N} \quad\Longrightarrow\quad k \;\ge\; \frac{1}{2\sqrt 6}\,\sqrt N . \]

任何算法都需要 \(\Omega(\sqrt N)\) 次查询——Grover 的 \(O(\sqrt N)\) 在常数意义内不可改进。（把成功阈值换成 \((1/2 \pm \varepsilon)\) 的一般形式同法可证。）注意下界只约束查询次数；若允许初态与 \(N\) 相关（知道答案的"先验线路"），另有混合论证处理，结论不变。

这个证明值得咀嚼的地方在于："多项式次数"是量子查询算法的宿命——它把"量子能多快"这样一个动力学问题，化归为"一个有界多项式能多陡"的纯代数问题。第 5 章 QSP 的视角正是反其道而行：干脆把整个算法设计成一个多项式。

本课总结

  • 振幅放大 \(Q = -S_\psi S_f\) 把 Grover 推广到任意初态线路 \(A\) 与任意好判据；几何上是二维平面内每查询一次转 \(2\theta\)。

  • 最优迭代次数 \(k^\ast \approx \frac{\pi}{4\sqrt a} - \frac12\)，成功率至少 \(1 - a\)；对搜索问题即 \(O(\sqrt{N/M})\)。

  • 与相位估计组合得到振幅估计：期望值估计从蒙特卡洛的 \(O(1/\varepsilon^2)\) 降到 \(O(1/\varepsilon)\)。

  • 多项式方法 + 马尔可夫不等式证明 \(\Omega(\sqrt N)\) 下界：Grover 型二次加速已是极限。

习题

  1. 验证 \(S_f\) 与 \(S_\psi\) 确实把平面 \(\mathrm{span}\{|g\rangle,|b\rangle\}\) 映到自身，并用 \(2\times 2\) 矩阵（以 \(\{|g\rangle,|b\rangle\}\) 为基）显式写出 \(Q\)，确认它是转角 \(2\theta\) 的旋转矩阵（提示：矩阵含 \(\sin 2\theta\) 与 \(\cos 2\theta\)）。

  2. 设 \(a = 1/4\)（\(\theta = \pi/6\)）。写出 \(p_k\) 的表达式并求 \(k^\ast\)；验证 \(p_{k^\ast} \ge 1 - a\)。

  3. 振幅估计的精度传递：若 QPE 用 \(m\) 个相位比特、相位读数误差 \(\le 2\pi/2^m\)，推导 \(\hat a\) 的相对误差量级（注意 \(\cos\) 在 \(\pi/2\) 附近的行为——为什么在 \(\theta\) 接近 \(\pi/2\) 时反而更好？）。

  4. 证明单标记搜索的接受概率多项式次数至多为 \(2k\)（提示：对查询次数归纳，考虑 \(\langle \psi_j | O_x^\dagger M O_x | \psi_j \rangle\) 型项中 \(x\) 的幂次）。