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

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

- 作者：David（道雾轩）
- 专栏：写给程序员的量子计算（https://daiw.org/manual/quantum-computing.md）
- 最后更新：2026-07-14
- 原文：https://daiw.org/manual/quantum-computing/grover
- 转载与引用：请注明出处并附原文链接（https://daiw.org/about/copyright）

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

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

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

## 思路：振幅放大

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

```mermaid
flowchart LR
  A["H^n:所有项均匀叠加<br/>(每项振幅都一样小)"] --> B["重复 ~√N 轮"]
  B --> C["① 预言机:给正确答案<br/>盖个负号(翻相位)"]
  C --> D["② 扩散算子:绕平均值翻转<br/>(把被标记项的振幅抬高)"]
  D --> B
  B --> E["测量 → 大概率得到答案"]
```

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

## 亲手搭一个(N=4)

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

```python
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())
```

```text
{'11': 1000}
```

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

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

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

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

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

## 它的威力与边界

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

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

## 小结与下一章

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

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

## 参考文献

- [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 与几何图像。