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

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

**课程目标：**

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

:::{admonition} 本课知识点
:class: tip

1. **[振幅放大框架](#amplitude-amplification-framework)**——能写出 $P_g$、$S_f$、$S_\psi$ 与迭代算符 $Q=-S_\psi S_f$ 的定义，并说明 $A$ 与"好"判据各取什么时回到 Grover 算法。
2. **[平面旋转几何与迭代公式](#plane-rotation-geometry)**——能在 $\{|g\rangle,|b\rangle\}$ 平面内推导 $Q^k|\psi\rangle$ 的振荡公式，并计算最优迭代次数 $k^\ast\approx\frac{\pi}{4\sqrt a}-\frac12$ 与成功率下界 $p_{k^\ast}\ge 1-a$。
3. **[通用二次加速](#generic-quadratic-speedup)**——能比较"生成-检验"式随机算法的经典尝试次数 $O(1/a)$ 与量子振幅放大的 $O(1/\sqrt a)$，并解释平方级加速为何对任意初态线路 $A$ 与任意好判据都成立。
4. **[振幅估计](#amplitude-estimation)**——能构造振幅估计（把 QPE 套在 $Q$ 上）并写出读出公式 $\hat a=\sin^2(\pi\tilde y/M_{\text{QPE}})$，推导它以 $O(1/\varepsilon)$ 次查询达到经典蒙特卡洛 $O(1/\varepsilon^2)$ 才能企及的精度。
5. **[查询复杂度下界](#query-lower-bound)**——能用多项式方法证明非结构化搜索的 $\Omega(\sqrt N)$ 查询下界：写出"成功概率是次数 $\le 2k$ 的多项式"、对称化与马尔可夫兄弟不等式三个步骤。

:::

(amplitude-amplification-framework)=
## 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).
$$

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

(plane-rotation-geometry)=
## 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$，做"定点击穿"——不再展开。）

(generic-quadratic-speedup)=
## 3. 应用一例：二次加速是通用的

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

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

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

(amplitude-estimation)=
## 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 章的特征值过滤）大量使用"无振幅估计"的变体来降低常数与线路深度，但原理仍是这一节。

(query-lower-bound)=
## 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【振幅放大框架】**（→ [第 1 节](#amplitude-amplification-framework)）

1. 基础：写出 $P_g$、$S_f = I - 2P_g$、$S_\psi = I - 2|\psi\rangle\langle\psi|$ 与迭代算符 $Q = -S_\psi S_f$（用 $A$、$S_0 = I - 2|0\rangle\langle 0|$、$P_g$ 表示）的定义，并指出 Grover 算法对应这组框架的哪一组特例（$A$ 与"好"判据各取什么）。
2. 进阶：设 $a=0$（初态没有好分量）与 $a=1$（初态全是好分量），直接从 $S_f$、$S_\psi$ 的定义计算 $Q|\psi\rangle$，说明这两种极端情形下振幅放大为何无法（也无需）再提高成功率。

> 提示：分别把两种情形下 $S_f|\psi\rangle$ 与 $S_\psi|\psi\rangle$ 的取值代入 $Q$ 的定义；注意整体相位不影响测量。

**练习 2【平面旋转几何与迭代公式】**（→ [第 2 节](#plane-rotation-geometry)）

1. 基础：设 $a = 1/4$（$\theta = \pi/6$）。写出 $p_k$ 的表达式并求 $k^\ast$；验证 $p_{k^\ast} \ge 1 - a$。
2. 进阶：验证 $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$。

**练习 3【通用二次加速】**（→ [第 3 节](#generic-quadratic-speedup)）

1. 基础：对好分量权重 $a = 10^{-4}$ 的"生成-检验"任务，分别给出经典重复采样与振幅放大所需的尝试/调用次数量级，并说出加速的倍数。
2. 进阶：把框架套到一个非搜索场景（如随机猜测 SAT 赋值并检验是否满足）：写出该场景中 $A$、好判据与 $a$ 各对应什么，并说明判据为何必须能实现为可逆的预言机线路。

> 提示：对照第 3 节的三个例子；判据线路要作为 $S_f$ 中的黑箱酉算子出现。

**练习 4【振幅估计】**（→ [第 4 节](#amplitude-estimation)）

1. 基础：写出振幅估计的读出公式 $\hat a = \sin^2(\pi\tilde y/M_{\text{QPE}})$，说明 $\tilde y$ 来自把 QPE 套在 $Q$ 上读出的本征相位 $\pm 2\theta$；对精度 $\varepsilon = 10^{-3}$，比较量子与经典蒙特卡洛的查询量级。
2. 进阶：振幅估计的精度传递：若 QPE 用 $m$ 个相位比特、相位读数误差 $\le 2\pi/2^m$，推导 $\hat a$ 的相对误差量级（注意 $\cos$ 在 $\pi/2$ 附近的行为——为什么在 $\theta$ 接近 $\pi/2$ 时反而更好？）。

> 提示：对 $\hat a = \sin^2\varphi$ 做一阶展开，误差放大因子为 $|\sin 2\theta|$，它在 $\theta \to \pi/2$ 时趋于 $0$。

**练习 5【查询复杂度下界】**（→ [第 5 节](#query-lower-bound)）

1. 基础：按顺序列出多项式方法证明的三个步骤及关键数值（$p(x)$ 的次数 $\le 2k$；对称化后 $P(0) \le \frac13$、$P(1) \ge \frac23$；$\max_{[0,N]}|P'| \le \frac{2d^2}{N}$），由 $\frac13 \le \frac{2(2k)^2}{N}$ 解出 $k$ 的下界，并对 $N = 10^6$ 算出具体数字。
2. 进阶：证明单标记搜索的接受概率多项式次数至多为 $2k$。

> 提示：对查询次数归纳，考虑 $\langle \psi_j | O_x^\dagger M O_x | \psi_j \rangle$ 型项中 $x$ 的幂次。