Grover 的振幅放大为什么是 根号N

前情提要：第 8 篇《Grover：在干草堆里快速找针》里，我们说 Grover 把无序搜索从 N 步压到根号 N 步，只给了直觉。这一篇，用"振幅放大"的几何，解释这个根号到底从哪来。

一、钩子：根号从哪来

经典搜 N 个里的 1 个，平均试 N/2 次。Grover 只要约根号 N 次。这个"根号"不是凑出来的，而是旋转几何的必然结果：每次迭代让"目标态的振幅"抬高一小步，要抬到接近 1，需要的步数正好和根号 N 成正比。

二、把搜索看成"在状态空间里转箭头"

把 N 个可能答案看成一组等权的叠加态。目标答案是其中之一，但一开始它的振幅只有 1/根号N（淹没在 N 个里）；其余 N-1 个是非目标，振幅也差不多大。Grover 的目标，就是把"目标那一份"的振幅单独养大，让测量时几乎必中它。

三、一次迭代 = 一小步旋转

Grover 的每一步（一次迭代）做两件事：

1. 预言子（oracle）：给目标态偷偷加一个负号（翻相位），非目标不变； 2. 关于平均的反演：把整体"绕平均值"翻一下。

这两步合起来，几何上等价于：把整个状态向量，朝"目标态方向"转过一个固定小角。目标振幅因此抬高一点，非目标被压低一点。

四、要转 90 度，需要 根号N 步

关键在角度。初始时，目标态和"全非目标平均方向"几乎垂直（夹角约 90 度）。而每一步转过的角度，正比于目标当前的振幅，也就是约 1/根号N 弧度。

要把目标从"几乎垂直"转到"正前方"（振幅接近 1），大约需要转过 90 度。每步转 1/根号N，总步数就约 = 90 度 ÷ (1/根号N) = 根号 N 量级。

这就是根号 N 的来历：步长 ∝ 1/根号N，路程 ∝ 1，故步数 ∝ 根号N。不是指数加速，但比起经典的 N，仍是扎实的二次加速。回到第 8 篇：它能把"大海捞针"快一个数量级（N 为一百万时，从约 50 万次降到约一千次）。

五、小结与预告

这一篇，把第 8 篇的 根号N 落到了几何：

• 搜索 = 在 N 个叠加态里放大目标振幅；
• 一次 Grover 迭代 = 朝目标方向转过小角，步长 ∝ 1/根号N；
• 转过约 90 度需 根号N 步——二次加速，非指数；
• 呼应第 7 篇 Deutsch：根子仍是干涉（振幅相长/相消）。

讲到这，往深里抠原理的这些文章，已把门、几何、纠缠、复杂度、纠错、测量、算法干涉都补了一遍。最后一块拼图是"硬件"——第 12 篇《硬件路线大乱斗：超导 / 离子阱 / 光量子 / 拓扑》总览过四条路线，而下一篇，我们就把其中最有代表性的一种拆开看：超导量子比特。

下次见。