加法器资源对比

"哪种加法器最好"这个问题之所以没有唯一答案，是因为它至少要分五个刻度回答：比特数、深度、T 数、魔法态吞吐、连接性约束。本词条把这些刻度分开排列，给出每个刻度下的证据方向，并特别标注一个容易被误读成"进位先行无用"的结论——QA009 实际说的是"在比特稀缺、且宽度处于实用区间的条件下，进位链更省资源"，它是有条件的，不是绝对的。

五个刻度

比较加法器时，先问清楚比的是哪个量。四个成本量在物理上不能互相换算（见门代价模型），而连接性是架构施加的硬约束，不是成本。

刻度	谁占优	证据
比特数	QFT 加法器（Draper 系）唯一低于 $2n$	QA004、QA018
辅助比特	CDKM（1 根）与其无辅助位变体（0 根）	QA002、QA005、QA011
深度（全连通）	进位先行 $O(\log n)$；无界 fan-out 下可到 $O({\log }^{\ast }n)$	QA003、QA006
深度（受限连接）	下界 $\Omega (n^{1/k})$，最优为二维 $\Theta (\sqrt{n})$	QA030、QA029
T 数 / Toffoli 数	QFT 与最省 Toffoli 加法”根本相同”；高基数 QCLA 更优	QA007、QA016、QA015
魔法态吞吐	低 Toffoli 数优先，受工厂数量限制时进位链占优	QA014
架构兼容	脉动式（二维）与测量基 QCLA	QA029、QA017

主表：三条路线的资源画像

加法器	辅助比特	深度	门集	关键出处
VBE 进位链	$O(n)$	$O(n)$	Toffoli + CNOT	QA001
CDKM 进位链	1（或 0）	$O(n)$	Toffoli + CNOT	QA002
Takahashi–Kunihiro QFT	0	$O(n)$	Toffoli + CNOT	QA005
Takahashi–Tani–Kunihiro QFT	$O(n/\log n)$	$O(\log n)$；无界 fan-out 下 $O({\log }^{\ast }n)$	含非标准门	QA006
Draper QFT 加法器	0	$O(n)$	受控相位旋转	QA004
QCLA	$O(n)$	$O(\log n)$	Toffoli + CNOT	QA003
最优 Toffoli 深度 QCLA	$O(n)$	$\log n+O(1)$	Toffoli	QA015
高基数 QCLA	$O(n)-O(n/r)$	T 深度 $O(r)+O(\log (n/r))$	Toffoli + T	QA016
Kronecker 前缀和加法器	$O(n)$	Toffoli 深度 $1.893\log n+O(1)$	Toffoli	QA036
二维脉动 QCLA	$O(n)$	$\Theta (\sqrt{n})$	Toffoli + CNOT	QA029、QA028
分块先行	额外工作区	随块大小 $b$ 线性增长	Toffoli	QA014
无辅助位次线性深度加法器	0	$O({\log }^{2}n)$	Toffoli + CNOT + X	QA011
无辅助位进位先行型新加法器	0	未给出具体式	经典可逆门	QA025
分段近似加法器	$o(n)$	$O(\lg \lg n)$	经典可逆门	QA026
常数加法器	$n-3$（就地）/ $n-2$（受控）	线性	Toffoli	QA013
经典–量子加法器	3 洁净（或 2 洁净 + $n-2$ 脏）	线性	Toffoli	QA034
比较器 / 递增器	可证最小	$\Theta (\log n)$	Clifford + Toffoli	QA012

（QA 编号在本文中作为可核验文献标识使用；对应文献页见 sources/ 目录。）

争议点一：进位链 vs 进位先行

这是本卷最值得完整记录的分歧，因为答案与教科书直觉相反。

证据 A（支持进位链）。QA009 在量子比特稀缺的前提下给出系统论证：在一段实际重要的线路宽度区间内，进位链比进位先行更省资源。机制很清楚——进位先行用 $O(n)$ 辅助比特换 $O(\log n)$ 深度，而辅助比特在量子纠错时代是最贵的。

证据 B（支持进位先行）。QA014 从魔法态侧给出反向压力：当魔法态工厂数量有限时，分块先行加法器（out-of-place 形式 $3n+5n/b$ 个 Toffoli，in-place 形式 $5n+8n/b$ 个）的反应深度随块大小 $b$ 线性增长会成为实际瓶颈。这改变了低深度设计的价值。

证据 C（支持进位先行，但有条件）。QA037 的进位先行加法器把 Toffoli 深度做到 $\log n+\log \log n+O(1)$，辅助位仅 $O(n)$，避免了已有方法的 $O(n\log n)$ 空间开销，并兼容二维最近邻架构——端到端结果是攻破 NIST P-256 约需 4300 个逻辑比特、逻辑 Toffoli 保真度约 $10^{-9}$。

准确的结论口径：QA009 的结论是有条件的——条件是比特稀缺与实用宽度区间；QA037 说明当比特约束放宽、或架构本身支持并行时，进位先行可以重新占优。两条并不矛盾，因为它们回答的是不同约束下的问题。引用”进位链优于进位先行”时应连同条件一起引用。

争议点二：T 数与深度不可互换

QA009 给出两个必须记住的方法论结论：

• 降低 T 数可能抬高总深度。 一个 T 数更省的分解未必更快，因为最优的 T 数分解往往深度更大。
• 测量可以换 CNOT。 在 NISQ 线路里这可能是有利的。

同一篇还指出：测量基反计算相对相位 Toffoli 辅助位最多可占整条线路深度的 30%——这意味着”加法器多深”与”整个算法跑多久”之间有一个不容忽视的连接项。

推论：任何只报 T 数不报深度的加法器对比都是不完整的。

争议点三：架构会改变一切

深度下界。QA030 证明 $k$ 维最近邻架构上精确加法器的深度下界是 $\Omega (n^{1/k})$，而不是 $O(\log n)$。任何以 $\log n$ 为目标的方案在受限连接上都需要额外机制。

二维实现。QA029 的三阶段脉动方案做到 $\Theta (\sqrt{n})$ 深度、$O(n)$ 比特，并在 $n>58$ 时快于一维版本。QA028 再把其总深度从 $140\sqrt{n}+k_1$ 优化到 $92\sqrt{n}+k_2$。

测量基绕行。QA017 用 MBQC 的”单位时间传态”能力让 QCLA 在最近邻架构上达到 $\Theta (\log n)$ 深度，100 比特以上比进位链快一个数量级；代价是簇态规模大一个数量级，未优化形式约 88% 资源用于通信，图态版（GSQCLA）只用到约 9% 的空间资源。

端到端才有意义。QA037 是把加法器放进完整算法里评估的例子（椭圆曲线 Shor）；QA008 与 QA031 是 RSA 分解的两个版本，都把加法器选择与架构假设绑定：前者用 negadd 与无辅助工作区，给出 $3n+0.002n\lg n$ 逻辑比特、$0.3n^3+0.0005n^3\lg n$ 个 Toffoli 的抽象模型口径；后者在相同物理假设下把比特降到百万以下、运行时间延到一周以上。

决策流程

给定一个真实约束集，按下面的顺序走：

1. 先定架构。 只有最近邻？→ 看 QA029 / QA028（二维）或 QA017（测量基）。否则进入第 2 步。
2. 再定比特预算。 辅助位可忽略？→ QFT（QA004、QA005）或无辅助位次线性深度方案（QA011）。比特极紧张？→ CDKM（QA002）或 negadd 路线（QA008）。
3. 然后定深度目标。 深度是瓶颈且比特已解决？→ 进位先行（QA003、QA015、QA016、QA037）。
4. 最后定计账口径。 T 数够吗？→ 若关心 T 数，比较 QA007 的翻译结果与 QA016 的高基数 QCLA。若同时关心魔法态吞吐 → QA014。若接受误差 → QA018 / QA019（分带）、QA026（$O(\lg \lg n)$）、QA027（NISQ 近似）。
5. 最后一步：端到端验算。 把选型放进完整算法估算（QA008、QA031、QA037 是三个可核验的范例）。

两个必须保留的限定

• 无界 fan-out 不是标准门集。 QA006 的 $O(\log n)$、乃至 $O({\log }^{\ast }n)$ 深度结果依赖无界 fan-out 门；这类门会改变经典模拟的复杂度性质，结论不能直接搬到标准门模型。
• 辅助比特在原理上不可完全消除。 QA020 证明不存在对未知量子态做加法的酉，且无辅助系统时对已知正交基的加法亦被禁止。所有”零辅助位”方案都依赖巧妙的条件化或近似，而非绕过该原理限制。

论文依据

• Paler–Oumarou–Basmadjian 2021 —— 本词条两个核心争议的共同依据：进位链在实用宽度下优于进位先行；降低 T 数可能抬高深度；测量可换 CNOT；测量基反计算占深度至多 30%。
• Gidney 2020 —— 分块先行加法器（$3n+5n/b$ 与 $5n+8n/b$ 个 Toffoli）与魔法态工厂数量对时空代价的影响；争议点一的证据 B。
• Gu 等 2025 —— Toffoli 深度 $\log n+\log \log n+O(1)$、$O(n)$ 辅助位、避免 $O(n\log n)$ 空间开销、兼容二维架构；并给出 P-256 约 4300 逻辑比特、保真度约 $10^{-9}$ 的端到端估算。争议点一的证据 C。
• Wang 等 2024 —— 160 种进位传播组合的穷举，证明精确 $\log n+O(1)$ Toffoli 深度可达，较已知最好结果降低近 50%。
• Wang–Baksi–Chattopadhyay 2023 —— 高基数 QCLA 的比特/T 数/T 深度口径；T 数上优于 Draper out-of-place 加法器。
• Sobczyk–Zouzias 2025 —— Kronecker 前缀和加法器的 $1.893\log n+O(1)$ Toffoli 深度。
• Remaud–Vandaele 2025 —— 首个精确无辅助位次线性深度（$O({\log }^{2}n)$）加法器。
• Remaud 2025 —— 2 种进位结构 × 3 种 Toffoli 阶梯实现 = 6 种加法器的统一分类，含 2 种新设计。
• Takahashi–Tani–Kunihiro 2009 —— 无辅助位 $O(n)$ 深度（规模 $7n-6$）构造，以及无界 fan-out 下 $O(\log n)$ / $O({\log }^{\ast }n)$ 深度的结果与其门集代价。
• 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}+k_1$ 降到 $92\sqrt{n}+k_2$。
• Trisetyarso–Van Meter 2009 —— 测量基 QCLA 的深度、簇态规模与资源分类（88% 通信、GSQCLA 约 9%）。
• Gidney–Ekerå 2019 —— negadd 与无辅助工作区模幂线路的端到端资源口径。
• Gidney 2025 —— 同架构假设下比特降到百万以下、运行时间延长到一周以上的更新，以及比特/时间变化的来源分解。
• Fedoriaka 2025 —— 常数加法器的 $n-3$ 辅助位 / $4n-5$ T 数与受控版 $n-2$ / $11n-15$。
• Gidney 2025 —— 经典–量子加法器：3 洁净辅助位 + $4n\pm O(1)$ Toffoli，以及 $3n\pm O(1)$ 的脏辅助位版本。
• Vandaele 2026 —— 比较器/递增器的 $\Theta (n)$ 门、$\Theta (\log n)$ 深度与可证最小比特数；含”用控制比特换辅助比特”的低开销定理。
• White–Hill–Hollenberg 2021 —— 截断/分带的误差由进位借位率给出，RSA-2048 下可截断到 $\pi /64$，相位加法器可与 Toffoli 构造竞争。
• Agrawal 等 2023 —— qudit 情形下受控旋转数的解析上界，以及有噪声时分带的常数深度近似线路更优。
• Gidney 2019 —— 分段加法器把深度降到 $O(\lg \lg n)$ 及其误差界。
• Gaur–Humble–Thapliyal 2024 —— NISQ 近似加法器（含零深度与 $O(1)$ 深度设计）在五种噪声模型下的保真度提升区间。
• Paler 2022 —— QFT 加法与最省 Toffoli 加法在容错成本（如 T 数）上根本相同。
• Schober–Wesley 2026 —— QFT 与进位链之间的门级转译，以及无辅助位的进位先行型新设计。
• Cuccaro–Draper–Kutin–Moulton 2004 —— 单辅助比特、线性深度的进位链基线。
• Takahashi–Kunihiro 2005 —— 无辅助比特的线性规模 QFT 加法器。
• Draper 2000 —— 比特数低于 $2n$ 的相位加法器。
• Vedral–Barenco–Ekert 1995 —— $O(n)$ 辅助比特的进位链基线。
• Alvarez-Rodriguez 等 2014 —— 辅助比特不可完全消除的原理限制。

延伸阅读

• adder-taxonomy —— 本词条各条目的详细论证
• cdkm-adder —— 比特最省方案
• carry-lookahead-adders —— 深度最优方案
• 门代价模型 —— 为什么五个刻度不能互相换算