Grover 搜索算法

Deutsch–Jozsa 赢在一个人工问题上。这一节解决一个人人都懂的问题——大海捞针， 而且这次的对手是货真价实的经典下界。

问题开门：N 个抽屉，一把钥匙

$N=2^n$ 个抽屉，编号 $0$ 到 $N-1$，恰有一个（记 $w$）藏着钥匙。 你有一个黑盒 $f$：给它编号 $x$，它答 $f(x)=1$ 当且仅当 $x=w$。 经典策略只有翻抽屉：平均 $N/2$ 次，最坏 $N$ 次，没有任何捷径—— $f$ 毫无结构可利用（这不是排序好的电话簿，是乱序的）。

量子版 oracle 照搬上一节的相位反冲（辅助位 $\ket{-}$ 从此隐去不写）：

$$O\ket{x}=(-1)^{f(x)}\ket{x} \qquad\Longleftrightarrow\qquad O=I-2\ket{w}\bra{w}\tag{9.8.1}$$

它只干一件事：给目标分支翻个负号。

一次干涉为什么不够了

试试照抄 DJ 的三板斧：$H$ 排制备均匀叠加 $\ket{s}=\frac{1}{\sqrt N}\sum_x\ket{x}$，调一次 oracle，再干涉。 麻烦在于：oracle 只把 $2^n$ 个振幅中的一个翻了号， 这点扰动对整体分布的影响是 $O(1/\sqrt N)$ 量级——一次干涉洗不出来， 直接测量命中概率仍约 $1/N$。DJ 的问题里「所有函数值合谋」形成鲜明的全局信号； 搜索问题的信号却细如发丝。出路：别指望一击必中，让小优势滚雪球。 每一轮把指向目标的振幅拧大一点点，拧 $\sqrt N$ 轮。 这台「振幅放大器」由两面镜子构成。

几何图像：两面镜子 = 一个旋转

全部动作发生在一个二维平面里——由目标态 $\ket{w}$ 和均匀叠加 $\ket{s}$ 张成的平面。取平面内与 $\ket{w}$ 垂直的单位矢量 $\ket{r}=\frac{1}{\sqrt{N-1}}\sum_{x\ne w}\ket{x}$（「其余抽屉的均匀叠加」），则

$$\ket{s}=\cos\theta\,\ket{r}+\sin\theta\,\ket{w}, \qquad \sin\theta=\braket{w}{s}=\frac{1}{\sqrt N}\tag{9.8.2}$$

初态 $\ket{s}$ 距「地面」$\ket{r}$ 只有一个小角 $\theta\approx1/\sqrt N$。Grover 迭代是两步：

1. oracle $O$：翻转 $\ket{w}$ 分量的符号 = 关于 $\ket{r}$ 的反射（镜子一）；
2. 扩散算子 $D=2\ket{s}\bra{s}-I$：关于 $\ket{s}$ 的反射（镜子二）。

两次反射合成一次 2θ 旋转基础~7 min展开

第 1 步：确认 $O$ 是反射。 平面内任意态 $\ket{\psi}=\cos\phi\ket{r}+\sin\phi\ket{w}$：

$$O\ket{\psi}=\cos\phi\ket{r}-\sin\phi\ket{w}\tag{9.8.3}$$

角度 $\phi\mapsto-\phi$：正是以 $\ket{r}$ 为镜面的反射。

第 2 步：确认 $D$ 是反射。 $D=2\ket{s}\bra{s}-I$ 满足 $D\ket{s}=\ket{s}$（镜面上的矢量不动）、对垂直于 $\ket{s}$ 的分量取反—— 以 $\ket{s}$（角度 $\theta$）为镜面的反射：$\phi\mapsto2\theta-\phi$。

第 3 步：合成。 先 $O$ 后 $D$：

$$\phi\ \xrightarrow{\ O\ }\ -\phi\ \xrightarrow{\ D\ }\ 2\theta+\phi\tag{9.8.4}$$

两次反射 = 一次旋转，转角 $2\theta$，方向朝 $\ket{w}$。 这是平面几何的老定理 （两镜夹角 $\theta$，反射两次即旋转 $2\theta$），在 Hilbert 空间原样上演。

第 4 步：迭代 $k$ 轮。 初态角 $\theta$，每轮加 $2\theta$：

$$\phi_k=(2k+1)\theta,\qquad P_{\text{命中}}(k)=\sin^2\big[(2k+1)\theta\big]\tag{9.8.5}$$

要 $\phi_k\approx\pi/2$（正对目标），解出

$$k_{\text{opt}}\approx\frac{\pi/2-\theta}{2\theta}\approx\frac{\pi}{4}\sqrt N\tag{9.8.6}$$

（末式用了大 $N$ 时 $\theta\approx\sin\theta=1/\sqrt N$。） $O(\sqrt N)$ 次查询、每轮只多两排 $H$ 和一点相位操作——平方加速到手。

手算 N = 4：一轮迭代，百发百中

$N=4$（两个 qubit），设目标 $w=10$。此时 $\sin\theta=\tfrac12$，$\theta=30^\circ$—— 角度不「小」，正好让我们整轮手算。

第 0 步： $\ket{s}=\tfrac12(\ket{00}+\ket{01}+\ket{10}+\ket{11})$， 四个振幅都是 $0.5$。

第 1 步（oracle）： 目标变号：

$$\big(\tfrac12,\ \tfrac12,\ -\tfrac12,\ \tfrac12\big)\tag{9.8.8}$$

第 2 步（关于平均值翻转）： 均值 $\bar a=\frac{0.5+0.5-0.5+0.5}{4}=\tfrac14$。 每个振幅 $\mapsto 2\times\tfrac14-a_x=\tfrac12-a_x$：

$$\big(0,\ 0,\ 1,\ 0\big)\tag{9.8.9}$$

态精确变为 $\ket{10}$。测量：100% 命中，一次查询。 经典平均要翻 $2.25$ 个抽屉（最坏 3 个）才能确定。 几何核对：$\phi_1=(2\times1+1)\times30^\circ=90^\circ$，正对目标，分毫不差。

平方就是极限：BBBV 下界

会不会有更聪明的量子算法做到 $\log N$？不会。 Bennett–Bernstein–Brassard–Vazirani 定理：任何量子算法解无结构搜索, 至少需要 $\Omega(\sqrt N)$ 次 oracle 查询。思路值得一记： 每次查询对态的扰动至多 $O(1/\sqrt N)$（只动一个分支的符号）， 而要把「目标是 $w_1$」和「目标是 $w_2$」的末态拉开到可区分的距离, 累计扰动必须 $O(1)$——除法即得 $\Omega(\sqrt N)$。 Grover 恰好贴着下界飞行,连常数 $\pi/4$ 都是最优的。

∎本节关键公式

• Grover 迭代

  $$G=D\,O,\quad O=I-2\ket{w}\bra{w},\quad D=2\ket{s}\bra{s}-I$$

  两面镜子：oracle 反射 + 平均值反射 = 旋转 2θ

• 角度参数

  $$\sin\theta=\sqrt{M/N},\qquad \phi_k=(2k+1)\theta$$

  M 为目标数；每轮向目标转 2θ

• 命中概率

  $$P(k)=\sin^2[(2k+1)\theta]$$

  正弦振荡——过了 π/2 会掉头，必须数圈停车

• 最优轮数

  $$k_{\text{opt}}\approx\frac{\pi}{4}\sqrt{N/M}$$

  BBBV 下界 Ω(√N)：平方加速已是黑盒搜索极限

?自测共 4 题

1. 1.

   Grover 迭代的两个步骤在几何上分别是什么？

   • 关于 ∣r⟩（垂直于目标）的反射，和关于 ∣s⟩（均匀叠加）的反射
   • 关于 ∣w⟩ 的反射，和关于 ∣r⟩ 的反射
   • 一次旋转 θ，和一次旋转 −θ
   • 一次投影测量，和一次幺正旋转

   提交
2. 2.

   N = 10⁶ 个条目、单个目标。Grover 的最优迭代次数约是多少？（整数）

   允许 300% 相对误差

   提交
3. 3.

   N = 4、单个目标，做了 2 轮 Grover 迭代（多转了一轮）。此时命中概率是多少？

   允许 2% 相对误差

   提交
4. 4.

   关于 Grover 算法的适用范围，正确的是？（多选）

   多选题

   • 它对无结构搜索给出平方加速，且 BBBV 定理证明不可能更快
   • 它把 NP 完全问题变成多项式可解
   • 目标有 M 个时迭代次数约为 (π/4)√(N/M)
   • 对称密码的应对办法是把密钥长度加倍

   提交

接下来

平方加速已经贴到黑盒搜索的天花板,想要指数加速， 就必须离开黑盒、去开采问题的内部结构。 有一个问题的结构恰好是量子力学最擅长的——周期性： 大数因数分解可以归约成「找一个函数的周期」， 而找周期正是干涉的看家本领。下一节：Shor 算法， 以及它悬在 RSA 头顶的那把剑。