加法器谱系

量子加法线路的历史不是一条改良曲线，而是三次范式切换：1995 年 VBE 选择了串行进位（每个比特一根进位线）；2000 年前后 QFT 加法器干脆取消了进位线，改为在傅里叶基里做相位累加；2004 年 CDKM 把进位藏进加数寄存器只需 1 根辅助线，同年 QCLA 用平衡树一次算完所有进位。三条路线分别把代价压在不同资源上，彼此无法换算。本词条给出这套坐标系，并说明每条路线在什么约束下才是对的选择。

三条路线各自的代价

把任何量子加法器放进坐标系，需要三个刻度：辅助比特（$a$）、深度（$d$）、门集。

路线	辅助比特	深度	门集	代表
串行进位（VBE 风格）	$O(n)$	$O(n)$	Toffoli + CNOT	vbe-ripple-carry
MAJ/UMA 进位链（CDKM）	$1$（或 $0$）	$O(n)$	Toffoli + CNOT	cdkm-adder
QFT 加法器（Draper）	$0$	$O(n)$	受控相位旋转	takahashi-qft-adder
Takahashi–Kunihiro QFT 加法器	$0$	$O(n)$	Toffoli + CNOT	takahashi-qft-adder
无界 fan-out QFT 加法器	$O(n/\log n)$	$O(\log n)$	非标准门集	QA006
进位先行（QCLA）	$O(n)$	$O(\log n)$	Toffoli + CNOT	carry-lookahead-adders
无辅助位次线性深度加法器	$0$	$O({\log }^{2}n)$	Toffoli + CNOT	QA011

这张表最值得看的是最左两列的关系：把辅助比特从 $O(n)$ 压到 1，并没有改变 $O(n)$ 深度；而想把深度压到 $O(\log n)$，辅助比特就要付回 $O(n)$。这不是巧合，而是进位本身必须存在某个地方这一事实的直接后果——要么作为一根独立的线（VBE），要么编码在现有寄存器的高位里（CDKM），要么编码在相位里（Draper），要么由 $O(n)$ 个进位辅助位并行承载（QCLA）。

三种”让进位有地方可放”的编码方式

把三条路线摆在一起看，差别只在进位的信息被编码在哪种量子态上：

编码成独立的量子比特。 最直接：进位比特 $c_{i+1}$ 就是一根线上的一个比特。VBE 是这条路线的原型（QA001）。代价是辅助比特 $O(n)$，而且这些比特必须被反计算回零才能交给下游用。

编码进已有的寄存器。 CDKM 的关键观察是第 $i+1$ 位的进位在求和完成后就不再需要，于是可以暂时借用第 $i+1$ 位的加数比特存它，求完和之后再释放。这样整条进位链只留 1 根真正的新辅助线（QA002）。这条路线是当前的事实标准。

编码进相位。 Draper 的 QFT 加法器（QA004）意识到：在傅里叶基里，整数 $x$ 对应一串相位；若把加数 $b$ 按傅里叶系数展开成受控相位门，加法就退化成”给累加器加一份傅里叶展开”。此时进位没有对应的线，它隐含在相位累加的结果里。这是唯一一条比特数低于 $2n$ 的路线，代价是 $O(n^2)$ 个角度随 $2^{-i}$ 变小的受控旋转——精确合成它们在容错模型下非常昂贵。

三种进位编码位置的对照

为什么”哪个最好”没有答案

三个原因，每个都有文献支持。

第一，资源之间不能互相换算。 T 数、深度、辅助比特、魔法态吞吐是四个独立的量（见门代价模型）。QA009 给出了一个具体反例：降低 T 数反而可能抬高总深度；同一篇还指出，用测量替代部分 CNOT 在 NISQ 下可能是划算的。也就是说”少用 T 门”与”跑得快”不是同一句话。

第二，架构约束会改变答案。 在只有一维最近邻连接的机器上，$O(\log n)$ 深度这个目标本身就不成立：QA030 证明 $k$ 维最近邻架构上任何精确加法器的深度下界是 $\Omega (n^{1/k})$。QA029 给出二维 NTC 架构上 $\Theta (\sqrt{n})$ 深度、$O(n)$ 比特的三阶段脉动加法器，并在 $n>58$ 时快于一维版本；QA028 进一步把这个深度从 $140\sqrt{n}$ 压到 $92\sqrt{n}$。

第三，真实资源估算的结论与教科书直觉相反。 QA009 系统地论证了：在相当宽的实用寄存器宽度区间内，进位链比进位先行更省资源。这条结论容易被误读成”进位先行没用”，它真正的含义是：在量子纠错时代辅助比特极贵的背景下，$O(\log n)$ 深度换 $O(n)$ 辅助比特往往不划算。这正是 negadd 方案（negadd-and-subtraction）在真实资源估算里胜出的原因。

结构 vs 阶梯：一个新的统一视角

QA010 提供了一个有用的分析框架：把文献里各种加法器拆成两个可独立选择的正交因子——

1. 进位结构（2 选 1）：串行进位（ripple-carry）还是进位先行（carry-lookahead）；
2. Toffoli 阶梯实现（3 选 1）：无辅助位线性深度、无辅助位多对数深度（$O({\log }^{2}n)$）、有辅助位对数深度。

$2\times 3=6$ 种组合，其中 4 种是已知设计，2 种是新设计。这个视角的价值在于：它解释了为什么不同论文里的”改进了”看起来毫不相干——它们改的其实是这两个因子中的某一个。

一个必须知道的物理限制

QA020 证明了一件事，值得在分类时就想清楚：不存在能够对未知量子态做加法的酉，即使基底已知、即使允许辅助系统也不行（这与不可克隆定理同源）；甚至在无辅助系统时，对已知正交基做加法同样被禁止。这条限制解释了两件事：一是为什么所有实用加法器都只在计算基（叠加态整体）上工作，而不是逐态加；二是为什么”省掉辅助比特”的努力往往以增加深度为代价——辅助比特本质上承担了”跨态传递信息”的角色。

论文依据

• Vedral–Barenco–Ekert 1995 —— 给出第一个显式的从加法到模幂的量子网络，并指出可逆模幂所需的辅助内存随被分解数规模线性增长；本词条的”显式进位线”路线即出自此文。
• Draper 2000 —— 提出把加数编码进累加器傅里叶基的加法方法，去掉了临时进位比特的需要；本词条”进位编码进相位”一路线的原始出处。
• Cuccaro–Draper–Kutin–Moulton 2004 —— 给出只需 1 个辅助比特、线性深度的新进位链加法器；本词条”进位编码进已有寄存器”一路线的原始出处。
• Takahashi–Kunihiro 2005 —— 线性规模的 QFT 加法器且不需要辅助比特，说明”无辅助位 + 纯经典可逆门”是可行的。
• Takahashi–Tani–Kunihiro 2009 —— 证明一旦允许无界 fan-out 门，对数深度加法（乃至 $O({\log }^{\ast }n)$）即成为可能，但辅助比特降到 $o(n)$；本词条据此说明”对数深度”与”标准门集”不能同时要求。
• Draper–Kutin–Rains–Svore 2004 —— 定义 QCLA 族，$O(\log n)$ 深度配 $O(n)$ 辅助比特；本词条”进位先行”路线的原始出处。
• Remaud–Vandaele 2025 —— 首个精确的无辅助位次线性（$O({\log }^{2}n)$）深度加法器；本词条对照表中最后一行。
• Remaud 2025 —— 把文献中的加法器统一为 2 种进位结构 × 3 种 Toffoli 阶梯实现 = 6 种；本词条”结构 vs 阶梯”一节的全部依据。
• Paler–Oumarou–Basmadjian 2021 —— 实证表明降低 T 数可能抬高深度，并系统论证在实用宽度区间内进位链优于进位先行；本词条”为什么没有唯一最优”的核心证据。
• Choi–Van Meter 2008 —— 证明 $k$ 维最近邻架构上精确加法器的深度下界为 $\Omega (n^{1/k})$；本词条架构约束论证的依据。
• Choi–Van Meter 2010 —— 二维 NTC 架构上 $\Theta (\sqrt{n})$ 深度、$O(n)$ 比特的脉动式加法器，$n>58$ 时优于一维。
• Saeedi–Shafaei–Pedram 2013 —— 把二维最近邻加法器总深度从 $140\sqrt{n}$ 降到 $92\sqrt{n}$。
• Alvarez-Rodriguez 等 2014 —— 证明不存在对未知量子态做加法的酉，无辅助系统时对已知正交基的加法亦被禁止；本词条物理限制一节。

延伸阅读

• cdkm-adder —— 本卷的事实标准，值得单独精读
• adder-resource-comparison —— 把本词条的定性结论变成可查的表
• negadd-and-subtraction —— 减法在文献里的真实做法
• 门代价模型 —— 为什么这四个刻度不能换算
• 数值格式卷 —— 定点/浮点里”选哪种加法器”是第一个被放大的决定