Grover 搜索 · 振幅放大与 √N 加速 · 写给程序员的量子计算

在 N 个无序项里找一个，经典要试 O(N) 次，Grover 只要 O(√N)。这一章亲手搭出 Grover，看正确答案的振幅怎么被「振幅放大」一轮轮抬高，讲清迭代次数为什么是 √N、以及「转过头反而更差」的经典坑。

Grover 搜索 · 振幅放大与 √N 加速

Deutsch-Jozsa 打的是人造问题；Grover 搜索打的是真问题：在 $N$ 个无序的项里，找出那个满足条件的。

想象一本没排序的电话簿，你要找出电话号码是某个值的那个人——只能一个个翻，平均要翻 $N/2$ 次，最坏 $N$ 次。这类「无结构搜索」经典无法更快。而 Grover 能在 $O(\sqrt{N})$ 次内找到——平方级加速。 $N$ 是一百万，经典要试百万次，Grover 只要一千次。

思路：振幅放大

Grover 的核心叫振幅放大(amplitude amplification)。回想量子算法的套路：铺开叠加 → 用干涉把正确答案的振幅抬高、错误答案压低 → 测量。Grover 把这个「抬高」做成一个可以反复施加的操作，每来一轮，正确答案的振幅就高一点：

图表加载中…

每一轮两步：① 预言机用相位反冲给正确答案盖个负号；② 扩散算子(diffusion) 做一次「绕平均值翻转(inversion about the mean)」——被盖了负号的那一项，经此一翻，振幅显著高出其余。几何上，每轮相当于把状态向量朝「答案」方向转一个固定角度，越转越接近答案。

亲手搭一个(N=4)

拿最小的例子：2 个 qubit（ $N=4$ 项），标记的答案是 $\ket{11}$ 。此时一轮迭代就能 100% 命中：

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

qc = QuantumCircuit(2, 2)
qc.h([0, 1])                 # 均匀叠加:四项各 1/2

# ① 预言机:给 |11⟩ 盖负号。两个 qubit 都是 1 才翻相位 → 正好是 CZ
qc.cz(0, 1)

# ② 扩散算子:H · X · CZ · X · H(绕平均值翻转的标准实现)
qc.h([0, 1]); qc.x([0, 1]); qc.cz(0, 1); qc.x([0, 1]); qc.h([0, 1])

qc.measure([0, 1], [0, 1])
sim = AerSimulator()
print(sim.run(transpile(qc, sim), shots=1000).result().get_counts())

{'11': 1000}

一轮迭代，100% 找到 $\ket{11}$ 。 你可以把预言机换成标记别的态（比如标记 $\ket{10}$ ：先对 qubit 0 加 X 把它「凑成全 1」再 CZ 再 X 还原），验证它总能找出你标记的那个。这就是搜索——你只告诉它「怎么验证一个答案对不对」（预言机），它就替你把对的那个找出来。

为什么是 √N，以及「转过头」的坑

振幅放大是「每轮转固定角度」，所以要转到答案方向，需要的轮数和 $\sqrt N$ 成正比。精确地说，最优迭代次数约为：

k \approx \frac{\pi}{4}\sqrt{N}

Grover 的经典坑：迭代不是越多越好，转过头反而更差。 因为每轮是「转固定角度」，转到正对答案（振幅最大）后继续转，就会转过头，振幅反而下降——再转甚至可能转回到几乎测不到答案。所以你必须掐着 $\frac{\pi}{4}\sqrt N$ 这个最优轮数停手，多转少转都不好。这和「经典算法跑越久越接近答案」的直觉完全相反。 $N=4$ 时最优是 1 轮（上面正好 100%）； $N$ 大时按公式取整。记住：Grover 要「适可而止」。

它的威力与边界

能加速什么：任何「解不好求、但答案好验证」的搜索。数据库搜索、约束满足、密码暴力破解的加速……凡是经典只能「一个个试」的，Grover 给平方级加速。
别夸大：平方级加速是多项式级的，不是像 Shor 那样的指数级。 $O(\sqrt N)$ 仍随 $N$ 增长，只是慢一截；它不能把指数难题变简单。而且它要求你能把「验证条件」写成一个量子预言机，并在相干的状态下跑完 $\sqrt N$ 轮——这对真机的噪声是很高的要求。

一个常被提及的应用：Grover 能把暴力破解 $k$ 比特密钥的难度从 $2^k$ 降到 $2^{k/2}$ ——相当于「密钥强度砍半」。所以后量子时代，对称加密的应对很简单：把密钥长度翻倍(AES-128 → AES-256)， $2^{128}$ 的一半又回到 $2^{128}$ 。真正被量子彻底击穿的是非对称加密(RSA/ECC)，那是下一章 Shor 的战场——那个才需要「换算法」而非「加长度」。

小结与下一章

Grover 用振幅放大在无序搜索里拿到 $O(\sqrt N)$ 加速：每轮「预言机翻相位 + 扩散绕均值翻转」把答案振幅抬高一点， $N=4$ 时一轮就 100% 命中。牢记两点：最优轮数 $\approx\frac{\pi}{4}\sqrt N$ ，转过头反而更差；它是平方（多项式）加速，不是指数，专治「验证易、求解难」的搜索。

压轴登场的，是量子算法里名气最大、也最有现实冲击力的一个——Shor 算法。它能在多项式时间内分解大整数，从而击穿 RSA。下一章讲清它的引擎（量子傅里叶变换）和为什么它让全世界都在准备「后量子密码」。👉 量子傅里叶与 Shor：破 RSA 的直觉。

参考文献

[1] Grover.「A fast quantum mechanical algorithm for database search.」1996. —— 原始论文。
[2] Qiskit 官方文档.「Grover's algorithm / amplitude amplification.」https://learning.quantum.ibm.com —— 线路与扩散算子。
[3] Nielsen & Chuang.《Quantum Computation and Quantum Information》， §6.1 —— Grover 与几何图像。

Grover 搜索 · 振幅放大与 √N 加速