Grover 搜索查询复杂度

形式陈述

设 $x\in\{0,1\}^N$ 有 $0<M<N$ 个标记坐标，good 子空间由 $x_i=1$ 的 $|i\rangle$ 张成。采用标准 bit oracle $|i,b\rangle\mapsto|i,b\oplus x_i\rangle$ ；它既能验证候选，也能在辅助位为 $|-\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,

其中取 $\theta=\arcsin\sqrt{M/N}\in(0,\pi/2)$ ， $|G\rangle,|B\rangle$ 分别是标记与未标记坐标的均匀态。相位 oracle $S_x=I-2\Pi_G$ 翻转 good 分量，diffusion $D=2|s\rangle\langle s|-I$ 关于 $|s\rangle$ 反射。一次 Grover iterate

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)$ 。若已知 $1\le M\le N/2$ ，取最接近 $\pi/(4\theta)-1/2$ 的非负整数 $r$ ，最终角度与 $\pi/2$ 的偏差至多为 $\theta$ ，所以一次成功率至少为 $\cos^2\theta=1-M/N\ge1/2$ 。按独立重复、任一次验证成功即接受运行两次，每次测量后用一次 bit 查询验证候选，至少一次找到标记项的概率便达到 $3/4$ 。总查询数为

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

这给出有界误差查询上界。若 $M>N/2$ ，直接独立抽取并验证两个坐标就有至少 $3/4$ 的成功率；若已知 $M=N$ ，任意输出一个坐标即可。

BBBV hybrid argument 表明，区分 $0^N$ 与任一单标记输入，若要求每个输入上的成功率至少为 $2/3$ ，就必须查询 $\Omega(\sqrt N)$ 次。对 $1\le M\le N/2$ 的有标记输入，寻找一个标记坐标的对应下界为 $\Omega(\sqrt{N/M})$ ，与上述查询上界匹配。

直觉

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

旋转次数决定何时测量：接近 good 方向时成功率最大，继续旋转反而使它下降。已知 $M$ 时可由 $\theta$ 计算停止位置；未知 $M$ 时则需要搜索合适的迭代次数。

Grover 搜索在 good-bad 平面中的振幅旋转及 N=8,M=1 的成功概率 — Grover 振幅旋转

例子与边界

取 $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$ 时越过成功方向。Boyer–Brassard–Høyer–Tapp 的随机迭代策略结合普通候选抽样，在 $M\ge1$ 时以期望 $O(\sqrt{N/M})$ 次查询找到经验证的标记项；无标记时不能靠这一期望结论保证停止。[1, §4]

要得到对全部输入都有效的 OR 判定硬上限，取该期望界的统一常数 $c>0$ ，在尚未找到标记项且查询预算达到 $B=\lceil3c\sqrt N\rceil$ 时停止并回答“无”。对 $M\ge1$ ，原算法找到首个验证成功项的查询数 $T$ 满足 $\mathbb ET\le c\sqrt{N/M}\le c\sqrt N$ ；Markov 不等式给出 $\Pr(T>B)\le1/3$ 。对 $M=0$ ，验证不会误收，而截止规则保证停止。这样才得到每条分支至多 $B$ 次、单侧错误至多 $1/3$ 的 $O(\sqrt N)$ 查询算法。

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

推论与应用

Grover 是振幅放大的均匀搜索特例：状态制备 $A$ 生成均匀叠加，good projector 由标记 oracle 给出，且 $-AS_0A^\dagger=2|s\rangle\langle s|-I=D$ ，所以两者的迭代算子恰好相同。更一般地，若成功率为 $a$ 的状态制备过程可逆，并能相干实现成功子空间的相位反射，就可在 $O(1/\sqrt a)$ 次调用的尺度上把成功率提高到常数。

单标记搜索的 $O(\sqrt N)$ 上界与 BBBV 的 $\Omega(\sqrt N)$ 下界共同确定了无结构黑盒搜索的最优查询尺度。

参考资料

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.
[1] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp, “Tight Bounds on Quantum Searching,” Fortschritte der Physik 46, 1998, pp. 493–506；所链作者稿 §4，Lemma 2、Theorem 3 及其后的无解超时讨论。

形式陈述 ​

反向链接

形式陈述