量子计数：数一数有多少个解

抽屉里有钥匙，但你不知道是一把、两把，还是一把也没有。Grover 算法 能帮你拉开有钥匙的那一屉，却不会告诉你还有没有下一把。量子计数问的是另一个问题：不是「哪个是解」，而是「一共有几个」。

转多少下，取决于有几个解

Grover 的一步迭代，是在一个二维平面里旋转。这个平面由两个方向张成：所有解等权叠加的 $|\beta\rangle$，和所有非解等权叠加的 $|\alpha\rangle$。均匀叠加落在两者之间，旋转角 $\theta$ 满足

每转一次前进 $\theta$，所以最优步数与 $\sqrt{N/M}$ 成正比。N 是一百万时，M 从 1 变成 4，最优步数就少一半。不知道 M，就不知道该转几下：转少了抬不起来，转多了越过顶点。

这条曲线的起伏周期，正是被 M 与 N 的比值定住的。下面这个演示里 M 固定为 1，你能拖的只有迭代次数。

把周期读成相位

计数不去找解，而是去问迭代算符转了多少度。做法是把 相位估计 套在 Grover 迭代上：均匀叠加可以写成两个本征态的组合，本征相位是 $e^{\pm i\theta}$，于是相位寄存器读出的就是 $\pm\theta/2\pi$，取绝对值再反解，M 就有了。整套东西与 振幅放大 共用同一个神谕，区别只在最后量的是「哪个」还是「几个」。

代价要算清楚。要分辨 M 与 M+1，相位精度得细到 $\Delta\theta\approx 1/\sqrt{NM}$，查询次数量级是 $\sqrt{NM}$；M 很小时退回 $\sqrt N$，与 Grover 同阶。收益却不同：经典要区分「没有解」和「恰好一个解」，得查到几乎每一项，是 Ω(N)；计数只要 $\sqrt N$ 量级。加速落在「计数」这个任务上，不落在「找出一个解」上。

两者是配套的。先用计数把 M 估出来，再按 $\frac{\pi}{4}\sqrt{N/M}$ 步跑 Grover，就不用猜步数。计数自己也不便宜：要神谕、要辅助比特、要受控迭代。