振幅放大

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

本词条要点：

1. 把 Grover 迭代提炼为**振幅放大 (Amplitude Amplification)** 框架：任何”初始态中混有少量好分量”的场景都适用。
2. 用几何语言（二维平面上的旋转）重新推导迭代公式，并精确计算最优迭代次数与成功概率。
3. 学会把振幅放大与相位估计组合，得到振幅估计——量子对经典蒙特卡洛方法的二次加速。
4. 证明非结构化搜索的 $\Omega (\sqrt{N})$ 查询下界（多项式方法），理解”Grover 型加速不可再改进”的含义。

1. 从 Grover 到一般框架

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

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

• 好子空间投影：$P_g={\sum }_{x\in \text{好}}|x⟩⟨x|$；
• 关于好子空间的反射（由预言机实现）：$S_f=I-2P_g$，把好分量翻相位；
• 关于初态的反射：$S_{\psi }=I-2|\psi ⟩⟨\psi |$，由 $-A{S}_0{A}^{†}$ 实现，其中 $S_0=I-2|0⟩⟨0|$ 关于 $|0⟩$ 反射。

Grover 迭代算子定义为

$$Q=-S_{\psi }{S}_f=-A(2|0⟩⟨0|-I)A^{†}(2P_g-I).$$

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

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

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

$$\sin \theta =\sqrt{a},|\psi ⟩=\sin \theta |g⟩+\cos \theta |b⟩,$$

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

• $S_f$：$|g⟩\mapsto -|g⟩,|b⟩\mapsto |b⟩$（关于 $|b⟩$ 轴的镜面反射）；
• $S_{\psi }$：$|\psi ⟩\mapsto -|\psi ⟩$、且保持与 $|\psi ⟩$ 正交的方向不变（关于 $|{\psi }^{\perp }⟩$ 轴的反射）。

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

$$Q^k|\psi ⟩=\sin ((2k+1)\theta )|g⟩+\cos ((2k+1)\theta )|b⟩.$$

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

$$k\approx \frac{\pi /2-\theta }{2\theta }=\frac{\pi }{4\theta }-\frac{1}{2}\approx \frac{\pi }{4\sqrt{a}}(\theta =\arcsin \sqrt{a}\approx \sqrt{a},a\ll 1).$$

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

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

$$p_k={\sin }^2((2k+1)\theta ).$$

由于 $(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 \frac{3}{4}(a\le 1/4).$$

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

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

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

• 经典：反复制备 $A|0⟩$、测量、检验好坏，期望 $1/a$ 次尝试；
• 量子：振幅放大只需 $O(1/\sqrt{a})$ 次 $A$ 与预言机调用。

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

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

的相位估计 (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$ 估到 $\epsilon$ 精度：

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

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

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

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

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

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

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

$$P(0)\le \frac{1}{3}(\text{无标记时允许失败}),P(1)\ge \frac{2}{3}(\text{有标记时大概率成功}).$$

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

$$\underset{[0,N]}{\max }|P^{\prime }|\le \frac{2d^2}{N}.$$

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

$$\frac{1}{3}\le \frac{2(2k{)}^2}{N}⟹k\ge \frac{1}{2\sqrt{6}}\sqrt{N}.$$

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

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

本词条总结

• 振幅放大 $Q=-S_{\psi }{S}_f$ 把 Grover 推广到任意初态线路 $A$ 与任意好判据；几何上是二维平面内每查询一次转 $2\theta$。
• 最优迭代次数 $k^{\ast }\approx \frac{\pi }{4\sqrt{a}}-\frac{1}{2}$，成功率至少 $1-a$；对搜索问题即 $O(\sqrt{N/M})$。
• 与相位估计组合得到振幅估计：期望值估计从蒙特卡洛的 $O(1/{\epsilon }^2)$ 降到 $O(1/\epsilon )$。
• 多项式方法 + 马尔可夫不等式证明 $\Omega (\sqrt{N})$ 下界：Grover 型二次加速已是极限。

习题

1. 验证 $S_f$ 与 $S_{\psi }$ 确实把平面 $\mathrm{span}\{|g⟩,|b⟩\}$ 映到自身，并用 $2\times 2$ 矩阵（以 $\{|g⟩,|b⟩\}$ 为基）显式写出 $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$（提示：对查询次数归纳，考虑 $⟨{\psi }_j|O_x^{†}M{O}_x|{\psi }_j⟩$ 型项中 $x$ 的幂次）。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch03-algo-basics/amplitude-amplification
• 内容遵循 CC BY-NC-SA 4.0 许可协议