进位先行加法器

进位先行是量子加法器里唯一以 $O(\log n)$ 深度为目标的一族。它的核心想法与经典进位先行完全一致：把进位分解为 generate（该位产生进位）与 propagate（该位传递进位）两个信号，在这两个信号上跑一棵平衡二叉树，一次算出全部 $n$ 个进位。代价写在账单上——$O(n)$ 根辅助比特。本词条讲清这棵树怎么搭、代价从哪来，以及近十年在测量基、高基数、最优 Toffoli 深度、二维架构兼容等方向上的具体结果。

generate / propagate / kill

三个信号把第 $i$ 位的局部行为拆开：

$$g_i=a_i\wedge b_i,p_i=a_i\oplus b_i,k_i=a_i\oplus b_i\oplus 1.$$

• $g_i$（generate）：本位两个加数都是 1，必定产生进位；
• $p_i$（propagate）：本位两数不同，进位是否产生取决于低位；
• $k_i$（kill）：本位两数都是 0 且不传递，进位必被清零。

于是一个区间的进位是它内部 generate 信号的前缀或：

$$C_j=\underset{i<j}{\bigvee }(g_i\wedge {\bigwedge }_{i<k<j}{p}_k),$$

即”最近一个 generate，及其后连续的 propagate”。这正是可以用平衡树并行计算的形式——每层把两个相邻区间的 $(g,p)$ 对合并，$\lceil {\log }_{2}n\rceil$ 层后全部前缀可得。QA003 摘要明确说明该工作借鉴了经典进位先行算术线路的技术，并给出 in-place 与 out-of-place 两个版本，以及模 $2^n$ 与模 $2^n-1$ 的版本。

QCLA：平衡二叉树并行归约 generate/propagate

$O(n)$ 辅助比特从哪来

树的每一层都要把合并结果保存下来供下一层读取。$n$ 个信号、$O(\log n)$ 层，若每层都留一份就是 $O(n\log n)$；实践中按层复用得到 $O(n)$。QA037 的一句话点明了这条线的痛点：他们的设计避免了已有方法的 $O(n\log n)$ 空间开销——说明这个数字确实是这一族的历史包袱。

这也解释了 QA009 那个反直觉结论的机制：进位先行用 $O(n)$ 辅助比特换 $O(\log n)$ 深度，而在量子比特稀缺的前提下，这个交换常常不划算。该文因此系统论证了在一段实际重要的宽度区间内进位链更省资源。

变体一：测量基 QCLA

QA017 指出一个具体问题：QCLA 原本为”支持长距离通信的抽象并发架构”设计，而多数现实架构严格限制通信距离。测量基量子计算（MBQC）提供了一个绕法——利用”单位时间传态”能力加速。

结果：MBQCLA 在仅最近邻的架构上达到 $\Theta (\log n)$ 深度，突破了线性最近邻架构上 $\Theta (n)$ 的加法深度限制；寄存器超过 100 比特时比进位链快一个数量级。代价写得很清楚——需要的簇态规模大一个数量级。资源分类后，未优化形式里约 88% 用于通信；手工优化水平通信成本后，就地 MBQCLA 的空间资源减少约 12%；作为对照，图态版 QCLA（GSQCLA）只用到 MBQCLA 约 9% 的空间资源。

变体二：高基数与最优 Toffoli 深度

高基数。 QA016 在 QCLA 里引入高基数层，把进位按基数 $r$ 分组：$O(n)-O(n/r)$ 比特、$O(n)+O(n/r)$ 个 T 门、T 深度 $O(r)+O(\log (n/r))$。论文在 T 深度、T 数、比特数三个维度上比较后认为优于既有 QCLA，并且在 T 数上仍优于 Draper 的 out-of-place 加法器——即使后者比特数极省。

最优 Toffoli 深度。 QA015 系统穷举了 160 种进位传播组合，指出此前的对数深度量子加法器都带常数系数 $k\ge 2$（Toffoli 深度 $k\log n+O(1)$），而精确的 $\log n+O(1)$ 是可达的。相比已知最好的加法器，Toffoli 深度降低近 50%。该文还展示了采用不同 propagate/generate 展开的进一步设计，以及向模运算框架的扩展。

新的组合维度。 QA010 给出一个统一视角：进位结构只有两种（ripple-carry 与 carry-lookahead），Toffoli 阶梯只有三种实现（无辅助位线性深度、无辅助位多对数深度、有辅助位对数深度），交叉得 6 种加法器——其中 2 种是新设计，且其中一种是胜过既有方法的进位先行加法器。这提示”改进进位先行”未必需要新结构，可能只是换一种阶梯实现。

Kronecker 前缀和。 QA036 走的是把前缀和当线性代数问题：下三角全 1 矩阵可分解为两个 Kronecker 积之和，由此设计递归前缀和线路族，得到 Toffoli 深度 $1.893\log n+O(1)$、$O(n)$ 个 Toffoli、$O(n)$ 额外比特。这是第一个同时满足零冗余、每层常数 fan-out、深度渐近严格小于 $2\log n$ 三性质的构造（详见kutin-parallel-prefix）。

变体三：模 $2^n-1$ 与二维架构

QA035 给出对数深度的进位先行 mod $(2^n-1)$ 加法器（QCLMA），并特意把进位路径做成树结构而非链结构以增强抗错；相对已有 $O(n)$ 深度的工作，4 比特模加实验的 QSFR 提升 47.21%。

QA037 则给出 Toffoli 深度 $\log n+\log \log n+O(1)$、仅 $O(n)$ 辅助位的进位先行加法器，强调它天然兼容二维最近邻架构且只引入常数因子开销。该文用它做了 Shor 椭圆曲线算法的完整资源分析，结论是攻破 NIST P-256 约需 4300 个逻辑比特、逻辑 Toffoli 保真度约 $10^{-9}$。

架构约束不可忽略

QA030 的结论对这一族是硬约束：任何 $O(\log n)$ 深度的加法器映射到只支持最近邻的 $k$ 维架构上时，深度下界不再是 $\Omega (\log n)$ 而是 $\Omega (n^{1/k})$。这是首次把图嵌入用于量子线路与器件分析。实践中的对应结果是 QA029 的二维脉动方案——三阶段工作（第一列生成和输出、其余列做进位先行；列间传播中间值；各列用列级进位生成自己的和输出），$\Theta (\sqrt{n})$ 深度、$O(n)$ 比特，$n>58$ 时快于一维版本；QA028 再把其总深度从 $140\sqrt{n}+k_1$ 优化到 $92\sqrt{n}+k_2$。

选型速查

约束	建议
比特稀缺	回到进位链，见 QA009 的实证
深度是瓶颈且比特充裕	QA037 或 QA016 的高基数版本
只要 T 数最优	QA015（$\log n+O(1)$ Toffoli 深度）与 QA016
仅有最近邻连接	QA029 / QA028（二维）或 QA017（测量基）
NISQ 上做模加	QA035，注意其结论来自 4 比特实验

论文依据

• Draper–Kutin–Rains–Svore 2004 —— QCLA 族的定义性工作：$O(\log n)$ 深度、$O(n)$ 辅助比特，借鉴经典进位先行技术，提供 in-place / out-of-place 与模 $2^n$ / 模 $2^n-1$ 版本；论文指出这是在仅略微增加比特数的代价下大幅降低加法成本，并可用于缩短 Shor 的运行时间。
• Trisetyarso–Van Meter 2009 —— 测量基 QCLA（MBQCLA）：在最近邻架构上达到 $\Theta (\log n)$ 深度、100 比特以上快一个数量级，代价是簇态大一个数量级、未优化形式约 88% 资源用于通信、就地版手工优化后省约 12%、图态版 GSQCLA 只用约 9% 空间资源。
• Wang 等 2024 —— 穷举 160 种进位传播组合，证明精确 $\log n+O(1)$ 的 Toffoli 深度可达，比已知最好结果降低近 50%；并给出 propagate/generate 展开与模框架扩展。
• Wang–Baksi–Chattopadhyay 2023 —— 高基数 QCLA：$O(n)-O(n/r)$ 比特、$O(n)+O(n/r)$ T 门、T 深度 $O(r)+O(\log (n/r))$；在 T 数上亦优于 Draper out-of-place 加法器。
• Remaud 2025 —— 2 种进位结构 × 3 种 Toffoli 阶梯实现的统一分类，产出 6 种加法器（含 2 种新设计，其中一种进位先行设计优于既有方法）。
• Sobczyk–Zouzias 2025 —— Kronecker 积前缀和线路，Toffoli 深度 $1.893\log n+O(1)$、$O(n)$ Toffoli、$O(n)$ 额外比特。
• Gu 等 2025 —— Toffoli 深度 $\log n+\log \log n+O(1)$、$O(n)$ 辅助位、避免 $O(n\log n)$ 空间开销且兼容二维最近邻架构的加法器；并给出 P-256 约 4300 逻辑比特、逻辑 Toffoli 保真度约 $10^{-9}$ 的端到端估算。
• Gaur–Muñoz-Coreas–Thapliyal 2024 —— 对数深度的进位先行 mod $(2^n-1)$ 加法器，树形进位路径；4 比特模加 QSFR 提升 47.21%。
• Paler–Oumarou–Basmadjian 2021 —— 在比特稀缺前提下实证进位链优于进位先行，是本族选型时必须并读的反向证据。
• 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$。

延伸阅读

• kutin-parallel-prefix —— 前缀扫描在量子线路下的困难
• cdkm-adder —— 竞品：辅助比特最省
• adder-resource-comparison —— 把这些数字放进同一张表
• hybrid-adders —— QFT 与进位结构的门级互变换