Grover 算法深入：振幅放大、多解搜索与通用加速

问题：N 个无序项，找「标记项」（黑盒判定 f(x)=1）
  → 只能「逐个试」
经典最优：O(N) 次查询（最坏）
Grover：O(√N) 次查询（量子）
→ 无结构 = 只有黑盒，无任何启发式信息

1. 初始化均匀叠加：|s⟩ = (1/√N) Σ|x⟩
2. 循环 √N 次：
   a. Oracle（标记翻转）：标记项相位翻转（-1）
   b. 扩散算子（均值翻转）：围绕均值的反射
3. 测量 → 高概率命中标记
→ 关键：两个反射的复合 = 旋转

任意态可以投影到「标记子空间 |t⟩」与「非标记 |u⟩」张成的平面：
  初始 |s⟩ 在这个平面内，与 |t⟩ 夹角 θ（sin θ = 1/√N）
  每次循环：两个反射 → 旋转 2θ
  √N 次后旋转到「几乎平行 |t⟩」→ 测量命中标记
→ Grover = 平面内的「旋转加速」

Grover 是振幅放大的特例（放大均匀叠加里的小振幅）
振幅放大（amplitude amplification）：
  任意初始叠加 |s⟩，放大「好子空间」的振幅
  循环：标记反射 + 扩散反射（绕 |s⟩）
  步数 ≈ 1/√(好振幅概率)
→ 把「小概率好结果」放大到「高概率」

不只是搜索：
  - 蒙特卡洛估计的加速（量子振幅估计）
  - 随机算法的「去随机化」
  - 量子计数、最小值搜索
→ 振幅放大是「量子算法工具箱」里与相位估计并列的核心原语

搜索 = 从均匀叠加放大标记
采样 = 从任意叠加放大目标分布
估计 = 放大「某函数值」的振幅（振幅估计）
→ 一句话：任何「小振幅目标」都能被放大到 O(1/√p) 次

初始叠加里标记总振幅 = √(M/N)（M 个解各 1/√N）
旋转角 sin θ = √(M/N)
步数 ≈ (π/4)·√(N/M)（更少！）
→ 解越多，需要的步数越少

M = 1：O(√N)（经典搜索最优加速）
M = N/2：θ 接近 π/4，几乎「一步命中」（一半是解）
M 未知：需要先「估计 M」（量子计数）再定步数
→ 多解场景的步数公式是 Grover 的「第一推广」

- 数据库里「多个匹配」时加速更明显
- 组合问题「多个解」时同样
- 但要「先知道 M 或估计 M」→ 量子计数（见第 7 节）
→ 多解不是障碍，是「加速放大器」

振幅放大到「最高点」后继续转 → 振幅开始下降
  → 步数必须「精确」否则错过峰值
  → 步数是整数，而最优步数常非整数 → 概率非 1
经典 Grover：成功概率 1 - O(1/N)（接近 1 但不等于 1）

用「条件相位 + 调整步数」让概率精确为 1
  → 精确 Grover（exact Grover algorithm）
  → 处理「N 不是 2 的幂」「M 已知」等边界
→ 理论干净，工程上概率 1-O(1/N) 已够用

「最少几次查询能保证成功概率 ≥ p」→ 阈值问题
  → 与振幅放大的「最优查询数」等价
  → 证明 Grover 是最优的「概率放大器」

无结构搜索的本质：黑盒判定 f(x)
  → 一次查询最多「翻转一个振幅」的符号
  → 干涉需要「相位累积」
  → 每个标记需要「多次旋转」积累振幅
→ 信息论下界：需要 Ω(√N) 次查询

如果只做 T 次查询：
  任意两个「标记位置」不同的实例
  在 T 次查询后的量子态「几乎相同」（查询太少分不清）
  → 无法区分 → 必须 T ≥ Ω(√N)
→ 任何量子算法都不能突破 √N

- Grover 是最优的（达到信息论下界）
- 无结构搜索的「量子加速天花板」= 二次
- 想更快必须引入「结构」（排序、索引、哈希）
→ √N 是「无结构」的物理极限

有用：
  - 真「无结构」：密钥暴力、无索引数据库
  - 查询昂贵：黑盒调用成本高，√N 次查询省大钱
  - 经典已 O(N)：Grover 给二次加速

不划算：
  - 经典已 O(log N)（有结构）：无优势
  - 数据在经典数据库（索引/B+树）：索引查询更快
  - 叠加访问开销大（memory-heavy oracle）
→ Grover 的价值在「无结构 + 查询昂贵」的场景

Grover 的旋转角 sin θ = √(M/N)
  → 角度里藏着 M！
  → 用「相位估计」测量这个角度 → 得到 M 的估计
量子计数：
  O(√N) 次查询 → 估计 M 到 ±ε 精度（经典要 O(N)）
→ Grover + QPE 的组合原语

1. 把 Grover 循环做成「受控旋转」的相位
2. 对「Grover 算符」做量子相位估计
3. 测量相位 → 得到 θ → 反推 M
→ 量子计数 = 「用 QPE 测 Grover 的旋转角」

- 多解搜索前「先数 M」定步数
- 数据库匹配计数（SELECT COUNT 的量子版）
- 组合问题的解数量估计
→ 量子计数是 Grover 家族里「最实用」的成员

对称密钥（AES）的暴力搜索：N = 2^k 个密钥
  → Grover 把搜索空间从 2^k 减半到 2^(k/2)
  → 安全含义：AES-128 的 Grover 强度 ≈ 64 bit
  → 这就是「量子安全」要求密钥翻倍的根源
  （见 /quantum-post-quantum-cryptography/）

- 属性无索引的查询（全表扫描的量子版）
- 数据可用叠加访问时 → O(√N)
- 前提：oracle 高效（黑盒调用不能太贵）
→ 数据库场景的「实用性」取决于数据访问方式

- 布尔可满足性（SAT）：把赋值搜索当成 Grover
- 图着色/子集和：搜索解空间
- 与变分算法对比：精确搜索 vs 启发式近似
→ 组合问题的「精确解」可 Grover 加速（指数空间减半）

- 固定点 Grover：避免「过转」，鲁棒到步数误差
- 量子最小值搜索：Grover + 二分 → 找最小值 O(√N)
- 量子振幅估计：蒙特卡洛估计的量子加速
- 空间查询（spatial search）：网格上的行走搜索（见行走篇）
→ Grover 家族覆盖「搜索/最小/估计」三大类

- 扩散算子的 O(log N) 门开销（H + CNOT 链）
- Oracle 的代价：黑盒若很贵，√N 优势被稀释
- N 不是 2 的幂：用「叠加覆盖」或精确 Grover
- 噪声：振幅放大对退相干敏感，需纠错
→ 工程上「Oracle 成本 + N 形状」决定实际收益