Grover 搜索查询复杂度

形式陈述

设 $x\in\{0,1\}^N$ 有 $M\ge1$ 个标记坐标，good 子空间由 $x_i=1$ 的 $|i\rangle$ 张成。均匀态可分解为

|s\rangle=\frac1{\sqrt N}\sum_{i=1}^N|i\rangle =\sin\theta\,|G\rangle+\cos\theta\,|B\rangle, \qquad \sin^2\theta=\frac MN,

G=DS_x

恰在 $\operatorname{span}\{|G\rangle,|B\rangle\}$ 中旋转 $2\theta$ 。从 $|s\rangle$ 开始做 $r$ 次后，

G^r|s\rangle =\sin((2r+1)\theta)|G\rangle +\cos((2r+1)\theta)|B\rangle,

故成功概率为 $\sin^2((2r+1)\theta)$ 。若 $M$ 已知，取最接近 $\pi/(4\theta)-1/2$ 的非负整数 $r$ ，使用

O\!\left(\sqrt{\frac NM}\right)

次查询得到常数以上成功率，属于有界误差查询上界。末端若要输出可验证见证，可再查询测得的候选坐标一次。

BBBV hybrid argument 表明，区分 $0^N$ 与任一单标记输入要达到常数成功率必须查询 $\Omega(\sqrt N)$ 次；推广到 $M$ 个标记得到 $\Omega(\sqrt{N/M})$ 的相应搜索尺度。因此 Grover 在无结构 oracle 模型中渐近最优。

直觉

两个反射的乘积是旋转。相位 oracle 把状态推到 $|s\rangle$ 的另一侧，diffusion 再把它关于 $|s\rangle$ 镜像；每轮把 good 方向的角度推进 $2\theta$ 。初始 good 振幅只有 $\sqrt{M/N}$ ，但相干旋转让振幅线性积累，成功概率则是其平方，于是查询数从经典的 $N/M$ 降到平方根。

“同时查看所有位置”不是正确解释。每轮只得到一次黑盒相位作用，若旋转过头，good 振幅还会下降；算法必须按 $\theta$ 选择次数，或在未知 $M$ 时采用额外策略。

例子与边界

取 $N=8,M=1$ ，则 $\sin\theta=1/\sqrt8$ 。一次迭代的 good 振幅为

\sin(3\theta) =3\sin\theta-4\sin^3\theta =\frac{5}{2\sqrt8},

成功概率 $25/32$ 。两次迭代使用恒等式

\sin(5\theta) =16\sin^5\theta-20\sin^3\theta+5\sin\theta =\frac{11}{4\sqrt8},

所以成功概率为

\frac{121}{128}\approx0.945.

轨迹也显示迭代不是越多越好：角度继续越过 $\pi/2$ 后概率会周期性下降。

若 $M=0$ ， $\theta=0$ ，所有 Grover 迭代都保持 $|s\rangle$ ；仅测量无法证明不存在标记项，候选验证只能拒绝当前候选。若 $M$ 未知，固定按 $M=1$ 运行会在较大 $M$ 时 overshoot；随机选择逐步扩大的迭代次数可获得期望 $O(\sqrt{N/M})$ 搜索，但要另行处理“无解”终止保证。

下界也依赖无结构 phase/bit oracle。若数据有排序、几何或哈希索引，允许的操作已不只是坐标查询；BBBV 不能阻止利用这些额外结构。查询最优也不表示 diffusion 的门复杂度或容错代价免费实现。

推论与应用

Grover 是振幅放大的均匀搜索特例：状态制备 $A$ 是均匀叠加，good projector 由标记 oracle 给出。把二维旋转抽离后，任何初始成功率为 $a$ 的过程都可在约 $1/\sqrt a$ 次调用尺度上放大。

搜索的 $O(\sqrt N)$ 上界与 BBBV 的 $\Omega(\sqrt N)$ 下界共同说明平方根提升是该黑盒任务的终点，不是等待更巧算法消除的松常数。若声称无结构搜索为多项式对数查询，应先检查是否偷用了更强 oracle、预处理或非 uniform advice。

参考资料

Lov K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” Proceedings of STOC 1996, pp. 212–219.
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani, “Strengths and Weaknesses of Quantum Computing,” SIAM Journal on Computing 26(5), 1997, pp. 1510–1523.
Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp, “Tight Bounds on Quantum Searching,” Fortschritte der Physik 46, 1998, pp. 493–505.

形式陈述 ​

反向链接

形式陈述