第4章：查询模型、干涉与 Grover 搜索

Oracle 与资源

查询模型把 $U_f$ 当作可调用黑盒，计数调用次数；完整时间复杂度还要计入实现 oracle、制备状态、其他门和输出的成本。

一次查询作用于叠加态，不意味着能测出所有 $f(x)$ 。算法需要让不同路径振幅相加或抵消，把关心的性质集中到少量可测结果上。

把辅助位置为 $|-\rangle$ ，有

U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle.

函数值被编码为主寄存器的相位。Deutsch–Jozsa 在函数被承诺为常量或均衡的模型下，经前后 Hadamard，利用振幅求和区分两类；没有该承诺时不能把测量结果解释成同样的分类结论。

N 个候选中有 M 个标记项，令标记均匀态为 $|G\rangle$ 、未标记均匀态为 $|B\rangle$ ，初态

|s\rangle=\sin\theta|G\rangle+\cos\theta|B\rangle,\quad\sin^2\theta=M/N.

一次 Grover 迭代先翻转标记相位，再关于 $|s\rangle$ 反射，两次反射组合成旋转。k 次后成功概率为 $\sin^2((2k+1)\theta)$ 。

当 $M\ll N$ 且已知 M，取约 $\frac\pi4\sqrt{N/M}$ 次查询可使成功率很高。迭代过多会越过最佳角度，成功率再次下降。

N=4、M=1，初始每项振幅为 $1/2$ 。相位 oracle 将标记项改为 $-1/2$ ，此时振幅均值为 $1/4$ 。关于均值反射 $a\mapsto2\bar a-a$ 后，标记项成为 1，其余成为 0，一轮即可确定找到。

该例不代表任意大小都一轮成功；它来自特殊角度 $\theta=\pi/6$ 。

无结构搜索的量子查询下界为 $\Omega(\sqrt N)$ ，因此 Grover 在该模型中达到数量级最优。这不是任意计算问题的通用下界，也不能把 oracle 内部计算忽略后宣布整体任务同样加速。