# 量子算法基础5：Grover算法

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

1. **[无结构搜索与两个核心算子](#unstructured-search-oracles)**——能写出无结构搜索问题的设定、预言机 $U_O = 2|x_0\rangle\langle x_0| - I$ 与扩散算子 $U_S = 2|s\rangle\langle s| - I$，并计算内积 $\langle x_0|s\rangle = \frac{1}{\sqrt{N}}$、写出 $|s\rangle$ 在目标方向与非目标方向上的分解。
2. **[不变子空间：降维分析工具](#invariant-subspace)**——能用定义判断 $\mathrm{span}\{x_0, x_1\}$ 是否为变换 $A$ 的不变子空间，解释它为何允许把 $N$ 维演化约化为二维矩阵问题，并说明基不正交时须先用 Gram–Schmidt 正交化。
3. **[二维不变子空间与 Grover 旋转矩阵](#grover-rotation-matrix)**——能证明 $\mathrm{span}\{|x_0\rangle, |s\rangle\}$ 是 $U_O$ 与 $U_S$ 的公共不变子空间、构造正交归一基 $\{|x_0\rangle, |x_0^\perp\rangle\}$，并推导 $G = U_S U_O$ 在该平面上是角度 $\pi - 2\theta$ 的旋转。
4. **[成功概率与最优迭代次数](#grover-success-probability)**——能推导 $T$ 次迭代后命中目标的精确概率 $P_T = \sin^2\big((2T+1)\theta\big)$，并证明取 $T \approx \frac{\pi}{4}\sqrt{N}$ 时成功率至少 $1 - \frac{1}{N}$。
5. **[去随机化：从随机重启到相干演化](#derandomization)**——能计算经典随机搜索的平均查询次数 $\Theta(N)$，并解释 Grover 如何用确定性的相干旋转取代"随机尝试 + 后选择"，把查询次数降到 $O(\sqrt{N})$。
6. **[为什么需要振幅放大](#why-amplitude-amplification)**——能解释量子线路只能直接实现幺正映射的原因、辅助寄存器如何把非幺正性转移到可后选择的标志比特上，并比较朴素重复的 $O(\frac{1}{p})$ 与振幅放大的 $O(\frac{1}{\sqrt{p}})$。
7. **[Grover 与振幅放大的关系](#grover-amplitude-connection)**——能把 Grover 搜索写成子程序 $U = H^{\otimes n}$、成功概率 $p = \frac{1}{N}$ 的振幅放大实例，并对 $N = 4$ 逐振幅验证一次迭代后必得目标条目。
8. **[振幅放大的理论](#amplitude-amplification-theory)**——能写出两个反射在基 $\{|g\rangle, |b\rangle\}$ 下的矩阵，证明迭代 $Q = U_S U_O$ 是角度 $-2\omega$（$\omega = \arcsin\sqrt{p}$）的旋转，并推导迭代次数 $n \approx \frac{\pi}{4\sqrt{p}}$ 与成功率下界 $1 - p$。

:::

(unstructured-search-oracles)=
## 1. 问题：无结构搜索与两个核心算子

我们要解决的是**无结构搜索 (unstructured search)** 问题：数据库中有 $N = 2^n$ 个条目，其中恰好有一个**目标条目 (marked item)** $x_0$；除了通过预言机查询之外，我们对数据库的结构一无所知。经典算法（即使允许随机性）平均需要 $\Theta(N)$ 次查询才能找到 $x_0$；Grover 算法只需要 $O(\sqrt{N})$ 次，而且这已被证明是最优的查询次数。

整个算法只用到两个酉算子。第一个是**预言机 (Oracle)**，它利用目标条目的信息：

$$ U_O = 2|x_0\rangle\langle x_0| - I. $$

按我们的约定，$U_O$ 保持 $|x_0\rangle$ 不变、把其余所有基矢变号。（更常见的约定是 $I - 2|x_0\rangle\langle x_0|$，即"翻转目标相位"；两者恰好相差一个整体符号 $-1$，由此得到的 Grover 迭代也只差一个整体符号，不影响任何测量概率。）

第二个算子是**扩散算子 (diffusion operator)**。定义均匀叠加态（$s$ 取 superposition 的首字母）

$$ |s\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle, $$

则

$$ U_S = H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|s\rangle\langle s| - I. $$

第二个等号的验证：由 $H^{\otimes n}|0\rangle = |s\rangle$（$n$ 个 Hadamard 把 $|0\rangle^{\otimes n}$ 叠加成所有基矢的均匀和）与 $H^{\otimes n}H^{\otimes n} = I$，

$$ H^{\otimes n}\left(2|0\rangle\langle 0|\right)H^{\otimes n} = 2\left(H^{\otimes n}|0\rangle\right)\left(\langle 0|H^{\otimes n}\right) = 2|s\rangle\langle s|, $$

而 $H^{\otimes n} I H^{\otimes n} = I$，两项相减即得。由定义直接计算关键内积（$|s\rangle$ 的分量全为实数，故 $\langle x_0|s\rangle = \langle s|x_0\rangle$）：

$$ \langle x_0|s\rangle = \frac{1}{\sqrt{N}}\sum_{x}\langle x_0|x\rangle = \frac{1}{\sqrt{N}}. $$

这个数是后文一切推导的出发点。

在分析算法之前，我们先把计算空间分解清楚。$N$ 个计算基矢可以分为目标态与其余基矢两部分：

$$ \sum_{x}|x\rangle = |x_0\rangle + \sum_{x \neq x_0}|x\rangle, $$

其中 $\{|x\rangle : x \neq x_0\}$ 张成 $|x_0\rangle$ 的正交补。把它代入 $|s\rangle$ 的定义（注意 $\sum_{x \neq x_0}|x\rangle$ 的范数是 $\sqrt{N-1}$），得到

$$ |s\rangle = \frac{1}{\sqrt{N}}|x_0\rangle + \sqrt{\frac{N-1}{N}}\,\frac{\sum_{x \neq x_0}|x\rangle}{\sqrt{N-1}}. $$

也就是说，均匀叠加态是"目标方向"与"非目标方向"的叠加，权重由 $\langle x_0|s\rangle = \frac{1}{\sqrt{N}}$ 决定。Grover 算法做的正是把权重从非目标方向转移到目标方向。算法本身一句话就能说完：从 $|s\rangle$ 出发，把迭代算子 $G = U_S U_O$ 重复大约 $\frac{\pi}{4}\sqrt{N}$ 次，然后测量。下面两节解释为什么。

(invariant-subspace)=
## 2. 分析工具：不变子空间

本节介绍**不变子空间 (invariant subspace)** 的概念，它是我们分析 Grover 算法的主要工具。

设 $\{x_0, x_1\}$ 为一组线性无关的矢量（这里是一般的矢量记号，与上文的目标条目无关）。若存在变换 $A$，它作用在 $x_0$ 和 $x_1$ 上之后，结果仍然落在 $\mathrm{span}\{x_0, x_1\}$ 之中，即运算封闭：

$$ Ax_0 = u_{00}\,x_0 + u_{10}\,x_1,\qquad Ax_1 = u_{01}\,x_0 + u_{11}\,x_1, $$

则 $\mathrm{span}\{x_0, x_1\}$ 称为 $A$ 的不变子空间。此时 $A$ 限制在这个子空间上是一个二维变换，可以写成矩阵形式（第 $j$ 列是第 $j$ 个基矢的像的系数）：

$$ A = \begin{pmatrix} u_{00} & u_{01}\\ u_{10} & u_{11} \end{pmatrix}. $$

不变子空间的价值在于降维：只要初态落在子空间内，我们就不必在完整的 $N$ 维空间中跟踪演化，而只需在二维平面上分析一个 $2\times 2$ 矩阵。对 Grover 算法而言，态将始终落在 $\mathrm{span}\{|x_0\rangle, |s\rangle\}$ 内，因此整个算法约化为平面上的旋转。

### 子空间性质

- **封闭性与线性组合**：子空间中矢量的任意线性组合仍在子空间中。因此，若 $A$ 保持该子空间，则 $A$ 的幂以及 $A$ 的多项式都保持该子空间——这对"反复迭代同一个算子"的算法尤为重要。
- **特征值与特征矢量**：变换限制在子空间上的特征值可以由这个 $2\times 2$ 矩阵的特征方程求得。特征值不依赖于基的选取（换基是相似变换，特征多项式不变），特征矢量本身则随基的变化而变化。
- **基不正交的情形**：若 $x_0$ 和 $x_1$ 线性无关但不正交，我们可以先用 Gram–Schmidt 正交化 (Gram–Schmidt orthogonalization) 构造一组**正交归一 (orthonormal)** 基，再写矩阵。对酉算子而言，只有在正交归一基下的矩阵才仍是酉矩阵，这样才能进一步把矩阵识别为旋转或反射。

## 3. Grover 迭代：二维平面上的旋转

一次 **Grover 迭代 (Grover iteration)** 定义为

$$ G = U_S U_O, $$

其中算符乘法按从右到左的顺序作用：**先**用预言机 $U_O$，**再**用扩散算子 $U_S$。算法从 $|s\rangle$ 出发，迭代 $T$ 次后测量。本节统一记 $\theta := \arcsin\frac{1}{\sqrt{N}}$。我们将证明：整个演化被限制在一个二维不变子空间内，且 $G$ 在该子空间上是旋转变换，每迭代一次把态向目标方向推进 $2\theta$。

(grover-rotation-matrix)=
### 3.1 公共不变子空间与旋转矩阵

**Lemma 1**. $\mathrm{span}\{|x_0\rangle, |s\rangle\}$ 是 $U_O$ 和 $U_S$ 共同的不变子空间；但 $|x_0\rangle$ 与 $|s\rangle$ 不正交。

**证明**。

- Part 1. 我们直接计算两个生成元在算子下的像。一方面，$U_O|x_0\rangle = 2|x_0\rangle\langle x_0|x_0\rangle - |x_0\rangle = 2|x_0\rangle - |x_0\rangle = |x_0\rangle$；另一方面，$U_S|s\rangle = 2|s\rangle\langle s|s\rangle - |s\rangle = 2|s\rangle - |s\rangle = |s\rangle$。两个生成元分别被 $U_O$、$U_S$ 映到自身。
- Part 2. 由 $\langle x_0|s\rangle = \frac{1}{\sqrt{N}}$，

$$ U_O|s\rangle = 2|x_0\rangle\langle x_0|s\rangle - |s\rangle = \frac{2}{\sqrt{N}}|x_0\rangle - |s\rangle \in \mathrm{span}\{|x_0\rangle, |s\rangle\}. $$

- Part 3. 同理，

$$ U_S|x_0\rangle = 2|s\rangle\langle s|x_0\rangle - |x_0\rangle = \frac{2}{\sqrt{N}}|s\rangle - |x_0\rangle \in \mathrm{span}\{|x_0\rangle, |s\rangle\}. $$

最后，$\langle x_0|s\rangle = \frac{1}{\sqrt{N}} \neq 0$，因此两个生成元不正交，$\{|x_0\rangle, |s\rangle\}$ 不是现成的正交基。Q.E.D.

**Lemma 2**. 定义

$$ |x_0^\perp\rangle = \frac{\sqrt{N}\,|s\rangle - |x_0\rangle}{\sqrt{N-1}}, $$

则 $\{|x_0\rangle, |x_0^\perp\rangle\}$ 是上述子空间的一组正交归一基。

**证明**。先验证正交性：

$$ \langle x_0|\left(\sqrt{N}|s\rangle - |x_0\rangle\right) = \sqrt{N}\cdot\frac{1}{\sqrt{N}} - 1 = 1 - 1 = 0. $$

再实际计算范数（利用 $\langle s|s\rangle = 1$、$\langle s|x_0\rangle = \langle x_0|s\rangle = \frac{1}{\sqrt{N}}$、$\langle x_0|x_0\rangle = 1$）：

$$ \left\|\sqrt{N}|s\rangle - |x_0\rangle\right\|^2 = N\langle s|s\rangle - \sqrt{N}\langle s|x_0\rangle - \sqrt{N}\langle x_0|s\rangle + \langle x_0|x_0\rangle = N - 1 - 1 + 1 = N - 1, $$

因此 $|x_0^\perp\rangle$ 的范数是 $\frac{\sqrt{N-1}}{\sqrt{N-1}} = 1$。由定义反解出

$$ |s\rangle = \frac{1}{\sqrt{N}}|x_0\rangle + \sqrt{\frac{N-1}{N}}\,|x_0^\perp\rangle, $$

所以 $\{|x_0\rangle, |x_0^\perp\rangle\}$ 与 $\{|x_0\rangle, |s\rangle\}$ 张成同一个二维子空间。Q.E.D.

为方便引用，我们把两个关键内积写在一起，并指出它们与 $\theta$ 的关系：

$$ \langle s|x_0\rangle = \frac{1}{\sqrt{N}} = \sin\theta,\qquad \langle s|x_0^\perp\rangle = \frac{\sqrt{N} - \frac{1}{\sqrt{N}}}{\sqrt{N-1}} = \sqrt{\frac{N-1}{N}} = \cos\theta, $$

其中第二个等号用了 $\sqrt{N} - \frac{1}{\sqrt{N}} = \frac{N-1}{\sqrt{N}}$。这正是 $\theta := \arcsin\frac{1}{\sqrt{N}}$ 的来历。

**Corollary 3**. $G = U_S U_O$（同理 $U_O U_S$）保持该子空间；并且在子空间的正交补 $\mathcal{H}^\perp = \{v : \langle x_0|v\rangle = \langle s|v\rangle = 0\}$（维数 $N-2$）上，$G$ 是恒等变换。

**证明**。$U_O$ 与 $U_S$ 各自保持该子空间（Lemma 1 的 Part 1–3），复合保持。对 $v \in \mathcal{H}^\perp$：$\langle x_0|v\rangle = 0$ 给出 $U_O|v\rangle = -|v\rangle$；$\langle s|v\rangle = 0$ 给出 $U_S|v\rangle = -|v\rangle$；于是 $G|v\rangle = U_S(U_O|v\rangle) = (-1)(-1)|v\rangle = |v\rangle$。Q.E.D.

这个推论说明：算法的初态 $|s\rangle$ 完全落在二维子空间内，且演化永远不会离开；其余 $N-2$ 个维度从头到尾不参与。因此整个算法的分析只需要一个 $2\times 2$ 矩阵。

**Theorem 4**. 在正交归一基 $\{|x_0\rangle, |x_0^\perp\rangle\}$ 下，

$$ G = U_S U_O = \begin{pmatrix} -\left(1-\frac{2}{N}\right) & -\frac{2\sqrt{N-1}}{N}\\ \frac{2\sqrt{N-1}}{N} & -\left(1-\frac{2}{N}\right) \end{pmatrix} = \begin{pmatrix} \cos(\pi - 2\theta) & -\sin(\pi - 2\theta)\\ \sin(\pi - 2\theta) & \cos(\pi - 2\theta) \end{pmatrix}, $$

其中 $\theta = \arcsin\frac{1}{\sqrt{N}}$。即 $G$ 是这个平面上角度为 $\pi - 2\theta$ 的**旋转 (rotation)**，等价地 $G = -R(-2\theta)$，其中 $R(\varphi) = \begin{pmatrix}\cos\varphi & -\sin\varphi\\ \sin\varphi & \cos\varphi\end{pmatrix}$ 是标准旋转矩阵。这一旋转图像与 Nielsen & Chuang (QCQI) 第 6.1.2 节（式 6.13–6.14）的分析一致。

**证明**。分三步。

第一步，计算 $U_S$ 在两个基矢上的作用。由 Lemma 2 的分解式以及 $\langle s|x_0\rangle = \frac{1}{\sqrt{N}}$、$\langle s|x_0^\perp\rangle = \sqrt{\frac{N-1}{N}}$：

$$ U_S|x_0\rangle = 2\langle s|x_0\rangle\,|s\rangle - |x_0\rangle = \frac{2}{\sqrt{N}}\left(\frac{1}{\sqrt{N}}|x_0\rangle + \sqrt{\frac{N-1}{N}}\,|x_0^\perp\rangle\right) - |x_0\rangle = \left(\frac{2}{N} - 1\right)|x_0\rangle + \frac{2\sqrt{N-1}}{N}|x_0^\perp\rangle, $$

$$ U_S|x_0^\perp\rangle = 2\sqrt{\frac{N-1}{N}}\left(\frac{1}{\sqrt{N}}|x_0\rangle + \sqrt{\frac{N-1}{N}}\,|x_0^\perp\rangle\right) - |x_0^\perp\rangle = \frac{2\sqrt{N-1}}{N}|x_0\rangle + \left(\frac{2(N-1)}{N} - 1\right)|x_0^\perp\rangle = \frac{2\sqrt{N-1}}{N}|x_0\rangle + \left(1 - \frac{2}{N}\right)|x_0^\perp\rangle, $$

其中最后一个等号用了 $\frac{2(N-1)}{N} - 1 = \frac{N-2}{N} = 1 - \frac{2}{N}$。

第二步，计算 $U_O$。Part 1 已证 $U_O|x_0\rangle = |x_0\rangle$；而 $\langle x_0|x_0^\perp\rangle = 0$（Lemma 2）给出

$$ U_O|x_0^\perp\rangle = 2|x_0\rangle\,\langle x_0|x_0^\perp\rangle - |x_0^\perp\rangle = -|x_0^\perp\rangle. $$

第三步，按"$U_O$ 先、$U_S$ 后"的顺序合成：

$$ G|x_0\rangle = U_S\left(U_O|x_0\rangle\right) = U_S|x_0\rangle = -\left(1 - \frac{2}{N}\right)|x_0\rangle + \frac{2\sqrt{N-1}}{N}|x_0^\perp\rangle, $$

$$ G|x_0^\perp\rangle = U_S\left(U_O|x_0^\perp\rangle\right) = U_S\left(-|x_0^\perp\rangle\right) = -\frac{2\sqrt{N-1}}{N}|x_0\rangle - \left(1 - \frac{2}{N}\right)|x_0^\perp\rangle. $$

把两个像的系数依次写成矩阵的第 1、2 列，即得定理中的第一个矩阵。

最后把它识别为旋转。直接验证

$$ \left(1-\frac{2}{N}\right)^2 + \left(\frac{2\sqrt{N-1}}{N}\right)^2 = 1 - \frac{4}{N} + \frac{4}{N^2} + \frac{4(N-1)}{N^2} = 1, $$

所以这四个元素确实具有旋转矩阵的形状。取 $\theta = \arcsin\frac{1}{\sqrt{N}}$（从而 $\cos\theta = \sqrt{\frac{N-1}{N}}$），由倍角公式

$$ \cos 2\theta = 1 - 2\sin^2\theta = 1 - \frac{2}{N},\qquad \sin 2\theta = 2\sin\theta\cos\theta = \frac{2\sqrt{N-1}}{N}. $$

于是矩阵可写成 $\begin{pmatrix}-\cos 2\theta & -\sin 2\theta\\ \sin 2\theta & -\cos 2\theta\end{pmatrix}$。它既等于 $R(\pi - 2\theta)$（因为 $\cos(\pi - 2\theta) = -\cos 2\theta$、$\sin(\pi - 2\theta) = \sin 2\theta$），也等于 $-R(-2\theta)$。Q.E.D.

从几何上看这个结果很自然：$U_O$ 是关于 $|x_0\rangle$ 轴的**反射 (reflection)**，$U_S$ 是关于 $|s\rangle$ 轴的反射，而两个反射的复合必为旋转，旋转角等于两轴夹角的两倍。两轴夹角 $\varphi$ 满足 $\cos\varphi = \langle x_0|s\rangle = \frac{1}{\sqrt{N}}$，即 $\varphi = \frac{\pi}{2} - \theta$，故旋转角为 $2\varphi = \pi - 2\theta$，与矩阵结果完全一致。

(grover-success-probability)=
### 3.2 成功概率与最优迭代次数

**Theorem 5**. 从 $|s\rangle$ 出发迭代 $T$ 次后，测得 $x_0$ 的概率**精确**等于

$$ P_T = \sin^2\left((2T+1)\theta\right),\qquad \theta = \arcsin\frac{1}{\sqrt{N}}. $$

**证明**。记 $|\psi(\alpha)\rangle := \sin\alpha\,|x_0\rangle + \cos\alpha\,|x_0^\perp\rangle$；由 Lemma 2，初态 $|s\rangle = |\psi(\theta)\rangle$。用 Theorem 4 的矩阵（即 $G = -R(-2\theta)$）作用于坐标 $(\sin\alpha, \cos\alpha)^T$：

- 第一分量为 $-\cos 2\theta\sin\alpha - \sin 2\theta\cos\alpha = -\sin(\alpha + 2\theta)$；
- 第二分量为 $\sin 2\theta\sin\alpha - \cos 2\theta\cos\alpha = -\cos(\alpha + 2\theta)$。

（两行分别用了和角公式 $\sin(a+b) = \sin a\cos b + \cos a\sin b$ 与 $\cos(a+b) = \cos a\cos b - \sin a\sin b$。）因此

$$ G|\psi(\alpha)\rangle = -|\psi(\alpha + 2\theta)\rangle: $$

每迭代一次，角度推进 $2\theta$，代价是一个全局相位 $-1$；由于算法的态始终位于该二维子空间内，这个符号在测量概率中完全不可观测。迭代 $T$ 次即得

$$ G^T|s\rangle = (-1)^T\left[\sin\left((2T+1)\theta\right)|x_0\rangle + \cos\left((2T+1)\theta\right)|x_0^\perp\rangle\right], $$

目标振幅为 $(-1)^T\sin((2T+1)\theta)$，概率为 $\sin^2((2T+1)\theta)$。Q.E.D.

我们也可以按坐标直接展开，这能看清楚"大 $N$ 近似"的来源。由 $G^T = (-1)^T R(-2T\theta)$ 与 $|s\rangle = \frac{1}{\sqrt{N}}|x_0\rangle + \sqrt{\frac{N-1}{N}}|x_0^\perp\rangle$：

$$ \langle x_0|G^T|s\rangle = (-1)^T\left[\frac{1}{\sqrt{N}}\cos 2T\theta + \sqrt{\frac{N-1}{N}}\sin 2T\theta\right] = (-1)^T\sin\left((2T+1)\theta\right), $$

其中第二个等号就是和角公式 $\sin(\theta + 2T\theta) = \sin\theta\cos 2T\theta + \cos\theta\sin 2T\theta$。当 $N \gg 1$ 时，$\sqrt{\frac{N-1}{N}} \approx 1$ 且 $\frac{1}{\sqrt{N}} \approx 0$，于是

$$ \sin\left((2T+1)\theta\right) \approx \sin(2T\theta), $$

这正是"$\sqrt{N-1} \gg 1$，因此振幅 $\sim \sin(2T\theta)$"这一近似的严格含义。另一个极端是小角度情形：当 $(2T+1)\theta \ll 1$ 时，$\sin((2T+1)\theta) \approx (2T+1)\theta \approx \frac{2T+1}{\sqrt{N}}$，即最初的若干次迭代中目标振幅近似**线性**增长，每迭代一次增加约 $\frac{2}{\sqrt{N}}$。

**Corollary 6**. 取

$$ T = \frac{\pi}{4\theta} - \frac{1}{2} \approx \frac{\pi}{4}\sqrt{N} $$

（$\theta$ 小时后者成立；实际取最接近的整数），则测得 $x_0$ 的概率至少为 $1 - \frac{1}{N}$。因此 Grover 算法用 $O(\sqrt{N})$ 次预言机查询找到目标条目。

**证明**。要最大化 $\sin^2((2T+1)\theta)$，应取 $(2T+1)\theta$ 尽可能接近 $\frac{\pi}{2}$，解出 $T = \frac{\pi/2 - \theta}{2\theta} = \frac{\pi}{4\theta} - \frac{1}{2}$；再由小角度近似 $\theta = \arcsin\frac{1}{\sqrt{N}} \approx \frac{1}{\sqrt{N}}$ 得 $T \approx \frac{\pi}{4}\sqrt{N}$。由于 $T$ 只能取整数、而 $(2T+1)\theta$ 随 $T$ 变化的步长是 $2\theta$，取最接近的整数保证 $|(2T+1)\theta - \frac{\pi}{2}| \le \theta$，于是

$$ P_T = \sin^2\left((2T+1)\theta\right) \ge \sin^2\left(\frac{\pi}{2} - \theta\right) = \cos^2\theta = 1 - \frac{1}{N}. $$

Q.E.D.

## 4. 从 Grover 到振幅放大

(derandomization)=
### 4.1 去随机化：从随机重启到相干演化

经典的随机搜索是这样工作的：每次独立地、均匀随机地查询一个条目，单次命中目标 $x_0$ 的概率为 $p = \frac{1}{N}$；未命中就丢弃结果、随机重启。由几何分布，平均需要 $\frac{1}{p} = \Theta(N)$ 次查询才能成功。这类算法的本质是"随机尝试 + **后选择 (post-selection)**"：把成功的希望寄托在随机性上。

Grover 算法可以看作对这个过程的**去随机化 (derandomization)**：我们把"随机重启"替换为相干的酉演化。量子态不再以概率 $p$ "落在"目标上，而是以振幅 $\frac{1}{\sqrt{N}}$ 叠加在目标方向上；每一步 Grover 迭代都在同一个二维子空间内、确定性地把态向目标方向旋转 $2\theta$。演化过程中没有任何随机选择——随机性被确定性的干涉所取代，查询次数从 $O(\frac{1}{p})$ 降到 $O(\frac{1}{\sqrt{p}})$。

(why-amplitude-amplification)=
### 4.2 为什么需要振幅放大

量子线路中的每个操作都必须是酉的（可逆的），而许多我们想实现的映射并不是酉的。以量子线性方程组求解器（如 HHL 类算法）为例：给定矩阵 $A$ 与输入态 $|b\rangle$，我们想制备

$$ |x\rangle \propto A^{-1}|b\rangle, $$

也就是实现线性映射 $|b\rangle \mapsto A^{-1}|b\rangle$。然而 $A^{-1}$ 通常不是幺正的：若 $A^{-1}$ 幺正，则它的逆 $A$ 也幺正（幺正算子的逆仍是幺算子），等价于 $A^\dagger A = I$；一般矩阵并不满足这一条件。因此我们不能把 $A^{-1}$ 直接做成一个量子门。

实现"非幺正映射"的标准办法是引入辅助寄存器，把非幺正性转移到一个可以后选择的标志比特上：

$$ U_{A^{-1}}|b\rangle|0\rangle = \sqrt{p}\,|x\rangle|0\rangle + \sqrt{1-p}\,|\mathrm{garbage}\rangle|1\rangle, $$

其中 $|x\rangle$ 与 $|\mathrm{garbage}\rangle$ 都是归一化态，整个 $U_{A^{-1}}$ 是酉的。测量第二个寄存器：若得到 $|0\rangle$（概率为 $p$），第一个寄存器恰好坍缩到我们想要的 $|x\rangle$，算法成功；若得到 $|1\rangle$，得到的是垃圾态，只能整体重来。**朴素策略下，我们平均需要重复 $O(\frac{1}{p})$ 次测量才能获得正确的结果。**

**振幅放大 (amplitude amplification)** 把 $O(\frac{1}{p})$ 降为 $O(\frac{1}{\sqrt{p}})$。这就是我们需要它的原因：任何"以概率 $p$ 成功的量子子过程"都可以被二次加速。

(grover-amplitude-connection)=
### 4.3 Grover 与振幅放大的关系

我们可以把 Grover 搜索写成上述框架：把一层 Hadamard 变换视为子程序 $U = H^{\otimes n}$，它把 $|0\rangle$ 制备成均匀叠加 $|s\rangle$；把"成功"定义为结果落在目标方向上，即好态取 $|x_0\rangle$。于是单次运行的成功概率为

$$ p = |\langle x_0|U|0\rangle|^2 = |\langle x_0|s\rangle|^2 = \frac{1}{N}. $$

朴素做法是"制备—测量"重复 $O(\frac{1}{p}) = O(N)$ 次；振幅放大把它降到 $O(\frac{1}{\sqrt{p}}) = O(\sqrt{N})$ 次，与第 3 节 Corollary 6 的 $T \approx \frac{\pi}{4}\sqrt{N}$ 一致。

作为具体例子，取 $N = 4$：

$$ |s\rangle = \frac{1}{\sqrt{4}}\left(|0\rangle + |1\rangle + |2\rangle + |3\rangle\right),\qquad |x_0\rangle = |1\rangle,\qquad |x_0^\perp\rangle = \frac{1}{\sqrt{3}}\left(|0\rangle + |2\rangle + |3\rangle\right). $$

此时 $\theta = \arcsin\frac{1}{2} = 30^\circ$，一次迭代后 $(2T+1)\theta = 90^\circ$，成功率恰为 $1$。我们也可以把振幅逐步算出来验证。初始四个振幅均为 $\frac{1}{2}$；$U_O$（保持目标、翻转其余）给出

$$ \left(-\tfrac{1}{2},\ +\tfrac{1}{2},\ -\tfrac{1}{2},\ -\tfrac{1}{2}\right); $$

接着 $U_S = 2|s\rangle\langle s| - I$ 把每个振幅 $a_x$ 映为 $2\bar{a} - a_x$，其中 $\bar{a} = \frac{1}{N}\sum_x a_x = -\frac{1}{4}$ 是振幅的平均值（这就是"关于平均值的翻转"）：

$$ 2\bar{a} - a_x \implies \left(0,\ -1,\ 0,\ 0\right). $$

一次迭代后态为 $-|1\rangle$（多出的负号是全局相位），测量必得目标条目。

(amplitude-amplification-theory)=
### 4.4 振幅放大的理论

**Proposition 1**. 设酉算子 $U$ 满足

$$ U|0\rangle|0\rangle = |\psi\rangle = \sqrt{p}\,|\mathrm{good}\rangle|0\rangle + \sqrt{1-p}\,|\mathrm{bad}\rangle|1\rangle,\qquad 0 < p \le 1, $$

其中 $|\mathrm{good}\rangle$ 与 $|\mathrm{bad}\rangle$ 都归一化，第二个寄存器是标志比特。那么存在一个只调用 $U$ 与 $U^\dagger$ 共 $O(\frac{1}{\sqrt{p}})$ 次的算法，以至少 $\max(p, 1-p) \ge \frac{1}{2}$ 的概率制备出 $|\mathrm{good}\rangle$；把该算法重复 $O(\log\frac{1}{\delta})$ 次，成功概率可以提升到 $1 - \delta$。下面的 Lemma 2、Lemma 3、Theorem 4 给出构造与证明。

**注意**：振幅放大实现的映射是 $|0\rangle|0\rangle \mapsto |\mathrm{good}\rangle|0\rangle$，而不是 $|\psi\rangle \mapsto |\mathrm{good}\rangle|0\rangle$。它是一个以 $U$ 为子过程的过程：把 $U$ 嵌入一个更大的算法中，共调用 $O(\frac{1}{\sqrt{p}})$ 次，从而制备出 $|\mathrm{good}\rangle$。

构造需要两个反射。第一个是关于 $|\psi\rangle$ 的反射

$$ U_S = 2|\psi\rangle\langle\psi| - I = U\left(2|0,0\rangle\langle 0,0| - I\right)U^\dagger, $$

右端的等式说明：只要能实现 $U$ 与 $U^\dagger$，就能实现 $U_S$。第二个是标志 Oracle，它翻转好态的相位：

$$ U_O = I - 2\,\Pi_{\mathrm{good}}, $$

其中 $\Pi_{\mathrm{good}}$ 是向好子空间的投影（在二维情形 $\Pi_{\mathrm{good}} = |\mathrm{good}\rangle|0\rangle\langle 0|\langle\mathrm{good}|$）。它与 Grover 部分的 $U_O = 2|x_0\rangle\langle x_0| - I$ 恰好相差一个整体符号；两种约定给出的迭代互为相反数，只差全局相位，不影响任何结论。**振幅放大的迭代**取为 $Q = U_S U_O$：先用 $U_O$，再用 $U_S$，与 Grover 迭代结构相同。为书写简便，记

$$ |g\rangle := |\mathrm{good}\rangle|0\rangle,\qquad |b\rangle := |\mathrm{bad}\rangle|1\rangle,\qquad \omega := \arcsin\sqrt{p}, $$

则 $|\psi\rangle = \sqrt{p}\,|g\rangle + \sqrt{1-p}\,|b\rangle = \sin\omega\,|g\rangle + \cos\omega\,|b\rangle$，且 $\langle\psi|g\rangle = \sqrt{p}$、$\langle\psi|b\rangle = \sqrt{1-p}$。

**Lemma 2**. $\mathrm{span}\{|g\rangle, |b\rangle\}$ 是 $U_S$ 与 $U_O$ 的公共不变子空间，并且在正交归一基 $\{|g\rangle, |b\rangle\}$ 下

$$ U_O = \begin{pmatrix}-1 & 0\\ 0 & 1\end{pmatrix},\qquad U_S = \begin{pmatrix}2p - 1 & 2\sqrt{p(1-p)}\\ 2\sqrt{p(1-p)} & 1 - 2p\end{pmatrix}. $$

**证明**。$U_O$ 翻转好态、保持坏态：$U_O|g\rangle = -|g\rangle$、$U_O|b\rangle = |b\rangle$，这给出第一个矩阵。对 $U_S$，我们把两个基矢的像实际算出来：

$$ U_S|g\rangle = 2\langle\psi|g\rangle\,|\psi\rangle - |g\rangle = 2\sqrt{p}\left(\sqrt{p}\,|g\rangle + \sqrt{1-p}\,|b\rangle\right) - |g\rangle = (2p-1)|g\rangle + 2\sqrt{p(1-p)}\,|b\rangle, $$

$$ U_S|b\rangle = 2\langle\psi|b\rangle\,|\psi\rangle - |b\rangle = 2\sqrt{1-p}\left(\sqrt{p}\,|g\rangle + \sqrt{1-p}\,|b\rangle\right) - |b\rangle = 2\sqrt{p(1-p)}\,|g\rangle + (1-2p)\,|b\rangle, $$

其中第二个式子 $|b\rangle$ 的系数用了 $2(1-p) - 1 = 1 - 2p$。两个像都落在子空间内，把系数写成列即得第二个矩阵。Q.E.D.

**Lemma 3**. $Q = U_S U_O$ 在基 $\{|g\rangle, |b\rangle\}$ 下是旋转矩阵

$$ Q = \begin{pmatrix}1 - 2p & 2\sqrt{p(1-p)}\\ -2\sqrt{p(1-p)} & 1 - 2p\end{pmatrix} = \begin{pmatrix}\cos 2\omega & \sin 2\omega\\ -\sin 2\omega & \cos 2\omega\end{pmatrix} = R(-2\omega),\qquad \omega = \arcsin\sqrt{p}. $$

**证明**。做矩阵乘法（右乘 $\mathrm{diag}(-1, 1)$ 相当于把第一列取反）：

$$ Q = U_S U_O = \begin{pmatrix}2p-1 & 2\sqrt{p(1-p)}\\ 2\sqrt{p(1-p)} & 1-2p\end{pmatrix}\begin{pmatrix}-1 & 0\\ 0 & 1\end{pmatrix} = \begin{pmatrix}1-2p & 2\sqrt{p(1-p)}\\ -2\sqrt{p(1-p)} & 1-2p\end{pmatrix}. $$

验证它具有旋转的形状：$(1-2p)^2 + 4p(1-p) = 1 - 4p + 4p^2 + 4p - 4p^2 = 1$。取 $\omega = \arcsin\sqrt{p}$，由倍角公式

$$ \cos 2\omega = 1 - 2\sin^2\omega = 1 - 2p,\qquad \sin 2\omega = 2\sin\omega\cos\omega = 2\sqrt{p(1-p)}, $$

所以 $Q$ 是角度为 $-2\omega$ 的旋转（旋转的幅度是 $2\omega$）。当 $p \ll 1$ 时，由 $\arcsin x = x + O(x^3)$ 得 $\omega \approx \sqrt{p}$，即每次迭代把态旋转约 $2\sqrt{p}$——这就是"小 $p$ 时角度 $\sim \sqrt{p}$"这一近似的来源。Q.E.D.

**Theorem 4**. 取

$$ n = \frac{\pi}{4\omega} - \frac{1}{2} \approx \frac{\pi}{4\sqrt{p}} $$

（实际取最接近的整数），则 $Q^n|\psi\rangle$ 落在 $|g\rangle$ 上的概率至少为 $1 - p$。因此，$O(\frac{1}{\sqrt{p}})$ 次 $U$ 调用就能以高概率制备出 $|\mathrm{good}\rangle$。

**证明**。与 Grover 部分 Theorem 5 的计算完全相同。记 $|\varphi(\alpha)\rangle := \sin\alpha\,|g\rangle + \cos\alpha\,|b\rangle$，初态 $|\psi\rangle = |\varphi(\omega)\rangle$。由 $Q = R(-2\omega)$，

$$ R(-2\omega)\begin{pmatrix}\sin\alpha\\ \cos\alpha\end{pmatrix} = \begin{pmatrix}\cos 2\omega\sin\alpha + \sin 2\omega\cos\alpha\\ -\sin 2\omega\sin\alpha + \cos 2\omega\cos\alpha\end{pmatrix} = \begin{pmatrix}\sin(\alpha + 2\omega)\\ \cos(\alpha + 2\omega)\end{pmatrix}, $$

即 $Q|\varphi(\alpha)\rangle = |\varphi(\alpha + 2\omega)\rangle$，每迭代一次角度推进 $2\omega$。迭代 $n$ 次：

$$ Q^n|\psi\rangle = |\varphi\left((2n+1)\omega\right)\rangle = \sin\left((2n+1)\omega\right)|g\rangle + \cos\left((2n+1)\omega\right)|b\rangle, $$

成功概率为 $\sin^2((2n+1)\omega)$。要让它接近 $1$，取 $(2n+1)\omega \approx \frac{\pi}{2}$，解出 $n = \frac{\pi/2 - \omega}{2\omega} = \frac{\pi}{4\omega} - \frac{1}{2} \approx \frac{\pi}{4\sqrt{p}}$（用 $\omega \approx \sqrt{p}$）。把 $n$ 四舍五入到最近的整数带来的偏差至多是 $\omega$，因此成功概率至少为 $\cos^2\omega = 1 - \sin^2\omega = 1 - p$。每次迭代需要一次 $U$ 与一次 $U^\dagger$（用来合成 $U_S$），故总的调用次数是 $O(\frac{1}{\sqrt{p}})$。Q.E.D.

对 Grover 搜索套用本节结果：$p = \frac{1}{N}$，$\omega = \arcsin\frac{1}{\sqrt{N}} = \theta$，迭代次数 $\approx \frac{\pi}{4}\sqrt{N}$——与 Corollary 6 完全一致。

## 练习题

**练习 1【无结构搜索与两个核心算子】**（→ [第 1 节](#unstructured-search-oracles)）

1. 写出 $n=3$（$N=8$）时均匀叠加态 $|s\rangle$ 的表达式与预言机 $U_O = 2|x_0\rangle\langle x_0| - I$ 的定义，计算 $\langle x_0|s\rangle$ 与 $\sqrt{\frac{N-1}{N}}$，并把 $|s\rangle$ 写成 $\frac{1}{\sqrt{N}}|x_0\rangle + \sqrt{\frac{N-1}{N}}\,|x_0^\perp\rangle$ 的形式。
2. 说明约定 $U_O = 2|x_0\rangle\langle x_0| - I$ 与"翻转目标相位"约定 $I - 2|x_0\rangle\langle x_0|$ 相差整体符号 $-1$，并解释为什么由此得到的两个 Grover 迭代只差全局相位、不影响任何测量概率。
3. 验证 $U_S = H^{\otimes n}(2|0\rangle\langle 0| - I)H^{\otimes n} = 2|s\rangle\langle s| - I$，并证明 $U_O$ 与 $U_S$ 都是幺正算子。

> 提示：幺正性可对归一化态 $|\psi\rangle$ 直接展开 $\left(2|\psi\rangle\langle\psi| - I\right)^2 = I$。

**练习 2【不变子空间：降维分析工具】**（→ [第 2 节](#invariant-subspace)）

1. 设 $x_0, x_1$ 线性无关，$Ax_0 = 2x_0 + x_1$，$Ax_1 = x_0 - x_1$。写出 $A$ 限制在 $\mathrm{span}\{x_0, x_1\}$ 上的矩阵，并说明该子空间是 $A$ 的不变子空间。
2. 证明：若子空间 $\mathcal{H}$ 在 $A$ 下不变，则 $\mathcal{H}$ 在 $A$ 的任意次幂以及任意多项式 $f(A)$ 下也不变；并解释这一性质对"反复迭代同一个算子 $G$"的算法为什么重要。

> 提示：先对 $k$ 归纳证明 $A^k x \in \mathcal{H}$，再利用子空间对线性组合的封闭性。

**练习 3【二维不变子空间与 Grover 旋转矩阵】**（→ [3.1 节](#grover-rotation-matrix)）

1. 证明 $U_O|x_0\rangle = |x_0\rangle$、$U_O|x_0^\perp\rangle = -|x_0^\perp\rangle$，并写出 $U_O$ 在正交归一基 $\{|x_0\rangle, |x_0^\perp\rangle\}$ 下的矩阵。
2. 取 $N = 4$：算出 $\theta$，逐一算出 Theorem 4 中旋转矩阵的四个元素，并验证矩阵每一列的范数都是 1。
3. 用"两个反射的复合是旋转、旋转角等于两反射轴夹角的两倍"解释 $U_S U_O$ 的旋转角为何是 $\pi - 2\theta$，并判断 $U_O U_S$ 的旋转角与旋转方向。

> 提示：两反射轴 $|x_0\rangle$ 与 $|s\rangle$ 的夹角 $\varphi$ 满足 $\cos\varphi = \langle x_0|s\rangle = \frac{1}{\sqrt{N}}$。

**练习 4【成功概率与最优迭代次数】**（→ [3.2 节](#grover-success-probability)）

1. 取 $N = 1024$：用 $\theta \approx \frac{1}{\sqrt{N}}$ 估算最优迭代次数 $T \approx \frac{\pi}{4}\sqrt{N}$（取最接近的整数），并写出此时成功概率的理论下界 $1 - \frac{1}{N}$ 的数值。
2. 证明：若把迭代次数加倍（取 $T' = 2T$，其中 $T$ 使 $(2T+1)\theta \approx \frac{\pi}{2}$），成功概率反而回落到约 $\frac{1}{N}$；据此说明为什么运行 Grover 算法之前需要（近似）知道 $N$。

> 提示：$(4T+1)\theta = 2(2T+1)\theta - \theta \approx \pi - \theta$，再用 $\sin(\pi - \theta) = \sin\theta$。

**练习 5【去随机化：从随机重启到相干演化】**（→ [4.1 节](#derandomization)）

1. 经典随机搜索单次命中概率 $p = \frac{1}{N}$。说明平均需要 $\frac{1}{p} = N$ 次查询，并计算 $N = 10^6$ 时经典查询次数与 Grover 的 $\frac{\pi}{4}\sqrt{N}$ 次之比。
2. 解释"随机尝试 + 后选择"与 Grover 的相干演化在随机性出现位置上的本质区别，并说明量子态以振幅 $\frac{1}{\sqrt{N}}$（而非概率 $\frac{1}{N}$）叠加在目标方向上，为什么使得干涉式加速成为可能。

> 提示：对比"未命中就丢弃结果、随机重启"与"演化过程中没有任何随机选择"两种机制。

**练习 6【为什么需要振幅放大】**（→ [4.2 节](#why-amplitude-amplification)）

1. 写出用辅助寄存器与后选择实现非幺正映射的标准形式 $U_{A^{-1}}|b\rangle|0\rangle = \sqrt{p}\,|x\rangle|0\rangle + \sqrt{1-p}\,|\mathrm{garbage}\rangle|1\rangle$，并计算 $p = 0.01$ 时朴素重复的平均测量次数与振幅放大所需调用次数的对比。
2. 证明：若 $A^{-1}$ 是幺正的，则 $A$ 也是幺正的；据此说明映射 $|b\rangle \mapsto A^{-1}|b\rangle$ 一般不能直接做成一个量子门。

> 提示：用 $(A^{-1})^\dagger = (A^\dagger)^{-1}$ 与幺正刻画 $U^\dagger = U^{-1}$。

**练习 7【Grover 与振幅放大的关系】**（→ [4.3 节](#grover-amplitude-connection)）

1. 指出把 Grover 搜索写成振幅放大框架时的子程序 $U$、好态 $|\mathrm{good}\rangle$ 与成功概率 $p$，并验证 $p = |\langle x_0|U|0\rangle|^2 = \frac{1}{N}$。
2. 证明 $U_S = 2|s\rangle\langle s| - I$ 把任意态的振幅 $a_x$ 映为 $2\bar{a} - a_x$（$\bar{a} = \frac{1}{N}\sum_x a_x$，即"关于平均值的翻转"）；再对 $N=4$、$x_0=1$ 从初始振幅 $(\frac12,\frac12,\frac12,\frac12)$ 出发完成一次完整迭代，验证结果为 $\pm|1\rangle$。

> 提示：$\langle s|\psi\rangle = \sqrt{N}\,\bar{a}$，因为 $|s\rangle$ 的每个分量都是 $\frac{1}{\sqrt{N}}$。

**练习 8【振幅放大的理论】**（→ [4.4 节](#amplitude-amplification-theory)）

1. 在基 $\{|g\rangle, |b\rangle\}$ 下写出 $U_O = I - 2\Pi_{\mathrm{good}}$ 与 $U_S = 2|\psi\rangle\langle\psi| - I$ 的矩阵，取 $p = \frac14$ 算出 $Q = U_S U_O$ 的四个元素，并指出 $Q$ 是哪个角度的旋转。
2. 仿照第 3 节 Theorem 5 的推导证明 $Q|\varphi(\alpha)\rangle = |\varphi(\alpha + 2\omega)\rangle$（$\omega = \arcsin\sqrt{p}$），并由此推出取 $n \approx \frac{\pi}{4\sqrt{p}}$ 时成功概率至少 $1 - p$；说明每次迭代为何需要一次 $U$ 与一次 $U^\dagger$。

> 提示：把 $R(-2\omega)$ 作用于坐标 $(\sin\alpha, \cos\alpha)^T$，用和角公式合并。