量子计数：QPE 计数是精确求相

Grover 搜索靠反复施加扩散算子把答案“挤”出来；量子计数换了个思路：把振幅 $|a_x|$ 写进一个特征值，再用一次逆 QFT 把特征值读出来。这条路线的算术需求与振幅放大几乎正交——它不碰加法、不碰乘法，只压在一个东西上：能不能精确合成任意角度的受控相位旋转。这个问题的答案就是 QFT，所以量子计数的成本账目与 QFT 合成、近似 QFT是同一本账。本词条给出这条等价关系、QPE 线路，以及为什么“精确计数”和“容错计数”之间没有免费的午餐。

一、这个应用需要哪种算术原语

把量子计数拆开，算术需求只有一条：

$$Q|0⟩=|a⟩,U|a⟩=e^{2\pi i\lambda }|a⟩⟹U|0⟩=\sum _x{a}_x{e}^{2\pi i\lambda x}|x⟩.$$

这就是指数化能起作用的原因：$a_x$ 被 $e^{2\pi i\lambda x}$ 乘上，$\lambda$ 被写进了相位。要在 $t$ 比特精度上读出 $\lambda$，需要两样算术：

1. 受控的 $U^{2^j}$（$j=0,\dots ,t-1$）——第 $j$ 次作用的角度是 $2\pi 2^j/2^t$。这是指数化算术，见平方-乘法。它是全站唯一一处量子计数真的调用”重复平方”的地方，代价随 $t$ 线性增长。
2. $t$ 比特精确逆 QFT——把 $t$ 个受控相位寄存器的读数一次性解纠缠。

关键在于第 2 条：$t$ 比特 QFT 展开后是 $t$ 个 H 门加一串角度为 $2\pi /2^k$ 的受控相位，这些角度一般不是 Clifford+T 的元素。所以“精确地做一次 QPE”这句话本身就意味着“精确地合成一整族任意角受控旋转”。量子计数不是一个与 QFT 并列的算法，它是 QFT 的一种用法——成本落在同一个地方。

二、QPE 线路：相位寄存器是主角

相位估计线路：相位寄存器 y 做指数化测量，逆 QFT 读出特征值（t = 2，N = 4）

图里最该盯住的是 F₂⁻¹ 那五个门。它们的门型是 h、cp、swap——没有一个是 Clifford+T。这就是”精确求相”的全部含义：你要的不是”一个名字叫逆 QFT 的黑箱”，而是 $t$ 个精确到任意角度的受控旋转。把这一格的成本当成 $O(t^2)$ 个便宜门来估，是量子计数文献里最常见的高估漏洞。

三、恒等式：${\mathrm{QFT}}^{\otimes }$ 就是”求和 × 逆 QPE”

把上面的线路与 QFT 的定义式并排放：

$${\mathrm{QFT}}^{\otimes }\left(\frac{1}{\sqrt{N}}\sum _{x}f(x)|x⟩\right)=\frac{1}{N}\sum _y\left(\sum _{x}f(x)e^{2\pi ixy/N}\right)|y⟩.$$

而 QPE 线路作用在同一个态上，给出的正是同一个式子。两者之间差的就是那个 $1/N$——即”对所有输入求和”。于是有一条精确的等价：

$${\mathrm{QFT}}^{\otimes }=\frac{1}{N}\cdot \left(\text{对输入求和}\right)\cdot \left(\text{逆 QPE 线路}\right).$$

这条恒等式是本词条的组织核心，它同时说了两件事。第一，计数算法把 QFT 当作原语来用，所以 QFT 的全部成本被原封不动地搬了过来——包括不可容错的那些任意角门。第二，恒等式里的”求和”是经典意义下的、对输入索引的求和（$O(\log N)$ 深度的分层加法树），不是amplitude-amplification里那种对无界实数的量子求和；两者不要混淆。Brassard–Høyer–Mosca–Tapp（2002）正是沿着这条恒等式给出量子计数的原始形式：把 $Q$ 装进振幅放大得到的酉里，对 $|a⟩$ 做相位估计，读出的就是 $a$ 的振幅。

四、同一枚硬币的两面

现在把容错问题摆到桌面上。近似 QFT 与精确 QPE 是同一个截断决策的两面：一旦你接受 $t$ 比特逆 QFT 的误差 $\epsilon$，那么

• 计数结果的分辨率就被限制在 $\epsilon$ 量级，$t$ 再大也不再有收益；
• 被丢掉的小角度门正是 T 数的主要来源——标准容错实现是”去掉小角度受控旋转，再把剩下的合成到 Clifford+T”，$O(t{\log }^{2}t)$ 个 T 门。

于是有两条自洽的选法：(a) 精确 QPE：用任意角旋转实现 $t$ 比特的相位寄存器，理论上可容错，代价全部压在合成这些旋转的 T 数上；(b) 截断 QPE：直接用 Clifford+T 实现截断 QFT，代价是分辨率封顶。没有第三条路，任何声称”既精确又只花 $O(t^2)$ 个 Clifford+T 门”的方案都在偷换其中一个前提。截断阈值 $\epsilon$ 怎么定、误差账怎么算，见approximate-qft；三种实现形态（精确/截断/半经典）的取舍见半经典 QFT。

论文依据

• Grover（1996） —— 振幅放大框架：$Q$ 把 $|0⟩$ 送到 $|a⟩$、$U$ 以特征值放大它。量子计数用的正是这个 $U$，本词条第一节的设定直接来自此文。
• Brassard–Høyer–Mosca–Tapp（2002） —— 量子计数的原始出处，把计数与振幅估计一并建立在对 $U$ 的特征值估计上；本词条第三节的恒等式是它所依赖的算术事实的展开。

延伸阅读

• qft-synthesis —— 任意角受控旋转合成到 Clifford+T 的 T 数账
• approximate-qft —— 截断阈值 $\epsilon$ 与容错形态的完整对照
• qft-gates —— $t$ 比特 QFT 的递归层结构
• amplitude-estimation —— 把本词条的一次读出换成迭代查询后的版本