CDKM 精简加法器

CDKM 论文（QA002）只占 9 页，却给出了此后二十年量子加法的事实标准：把”进位”这个必须存在的中间量，从一根独立的新辅助线，改为临时占用加数寄存器自己的比特。这一改动把辅助比特从 $O(n)$ 压到 1，深度仍是 $O(n)$，而且只用 Toffoli 与 CNOT。本词条讲清这套 MAJ/UMA 结构到底在做什么、为什么”借位”是合法的，以及后续所有 negadd、分块先行、无辅助位次线性深度设计如何都以它为骨架。

问题的提法

设要算 $a+b$，其中 $a,b$ 均为 $n$ 比特，输出到一个独立寄存器 $z$（out-of-place 形式）；还有一种形式是就地加，$b$ 直接变成和（in-place）。逐位来看，第 $i$ 位需要的是

$$s_i=a_i\oplus b_i\oplus c_i,c_{i+1}=\mathrm{maj}(a_i,b_i,c_i),$$

其中 $c_0$ 是进位入，$c_n$ 是进位出。麻烦在于：$c_{i+1}$ 必须先算出来才能算 $s_{i+1}$，形成串行依赖；而若为每个 $c_i$ 单独开一根辅助线（VBE 方案），辅助比特就是 $O(n)$。

CDKM 的观察是：第 $i$ 位的加数比特 $b_i$ 在第 $i$ 位的和算完之后就不再需要了。所以可以让 $c_{i+1}$ 暂时住在 $b_{i+1}$ 上，等第 $i+1$ 位求完和再把它释放出来。整条链因此只需要 $c_0$ 那一根真正的辅助比特（还可以让 $b$ 自己在 $c_0$ 为 0 时充当它，从而做到零辅助）。

MAJ 与 UMA：谁把什么送到哪根线

整套结构由两个 2 比特门构成，它们作用在相邻的三根线 $(a_i,b_i,c_i)$ 上：

MAJ（majority，2 个 CNOT + 1 个 Toffoli） 做三件事：

• 把 $b_i$ 变成 $a_i\oplus b_i$；
• 把 $c_i$ 变成 $\mathrm{maj}(a_i,b_i,c_i)$——也就是把行进位写进 $c$ 这根线上；
• 顺带修正 $b_i$ 的一个条件翻转，使得当进位条件成立时 $b_i$ 恰好是 $b_i\oplus a_i\oplus 1$。

MAJ 之后的状态是不确定的（含有不可分解的纠缠），但每一位的进位已经正确地落在了对应的 $b_{i+1}$ 位置上。这就是”借位”。

UMA（un-majority，1 个 CNOT + 1 个 Toffoli） 是 MAJ 的逆运算加上一个异或。逐位执行时，它把暂存在 $b_{i+1}$ 里的进位取出来，与 $a_{i+1}$ 异或得到和比特 $s_{i+1}=a_{i+1}\oplus b_{i+1}\oplus c_{i+1}$，然后把 $c_{i+1}$ 归位到辅助线上，同时恢复 $b_i$ 的原值（如果它被借用过）。

关键的时序安排是：MAJ 链从低位到高位顺序执行（每一位依赖前一位留下的进位），UMA 链从高位到低位逆序执行。这样进位在整条链上只流动一遍，不需要任何一根专门的进位线去承载 $n$ 个中间值——只有链条两端各有一根线。

CDKM：MAJ 链正序、UMA 链逆序

为什么这不是”计算态”

MAJ 之后整条线路处于不可分解的叠加态，不能读出任何一个比特。这一点在原理上很重要，因为常见误解是”先进位链、再读进位、然后照着进位加”——那样就退化成测量-重置-条件操作的经典模式，破坏叠加态。

CDKM 的做法是全程酉的：进位信息被摊开分布在多根线上，直到 UMA 阶段才在每一步局部地把第 $i$ 位的进位重新聚合回那一位的受控操作里。理解这一点，就理解了为什么整个加法器可以作用在任意叠加态上而不需要”读出”。

变体与后续

CDKM 原论文讨论的是基本形式。此后文献围绕它长出一批变体，值得知道存在：

• 就地（in-place）与就地取负（negadd）。negadd 把 $b$ 原地变成 $b-a$，是negadd-and-subtraction的主体。
• 模 $2^n$ / 带进位入的变体。模 $2^n$ 加法就是丢弃 $c_n$；带进位入就是令 $c_0=1$。这些变体在 Shor 的模幂里高频出现。
• T 数与深度的最优化。QA025 系统地优化了进位链加法器与比较器的 CNOT/T 数与深度；QA033 从图傅里叶变换（ZX↔ZH）的角度重新推导并推广了 Toffoli 加法器已知的 T 成本削减技巧。

结构上的推广。QA010 给出一个统一视角：把文献里的加法器拆成两个正交因子——2 种进位结构（ripple-carry / carry-lookahead）× 3 种 Toffoli 阶梯实现（无辅助位线性深度、无辅助位 $O({\log }^{2}n)$ 深度、有辅助位对数深度）= 6 种加法器。CDKM 是其中最基础的一格。

深度的改进。CDKM 的深度仍是 $O(n)$。三类改进各有代表：

• 分块先行：QA014 把比特分组为大小 $b$ 的块，out-of-place 形式 Toffoli 数 $3n+5n/b$、in-place 形式 $5n+8n/b$，代价是反应深度随 $b$ 线性增长且需额外工作区。
• 无辅助位次线性深度：QA011 把 $n$ 个 CNOT 的”阶梯”换成 $O(\log n)$ 深度的线路、$n$ 个 Toffoli 的阶梯换成 $O({\log }^{2}n)$ 深度，得到首个精确无辅助位次线性深度加法器。
• 对数深度：QA037 给出 Toffoli 深度 $\log n+\log \log n+O(1)$、仅 $O(n)$ 辅助位的进位先行加法器，并强调它天然兼容二维最近邻架构。

一个必须保留的分歧

CDKM 深度 $O(n)$、辅助比特 $1$；进位先行深度 $O(\log n)$、辅助比特 $O(n)$。哪个更好？这取决于比特是否稀缺，且不要选边站。QA009 在量子比特是稀缺资源的假设下系统论证：在相当宽的实用寄存器宽度区间内，进位链比进位先行更省资源；同时指出降低 T 数可能反而抬高总深度。QA014 则从另一侧给出证据：当魔法态工厂数量有限时，反应深度随块大小 $b$ 线性增长这件事会成为实际瓶颈，从而改变低深度设计的价值。

论文依据

• Cuccaro–Draper–Kutin–Moulton 2004 —— 本词条的主体来源。提出线性深度、只需单个辅助比特的新进位链加法器，并指出其深度与门数都低于此前的进位链加法器。MAJ/UMA 结构与借位思想即出自此文。
• Vedral–Barenco–Ekert 1995 —— 提供对照基线：此前的进位链方案需要线性多个辅助比特。
• Gidney–Ekerå 2019 —— 在 negadd 与无辅助工作区的模幂线路上给出可核验的资源口径（$n$ 比特 RSA 用 $3n+0.002n\lg n$ 逻辑比特、$0.3n^3+0.0005n^3\lg n$ 个 Toffoli），说明 CDKM 这类低辅助设计为何能在端到端估算里胜出。
• Remaud 2025 —— 把 Toffoli 阶梯的 3 种实现方式与 2 种进位结构交叉，给出 6 种加法器的统一分类；本词条”结构上的推广”一节。
• Remaud–Vandaele 2025 —— 给出 CNOT 阶梯 $O(\log n)$、Toffoli 阶梯 $O({\log }^{2}n)$ 的低深度实现，据此得到首个精确无辅助位次线性深度加法器。
• Gidney 2020 —— 分块先行加法器：out-of-place $3n+5n/b$、in-place $5n+8n/b$ 个 Toffoli，并建模魔法态工厂数量对时空代价的影响。
• Gu 等 2025 —— Toffoli 深度 $\log n+\log \log n+O(1)$、$O(n)$ 辅助位的进位先行加法器，且兼容二维最近邻架构。
• Remaud 2024 —— 对进位链加法器与比较器做 Clifford+T 下的 CNOT/T 数与深度最优化。
• Wang 等 2016 —— 针对超导平台约束降低 CDKM 式进位链加法器的门成本。
• Kuijpers–van de Wetering–Kissinger 2019 —— 从 ZX↔ZH 图傅里叶变换推导并推广 Toffoli 加法器（含 CDKM 一族）已知的 T 成本削减技巧。
• Paler–Oumarou–Basmadjian 2021 —— 提供”进位链 vs 进位先行”的实证对照，以及 T 数与深度不可互换的具体反例。
• Alvarez-Rodriguez 等 2014 —— 指出为什么辅助比特不可省：不存在对未知量子态做加法的酉，无辅助系统时对已知正交基的加法亦被禁止。

延伸阅读

• majority-uma-uncompute —— 把 MAJ/UMA 的内部结构拆开讲
• negadd-and-subtraction —— CDKM 的就地取负形式
• adder-resource-comparison —— 该选 CDKM 还是别家
• quantum-full-adder —— 模块级的对应物：PPKN 保输入全加器