MAJ/UMA 与反计算

CDKM 加法器之所以省辅助比特，全在两个 2 比特门的分工上。MAJ 把行进位写进加数寄存器的高位，UMA 再把它取出来变成和比特并把低一位还原。本词条把这对结构拆到门级，讲清三件事：借位为什么在可逆计算里合法、为什么整条链全程不需要读出任何中间量、以及一个被低估的成本——结束时把辅助位与借过的比特全部归零的反计算段，在真实估算里能占到整条线路深度的三成。

借位为什么合法

在量子线路里”临时占用”一个比特，前提是这个比特在占用期间确实不再承载别的信息，且最终能被精确还原。这是可逆计算里的标准手法，关键在于时序：第 $i+1$ 位的加数 $b_{i+1}$ 在第 $i$ 位求完和 $s_i$ 之后确实不再需要，而第 $i+1$ 位求和需要的正是那个进位。

把 MAJ 链安排成从低位到高位正序、UMA 链安排成从高位到低位逆序，进位就只沿链流动一遍。任何别的排列都会要求某处同时存在两个进位，那时才需要额外的线——CDKM 的全部技巧就是让这种情形永不发生。

逐位追踪一位

考虑三根线 $(a,b,c)$，$c$ 是当前携带的进位。先看 MAJ 的三个动作（2 个 CNOT + 1 个 Toffoli）：

动作	作用
$\mathrm{CX}(a\to b)$	把 $b$ 变成 $a\oplus b$
$\mathrm{CCX}(a,c\to b)$	在 $a\wedge c$ 时翻转 $b$，使 $b$ 变为 $a\oplus b\oplus c$
$\mathrm{CCX}(a,b\to c)$	把 $c$ 变成 $\mathrm{maj}(a,b,c)$

第三行是关键：行进位被送到了 $c$ 线上。此时 $c$ 不再是旧进位，而是新进位 $\mathrm{maj}(a,b,c)$。在链上，这个位置对应第 $i+1$ 位的进位槽位，于是”进位”这件事被顺次推到了下一位。

UMA 是这三步的逆序（$\mathrm{CCX}$、$\mathrm{CX}$、$\mathrm{CCX}$）再跟一个异或。逆序执行的意义在于：正序做完 MAJ 后状态纠缠、不可读；逆着走 UMA，每一步都在”上一位的进位已经到位”的前提下把本位和算出来：

$$s=a\oplus b\oplus c,$$

而 $c$ 恰好就是该位的进位。UMA 结束时，$b$ 恢复原值，$c$ 也归位。

单比特 MAJ 与 UMA 的门级分解

注意 MAJ 之后 $b$ 处于 $a\oplus b\oplus c$ 而不是 $a\oplus b$：那次受控非门正是”借位标记”。链式执行时，每一位借走的痕迹会在下一轮 UMA 中被撤销，最终 $b$ 恢复原值——若用的是就地加法形式，恢复后的 $b$ 就是和。

为什么全程不产生可读的中间态

MAJ 执行完之后，整条线路是不可分解的叠加态：每一位的 $b$ 上都带着来自所有低位的纠缠。这类状态不能被测量读出有意义的信息，也不允许测量-重置-条件化这类经典操作（那会破坏叠加）。

这不是缺陷，而是必须的。反过来问会清楚得多：QA020 证明，不存在能把未知量子态（哪怕基底已知）加上常数、且不借助辅助系统的酉。也就是说，加法在原理上就要求”辅助比特”这个角色——它承担的是跨态传递进位信息。CDKM 的贡献不是消除了这个角色，而是把承载它的线数从 $O(n)$ 压到 1。

所以”计算态”这个说法在这里是不成立的：进位在整个链上从未作为一个可读的值出现过，它被摊开分布在 $n$ 根线上，直到 UMA 阶段才在每一位上被局部重新聚合。这也是为什么 CDKM 加法器能原样作用在均匀叠加态上。

反计算的真实成本

算术线路的成本常常被报成”门数 + 深度”。但下游模块要求上游把空间交还回来：辅助位必须回到 $|0⟩$，借过的寄存器位必须复原。这段反计算在门数上常被忽略，在深度上却可能相当可观。

QA009 给出的数字是：测量基反计算相对相位 Toffoli 辅助位最多可占整条线路深度的 30%。同一篇还指出两条与直觉相反的结论——降低 T 数可能抬高总深度；在 NISQ 线路里用测量换 CNOT 可能是有利的。这三条合起来说明一件事：谈加法器的”效率”时，必须先说清楚指的是哪个深度、哪次分解，否则数字不可比。

当下的后续走向

MAJ/UMA 这个骨架仍然是活的标准件，后续改进集中在四类：

T 成本与深度的重排。 QA032 从 ZX↔ZH 图傅里叶变换出发，重新推导并推广了 Toffoli 加法器（含 CDKM 一族）已知的 T 门削减技巧；QA025 则对进位链加法器与比较器做 Clifford+T 下的 CNOT/T 数与深度最优化。QA007 给出一个值得注意的证据：把 QFT 加法器系统地改写成 Toffoli 构造后，它与最省 Toffoli 加法器具有根本相同的容错成本（如 T 数），差别主要在门的合成方式。

阶梯替换。 CDKM 里的 CNOT 阶梯与 Toffoli 阶梯是串行深度的来源。QA011 把这两种阶梯分别换成 $O(\log n)$ 与 $O({\log }^{2}n)$ 深度的线路（门数保持线性 / 线性对数），得到首个精确的无辅助位次线性深度加法器，且只用 Toffoli、CNOT 与 X 门。QA010 进一步指出，阶梯的三种实现方式（无辅助位线性、无辅助位多对数、有辅助位对数）与 2 种进位结构的交叉恰好给出 6 种加法器，其中 2 种是新设计。

模块化。 QA023 给出 PPKN 门——一种保输入的单 Toffoli 全加器（1 个 Toffoli + 5 个 CNOT），并说明如何级联 PPKN 模块构成 $n$ 比特进位链加法器。这是”把全加器当模块”的思路，详见quantum-full-adder。

块粒度与工厂吞吐。 QA014 把比特分组为大小 $b$ 的块并行，out-of-place 形式 $3n+5n/b$ 个 Toffoli、in-place 形式 $5n+8n/b$ 个，并指出代价是反应深度随 $b$ 线性增长且需要额外工作区；它同时建模了魔法态工厂数量对时空代价的影响。

论文依据

• Cuccaro–Draper–Kutin–Moulton 2004 —— MAJ/UMA 结构的原始出处：只需单个辅助比特、线性深度的新进位链加法器。
• Alvarez-Rodriguez 等 2014 —— 证明不存在对未知量子态做加法的酉，且无辅助系统时对已知正交基的加法亦被禁止；本词条”为什么全程不产生可读的中间态”一节的原理依据。
• Paler–Oumarou–Basmadjian 2021 —— 给出测量基反计算相对相位 Toffoli 辅助位最多占深度 30% 这一数字，以及 T 数降低可能抬高深度、用测量换 CNOT 等结论。
• Kuijpers–van de Wetering–Kissinger 2019 —— 通过 ZX↔ZH 图傅里叶变换推导并推广 Toffoli 加法器已知的 T 成本削减技巧。
• Remaud 2024 —— 对先进先进位链加法器与比较器做 Clifford+T 的 CNOT/T 数与深度最优化。
• Remaud–Vandaele 2025 —— 用 $O(\log n)$ / $O({\log }^{2}n)$ 深度的低深度实现替换 CNOT 阶梯与 Toffoli 阶梯，得到首个精确无辅助位次线性深度加法器。
• Remaud 2025 —— 把 Toffoli 阶梯的 3 种实现与 2 种进位结构交叉，得到 6 种加法器的统一分类。
• Gidney 2020 —— 分块先行加法器的 Toffoli 数与魔法态工厂建模。
• Papakonstantinou 2025 —— PPKN 保输入单 Toffoli 全加器（1 Toffoli + 5 CNOT），并给出级联构成进位链加法器的模块化架构。
• Paler 2022 —— 把 QFT 加法器系统翻译为 Toffoli 加法器，论证两者的容错成本（如 T 数）根本相同。

延伸阅读

• cdkm-adder —— 本词条的上层结构
• negadd-and-subtraction —— 借位技巧在取负相加中的用法
• hybrid-adders —— QFT 与进位结构之间的门级互变换
• 门代价模型 —— T 数、深度、比特、吞吐为什么不能换算