4.2 Grover 算法：振幅放大的平方级加速

4.2 Grover 算法：振幅放大的平方级加速

本节摘要：Grover 解决无序数据库搜索：N 条记录里找出唯一满足条件的那条，经典最坏要查 N 次，Grover 只需约 π√N/4 次。本节给出 oracle 相位反转与扩散变换这对组合的几何图像，逐轮演算振幅如何被"泵"高，并用 N=10000（约 100 次迭代对比经典 5000 次）把平方加速落到具体数字。它也是三个算法里唯一有直接商业想象力的：枚举、反演、 satisfiability 类问题都在射程内。

问题设定与核心困难

输入是一个黑箱函数 f（oracle）：输入候选编号 x，输出 1 表示 x 是目标，0 表示不是。承诺恰有一个 x* 使 f(x*)=1。问：找到 x*。

经典上无任何捷径——黑箱不泄露结构，只能挨个问，平均 N/2 次，最坏 N 次。这正是无序搜索的定义：没有结构可利用。Grover 的成就在于绕开"逐个询问"，改用全局操作：一次 oracle 调用不是查询某一个 x，而是同时给所有 x 的振幅做条件操作——目标 x 的振幅被乘上 −1，其余不动。这种"一次调用，全体响应"的批量性只有量子叠加能给。

两步一组：反转与绕平均翻转

Grover 迭代（记作 G）由两个门级步骤组成，几何上是平面上的两次镜像反射：

第一步 Oracle 反射 O：目标态振幅乘 −1
  O|x⟩ = −|x⟩（若 x = x*）；O|x⟩ = |x⟩（其余）
  几何效果：整个振幅矢量沿"目标轴"做镜像

第二步 扩散反射 D：绕全体振幅的平均值翻转
  D = 2|均值态⟩⟨均值态| − I
  逐分量效果：新振幅 = 2×平均 − 旧振幅
  几何效果：矢量沿"平均方向"再做镜像
​

两次反射连乘等于一次旋转。设全部振幅初始均匀（每个 1/√N），目标轴与均匀态的夹角为 θ，sinθ = 1/√N。每做一轮 G，振幅矢量朝目标方向匀速旋转 θ。于是找到目标的期望迭代次数：

初始偏角 θ（sinθ = 1/√N ≈ θ，N 大时）
把振幅转到目标轴附近需旋转约 θ/2 到 π/2
迭代次数 k ≈ π/(4θ) ≈ (π/4)·√N ≈ 0.8·√N
​

迭代到位后测量，命中目标的概率接近 1。用矩阵把每一步的账算细（以 N=4、x*=10 二进制为例）：

初始：[1/2, 1/2, 1/2, 1/2]（对应 |00⟩|01⟩|10⟩|11⟩）
O 之后：[1/2, 1/2, −1/2, 1/2]
平均 = 1/4；D：新 = 2×(1/4) − 旧
D 之后：[0, 0, 1, 0] —— 一步到顶，测得 |10⟩ 概率 = 1

N=4 恰好一轮收敛，是教科书级的巧合（θ=30°，90°/30°=3 次反射 = 1.5 轮）
​

图：Grover 每轮迭代的振幅演化（N=16）

每轮增益递减是旋转图像的自然推论：靠近目标轴后，同样的旋转步长在"高度"上的增量变小；越过峰值还开始回落——所以 Grover 有明确的"该停就停"，迭代次数不是越多越好。

把数字算实：N=10000 的账本

抽象的 O(√N) 落到一张表上：

N=10000 这一行值得背下来：经典平均五千次查询，Grover 约一百次迭代。看似只是百倍，但平方加速的含金量随规模滚雪球——把 N 放大一万倍，经典代价放大一万倍，Grover 只放大一百倍。在密码学的密钥穷举语境里，"平方级"等于把有效密钥长度砍半：128 位密钥的安全强度在 Grover 面前约等于 64 位（第 6.1 节会讲这对现实部署的影响）。

若目标是 t 个并列答案，迭代次数缩为约 (π/4)√(N/t)，t 越大越轻松。这个"多解更省"的特性让 Grover 能嵌进大量组合问题：数独求解、图着色、布尔可满足性，都能编码成 oracle 反复调用。

线路与实现成本

一轮 G 的线路骨架如下（Qiskit 风格）：

from qiskit import QuantumCircuit

def grover_iteration(n, oracle):
    g = QuantumCircuit(n)
    g.compose(oracle, inplace=True)        # 第一步：oracle 相位反转
    g.h(range(n))                          # 扩散变换三明治：
    g.x(range(n))                          #   H → 多重受控 Z → H·X·H 的共轭还原
    g.h(n - 1)
    g.mcx(list(range(n - 1)), n - 1)       #   多受控 Z（实现绕平均翻转）
    g.h(n - 1)
    g.x(range(n))
    g.h(range(n))
    return g

# N=8 的完整搜索：铺开 + 2 轮 G + 测量
qc = QuantumCircuit(3)
qc.h(range(3))
qc.compose(grover_iteration(3, mark_index_5), inplace=True)
qc.compose(grover_iteration(3, mark_index_5), inplace=True)
qc.measure_all()
# 统计：|101⟩ 出现概率约 0.945，其余各项分食残余
​

注意账单的诚实一面：oracle 不是免费的。现实中 f 往往是一段逻辑电路，翻译成量子门的深度可能不小；多受控门（mcx）在无纠错设备上还要进一步分解成大量 CNOT。Grover 的加速是查询次数意义上的，端到端收益取决于 oracle 的线路成本——这是评估任何"Grover 加速某某任务"新闻时的第一问。

几何直觉的三句总结

第一句，oracle 是"以目标为轴的镜像"，扩散是"以平均为轴的镜像"，两次镜像合成一次匀速旋转。第二句，旋转的总角度由初始偏角（≈1/√N）决定，所以迭代次数天然是 O(√N)——复杂度直接写进了几何。第三句，峰值过后继续迭代概率反而下降，"何时停"和"怎么转"同样重要。这三句也解释了 QAOA（4.4 节）为何长得像 Grover：变分算法干脆把"转多少"交给经典优化器去试。

本节要点回顾

• 批量 oracle：一次调用给全部振幅做条件操作，绕开"逐个询问"的经典宿命。
• 两镜一旋：oracle 反射 + 扩散反射 = 朝目标匀速旋转，步长 θ≈1/√N。
• N=10000 对照：经典 5000 次平均查询 vs 约 100 次迭代；平方加速随规模滚雪球。
• 迭代有峰值：约 π√N/4 轮封顶，过度迭代反噬。

Grover 是"在黑暗里摸出唯一亮的东西"。下一节的 Shor 更狠：把"分解大数"转化成"读出一个周期"，用傅里叶变换一次性兑现指数加速——那是整个领域震慑密码学的底气。