量子算法基础2：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\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) 的概念，它是我们分析 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\) 个基矢的像的系数）：

\[\begin{split} A = \begin{pmatrix} u_{00} & u_{01}\\ u_{10} & u_{11} \end{pmatrix}. \end{split}\]

不变子空间的价值在于降维：只要初态落在子空间内，我们就不必在完整的 \(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) 基，再写矩阵。对酉算子而言，只有在正交归一基下的矩阵才仍是酉矩阵，这样才能进一步把矩阵识别为旋转或反射。

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\)。

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\}\) 下，

\[\begin{split} 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}, \end{split}\]

其中 \(\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\) 先、\(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\)，与矩阵结果完全一致。

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

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

第一分量为 \(-\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.

从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\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与振幅放大的关系¶

我们可以把 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})\) 次，与上一节 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\)（多出的负号是全局相位），测量必得目标条目。

理论¶

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\}\) 下

\[\begin{split} 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}. \end{split}\]

证明。\(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\}\) 下是旋转矩阵

\[\begin{split} 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}. \end{split}\]

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

\[\begin{split} 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}. \end{split}\]

验证它具有旋转的形状：\((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\)。

\[\begin{split} 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}, \end{split}\]

即 \(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 完全一致。