振幅放大：扩散算子本身就是一条算术线路

Grover 搜索最常被这样描述：造一个均匀叠加、做一次 Oracle 打相位、再“关于平均值反射”，重复 $O(\sqrt{N})$ 次。这个描述掩盖了一个关键事实——扩散算子不是一个门序列，而是一次对 $2^n$ 个振幅的精确求和。数学上的扩散是 $2|a⟩⟨a|-I$，其中 $a$ 往往是一个叠加态；这类算符无法用 QASM 的布尔门（$X$、$Z$、AND）实现。本词条先把 QASM 上真正被执行的反射拆开，说明它与 $2|a⟩⟨a|-I$ 不是同一个东西；再说明精确实现需要哪些算术原语、代价为什么高；最后指出这条分岔如何一路决定了quantum-counting与amplitude-estimation的成本结构。

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

振幅放大对算术层的要求集中在一处：在不知道 $a$ 的具体振幅的情况下，把振幅平方和精确地累加进一个足够宽的寄存器。展开就一目了然——设 $|a⟩={\sum }_x{a}_x|x⟩$，则

$$2|a⟩⟨a|-I=\frac{1}{2^{n-1}}\sum _{x\in \{0,1{\}}^n}|a_x{|}^2|x⟩⟨x|-I.$$

展开后的第一项里有 $2^n$ 个待加项，每一项的权重是一个无界的实数 $a_x$。要把这条算术线路搭出来，需要三样东西：

1. 投影原语 $P_x=|x⟩⟨x|$，即“把 $|x⟩$ 之外的成分消掉”；
2. 受控平方/受控加法：把 $|a_x{|}^2$ 这个非整数、以二进制无穷尾的数累加到寄存器上。经典加法器处理不了无穷尾，必须是量子加法器，见常量加法与累加。
3. 量子求和：把 $2^n$ 项在深度 $O(\log 2^n)$ 内加起来。这一步是全条线路最贵的地方，原因见第三节。

值得注意的是，这个清单里没有乘法、没有模运算、没有 QFT。振幅放大是全站唯一一个”重算术需求但不用乘法”的算法；它的算术压力全部来自”对无界实数做精确加法”这一件事。

二、QASM 上真正被执行的那个反射

在实际的量子线路里，Grover 迭代写成 $H^{\otimes n}O{H}^{\otimes n}M$，其中 $M$ 被实现为布尔反射

$$M=X^{\otimes n}(I-2|0⟩⟨0{|}^{\otimes n})X^{\otimes n},$$

中间的因子是一次多控 $Z$ 门：对所有比特同时为 $0$ 的扇区打 $\pi$ 相位，用一个干净辅助比特与两个 Toffoli 即可实现，成本 $O(n)$ 个门。

这里有一个必须点破的事实：$I-2|0⟩⟨0{|}^{\otimes n}$ 是关于基态 $|0{⟩}^{\otimes n}$ 的反射，不是关于 $|s⟩=H^{\otimes n}|0{⟩}^{\otimes n}$ 的反射。两者差在两侧的 $X^{\otimes n}{H}^{\otimes n}$ 能否与中间因子交换——事实上不能。因此 QASM 版的 Grover 扩散算子并不等于 $2|a⟩⟨a|-I$，它是一个功能上够用、但算符形式不同的东西。这一点在初学资料里几乎总是被含糊过去，而它正是精确扩散算子代价高的根本原因。

QASM 版 Grover 迭代：Oracle + 布尔反射 M（n = 2，a = 00）

图里 M 那段只有五个门，O 那段三个门——这就是为什么教科书里的 Grover 迭代“看起来很便宜”。便宜的原因不是算法简单，而是把求和这一步挪到了算法之外：QASM 线路从不需要知道 $|a_x{|}^2$ 的任何数值。

三、精确扩散算子：反射就是一条求和线路

回到 $2|a⟩⟨a|-I$。按第一节的展开，它的实现流程是：相干地读出 $a$ 的每一个振幅（这需要相干数据访问，即 QRAM 一类的原语），把 $|a_x{|}^2$ 加到一个寄存器上，然后把 $2^n$ 项求和。这个流程对 Grover 搜索与对任意酉 $Q$ 都一样——这正是振幅放大的一般形式 $|a⟩\mapsto Q|0⟩$ 的由来。

代价集中在最后一步，而且是一条硬事实：量子求和没有闭式构造。经典求和可以写成一个矩阵乘法或一次归约扫描，量子侧没有对应的单层电路；已知的最好做法是深度 $O(\log N)$、$O(\log N)$ 辅助比特的分层加法树，常数与 T 数都不小。在允许无界复制的门集下，加法可以达到对数深度（Høyer–Špalek（2003）给出的无界 fan-out 模型就是定义这一可达性的门集），但那是放宽了硬件模型换来的，不能默认套到超导或离子阱线路上。

还有一个理论上的硬要求常被略过：$2|a⟩⟨a|-I$ 是一个酉算符（反射的平方是 $I$），因此任何实现都必须是可逆的。“测出 $a_x$、平方、累加”这条流水线里含有测量，不是酉的；严格实现要么用可逆累加器把测量替换掉，要么承认这条路线是酉的松弛版本。两条路都要额外付辅助比特。

精确扩散算子的结构草图：读出 → 受控平方 → 相干求和（图中为非酉的示意形态）

图中的 acc 宽度值得单独说一句：累加的是 $2^n$ 个无界实数，精度为 $\delta$ 时需要 $n-{\log }_2\delta$ 比特量级的寄存器。扩散算子的比特数与精度成正比，这与 QASM 版只用一个干净辅助比特形成尖锐对比。

四、文献怎么分账

Grover（1996）给出的是数学层面的振幅放大与关于 $|a⟩$ 的反射算符，扩散算子的规范出处就在这里；它并不解决“如何在门模型里实现精确求和”。Brassard–Høyer–Mosca–Tapp（2002）把这件事摆到台面上：它的框架是相干数据访问，把量子计数、极大似然估计与对数精度的查询算法三件事一并处理，代价则是用深度换迭代次数——迭代次数从 $O(1/\sqrt{N})$ 掉到 $O(\log (1/\epsilon ))$，但每一步都更厚。

这条分岔的最终归宿是两条互斥的路线。一条接受 QASM 反射便宜但每步查询多；另一条接受Grinko 等（2021）那条路：不再迭代扩散算子，而是把整个振幅估计重写成固定三个受控旋转的酉分解，从而完全绕开求和——代价是多了一个辅助比特，以及对旋转角精度的要求。amplitude-estimation专门算这笔账。

论文依据

• Grover（1996） —— 扩散算子 $2|a⟩⟨a|-I$ 与振幅放大的规范出处；本词条把它作为算术算符（而非门序列）来解读的依据。
• Brassard–Høyer–Mosca–Tapp（2002） —— 期刊完整版，给出量子计数、极大似然估计与对数精度查询算法；其相干数据访问框架正是“精确扩散依赖相干求和”这一判断的文献来源。
• Grinko 等（2021） —— 用固定三个受控旋转的酉分解替代 Grover 迭代，等于从工程上承认精确扩散太贵；本词条第四节据此收束两条路线。
• Høyer–Špalek（2003） —— 无界 fan-out 门集下算术深度的对数深度可达性；用于说明量子求和的对数深度结论依赖一个放宽的硬件模型。

延伸阅读

• quantum-counting —— 绕开扩散算子、用 QPE 一次读出特征值
• amplitude-estimation —— 三条振幅估计路线的门数/比特数/精度对照
• constant-and-increment-adders —— 受控平方累加器要用的常量加法构造
• arithmetic-circuits-overview —— 原语分类：为什么本算法一项乘法都不需要