Grover 算法

Grover’s algorithm

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

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

$U_O=2|x_0⟩⟨x_0|-I.$

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

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

$|s⟩=\frac{1}{\sqrt{N}}{\sum }_x|x⟩,$

则

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

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

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

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

$⟨x_0|s⟩=\frac{1}{\sqrt{N}}{\sum }_x⟨x_0|x⟩=\frac{1}{\sqrt{N}}.$

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

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

${\sum }_x|x⟩=|x_0⟩+{\sum }_{x\ne x_0}|x⟩,$

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

$|s⟩=\frac{1}{\sqrt{N}}|x_0⟩+\sqrt{\frac{N-1}{N}}\frac{{\sum }_{x\ne x_0}|x⟩}{\sqrt{N-1}}.$

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

子空间

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

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

$A{x}_0=u_{00}{x}_0+u_{10}{x}_1,A{x}_1=u_{01}{x}_0+u_{11}{x}_1,$

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

$A=\left(\begin{array}{cc}{u}_{00}& u_{01}\\ u_{10}& u_{11}\end{array}\right).$

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

子空间性质

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

Grover算法

理论

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

$G=U_S{U}_O,$

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

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

证明。

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

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

• Part 3. 同理，

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

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

Lemma 2. 定义

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

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

证明。先验证正交性：

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

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

${\Vert \sqrt{N}|s⟩-|x_0⟩\Vert }^2=N⟨s|s⟩-\sqrt{N}⟨s|x_0⟩-\sqrt{N}⟨x_0|s⟩+⟨x_0|x_0⟩=N-1-1+1=N-1,$

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

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

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

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

$⟨s|x_0⟩=\frac{1}{\sqrt{N}}=\sin \theta ,⟨s|x_0^{\perp }⟩=\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:⟨x_0|v⟩=⟨s|v⟩=0\}$（维数 $N-2$）上，$G$ 是恒等变换。

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

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

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

$G=U_S{U}_O=\left(\begin{array}{cc}-\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{array}\right)=\left(\begin{array}{cc}\cos (\pi -2\theta )& -\sin (\pi -2\theta )\\ \sin (\pi -2\theta )& \cos (\pi -2\theta )\end{array}\right),$

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

证明。分三步。

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

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

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

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

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

$U_O|x_0^{\perp }⟩=2|x_0⟩⟨x_0|x_0^{\perp }⟩-|x_0^{\perp }⟩=-|x_0^{\perp }⟩.$

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

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

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

把两个像的系数依次写成矩阵的第 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},\sin 2\theta =2\sin \theta \cos \theta =\frac{2\sqrt{N-1}}{N}.$

于是矩阵可写成 $\left(\begin{array}{cc}-\cos 2\theta & -\sin 2\theta \\ \sin 2\theta & -\cos 2\theta \end{array}\right)$。它既等于 $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⟩$ 轴的反射 (reflection)，$U_S$ 是关于 $|s⟩$ 轴的反射，而两个反射的复合必为旋转，旋转角等于两轴夹角的两倍。两轴夹角 $\phi$ 满足 $\cos \phi =⟨x_0|s⟩=\frac{1}{\sqrt{N}}$，即 $\phi =\frac{\pi }{2}-\theta$，故旋转角为 $2\phi =\pi -2\theta$，与矩阵结果完全一致。

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

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

证明。记 $|\psi (\alpha )⟩:=\sin \alpha |x_0⟩+\cos \alpha |x_0^{\perp }⟩$；由 Lemma 2，初态 $|s⟩=|\psi (\theta )⟩$。用 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 )⟩=-|\psi (\alpha +2\theta )⟩:$

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

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

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

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

$⟨x_0|G^T|s⟩=(-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.

---

从Grover到振幅放大

Derandomization

经典的随机搜索是这样工作的：每次独立地、均匀随机地查询一个条目，单次命中目标 $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?

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

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

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

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

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

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

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

Grover与振幅放大的关系

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

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

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

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

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

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

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

接着 $U_S=2|s⟩⟨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⟹\left(0,-1,0,0\right).$

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

理论

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

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

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

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

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

$U_S=2|\psi ⟩⟨\psi |-I=U\left(2|0,0⟩⟨0,0|-I\right)U^{†},$

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

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

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

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

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

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

$U_O=\left(\begin{array}{cc}-1& 0\\ 0& 1\end{array}\right),U_S=\left(\begin{array}{cc}2p-1& 2\sqrt{p(1-p)}\\ 2\sqrt{p(1-p)}& 1-2p\end{array}\right).$

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

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

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

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

Lemma 3. $Q=U_S{U}_O$ 在基 $\{|g⟩,|b⟩\}$ 下是旋转矩阵

$Q=\left(\begin{array}{cc}1-2p& 2\sqrt{p(1-p)}\\ -2\sqrt{p(1-p)}& 1-2p\end{array}\right)=\left(\begin{array}{cc}\cos 2\omega & \sin 2\omega \\ -\sin 2\omega & \cos 2\omega \end{array}\right)=R(-2\omega ),\omega =\arcsin \sqrt{p}.$

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

$Q=U_S{U}_O=\left(\begin{array}{cc}2p-1& 2\sqrt{p(1-p)}\\ 2\sqrt{p(1-p)}& 1-2p\end{array}\right)\left(\begin{array}{cc}-1& 0\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}1-2p& 2\sqrt{p(1-p)}\\ -2\sqrt{p(1-p)}& 1-2p\end{array}\right).$

验证它具有旋转的形状：$(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,\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 ⟩$ 落在 $|g⟩$ 上的概率至少为 $1-p$。因此，$O(\frac{1}{\sqrt{p}})$ 次 $U$ 调用就能以高概率制备出 $|\mathrm{good}⟩$。

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

$R(-2\omega )\left(\begin{array}{c}\sin \alpha \\ \cos \alpha \end{array}\right)=\left(\begin{array}{c}\cos 2\omega \sin \alpha +\sin 2\omega \cos \alpha \\ -\sin 2\omega \sin \alpha +\cos 2\omega \cos \alpha \end{array}\right)=\left(\begin{array}{c}\sin (\alpha +2\omega )\\ \cos (\alpha +2\omega )\end{array}\right),$

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

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

成功概率为 ${\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^{†}$（用来合成 $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 完全一致。

---

参考资料

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