常数与递增加法器

模幂线路里有大量”把一个编译期已知的常量加进量子寄存器”的操作——模归约的偏移量、窗口化取模的移位项、循环计数器的递增。它们不需要通用加法器。核心技巧是进位可以被离线算出来：常量的哪些位会产生进位、传播到哪里、在哪一位被终止，都能在编译期确定，于是线路上只需搬运结果而不必现场计算进位。本词条讲清这条捷径的边界、已有的具体结果，以及”比较器”与”递增器”作为退化情形的渐进最优界。

核心观察：常数进位可以离线算

设要算 $x+c$，$c$ 已知。第 $i$ 位是否产生进位取决于 $x_{<i}$ 与 $c$ 的低位：

$$c_{i+1}=\mathrm{maj}(x_i,c_i,\text{carry-in}),$$

而 carry-in 本身是 $x$ 的函数——看起来无法离线。但这里有个关键差别：虽然进位的取值依赖于 $x$，进位发生的位置却不完全依赖于 $x$。具体地，一旦遇到 $c_i=1$ 的位，进位链被”点燃”；遇到 $c_i=0$ 的位，进位被”熄灭”。整条加法可以分成若干段，每段的边界由 $c$ 的位模式决定，而段内的进位只需按 $x$ 的相关位做受控搬运。

这意味着线路可以按 $c$ 的连续段结构组织，段内仍是标准的进位搬运，段与段之间的进位边界是编译期常量。省下来的正是段内的 $\mathrm{maj}$ 计算——通用加法器里最贵的那些 Toffoli。

常数加法：段边界由编译期常量确定

常数加法器的具体结果

QA013（Fedoriaka 2025） 给出就地加经典 $n$ 比特常量到量子 $n$ 比特整数（模 $2^n$）的线路：

• 就地版：$n-3$ 个辅助比特，T 数 $4n-5$；
• 受控版：$n-2$ 个辅助比特，T 数 $11n-15$；
• 附带 Q# 实现。

这组数字说明两件事。第一，常数加法的辅助比特需求并不为零（$n-3$ 仍是 $O(n)$），但常数很小，说明线路结构里有大量部分折叠。第二，受控版代价明显更高（辅助位 $n-2$、T 数 $11n-15$）——受控条件会把段内搬运变成多控门，这是常数加法设计中要重点权衡的一点。

QA011（Remaud–Vandaele 2025） 在其无辅助位次线性深度加法器的同一工作中，同时给出了新的递增构造与常数加法构造。这说明这两者与通用加法器共享骨架（CNOT 阶梯与 Toffoli 阶梯的低深度替换），因而改进可以顺带获得。

QA034（Gidney 2025） 解决的是一个更基本的问题——经典–量子加法器（即经典常量加进量子寄存器）。论文给出的背景是：2004 年 CDKM 找到了 $O(n)$ 门、$O(1)$ 辅助比特的量子–量子加法器，此后”经典–量子加法器能否达到同样的渐近复杂度”成了一个悬案二十年。结果：

• 3 个洁净辅助比特 + $4n\pm O(1)$ 个 Toffoli 门；
• 另给出一个 $3n\pm O(1)$ 个 Toffoli 的版本，用 2 个洁净辅助比特 + $n-2$ 个脏辅助比特；
• 且让这些加法器受一个控制比特条件化时不需要额外工作区或额外 Toffoli。

这个结果的现实意义论文说得很清楚：这类成本对模算术线路尤其相关，因为模数通常是经典已知的、需要加一个经典偏移量。

比较器与递增器：退化情形及其最优界

递增（$x\mapsto x+1$）与比较（判断 $x\ge y$）可以看作常数加法器的退化情形，但它们有自己的理论结果。

QA012（Vandaele 2026） 给出比较与递增操作的量子线路，在 Clifford+Toffoli 门集上达到渐近最优：

• 门数 $\Theta (n)$；
• 深度 $\Theta (\log n)$；
• 比特数可证最小。

论文把结果推广到经典–量子比较器，由此得到一个比特数最优的改进版经典–量子加法器。作为应用示例：这些构造可以把 Shor 分解算法的空间高效线路深度从 $\mathcal{O}(n^3)$ 降到 $\mathcal{O}(n^2{\log }^{2}n)$，且不增加比特数、不改变门数的渐近阶。支撑这些结果的是一个一般性定理：可以用控制比特换辅助比特，且在深度与门数上的额外开销都很低。

这个”辅助比特 ↔ 控制比特”的交换定理值得单独记住——它解释了为什么在”比特极稀缺”的量子纠错设定下，控制比特有时比辅助比特更划算。

辅助比特与控制比特之间的交换（QA012 的一般定理）

另一条相关线索。 QA025 对进位链加法器与比较器一并做了 Clifford+T 下的 CNOT/T 数与深度最优化——比较器与进位链共享 MAJ/UMA 骨架，因此可以套用同一套 T 成本削减技巧（见majority-uma-uncompute）。

相位路线上的对应做法

如果加数是编译期常量，QFT 路线还有另一条捷径：直接把该常量的傅里叶系数展开成受控相位门。QA004 指出相位加法器的一个明确能力——把经典数加到量子叠加态上，而无需把经典数编码进量子寄存器。在 $n$ 比特宽度下，常量的二进制位直接决定了哪些受控 $Z$ 旋转要施加；不需要辅助比特，但旋转数是 $O(n^2)$ 级别。

因此两条路线在这里的取舍与通用加法器一致：相位路线省比特、进位路线省门（见takahashi-qft-adder）。

一条需要如实说明的取材边界

关于”量子相等加法器”（equality adder），本次核验没有找到专门的论文；比较方向只有上列的几条可核验记录（QA012、QA025、QA034），不能凑数。类似地，模 $2^n+1$ 加法器的专门设计是有的（QA038，见negadd-and-subtraction），但那属于模运算一侧，不在本词条展开。

什么时候该专门做常数/递增线路

• 模归约的偏移量：模数经典已知 → 经典–量子加法器（QA034）。
• 窗口化模幂：移位项与偏移量都是常量 → QA013 或 QFT 路线。
• 循环计数器：递增是最简单的情形 → QA011 或 QA012。
• 需要比较来触发条件操作：比较器的渐进最优界见 QA012，且其”控制换辅助”定理对整个模运算卷都有用。

论文依据

• Fedoriaka 2025 —— 提出就地加经典 $n$ 比特常量到量子 $n$ 比特整数（模 $2^n$）的新线路：$n-3$ 辅助比特、T 数 $4n-5$；受控版 $n-2$ 辅助比特、T 数 $11n-15$；附 Q# 实现。
• Gidney 2025 —— 终结经典–量子加法器问题：3 个洁净辅助位 + $4n\pm O(1)$ 个 Toffoli；另给出 $3n\pm O(1)$ Toffoli、2 洁净 + $n-2$ 脏辅助位的版本；并证明受控应用不需要额外工作区或 Toffoli。论文说明该问题自 2004 年 CDKM 之后悬置，并指出其成本对模算术线路（经典已知模数与偏移量）尤其相关。
• Remaud–Vandaele 2025 —— 在首个精确无辅助位次线性深度加法器的同一工作中，给出新的递增构造与常量加法构造。
• Vandaele 2026 —— 比较与递增线路在 Clifford+Toffoli 门集上达到 $\Theta (n)$ 门数、$\Theta (\log n)$ 深度且比特数可证最小；推广到经典–量子比较器得到比特数最优的改进加法器；给出”用控制比特换辅助比特、开销低”的一般定理；应用于 Shor 把深度从 $\mathcal{O}(n^3)$ 降到 $\mathcal{O}(n^2{\log }^{2}n)$。
• Draper 2000 —— 相位加法器允许把经典数加到量子叠加态而无需编码进量子寄存器；本词条”相位路线”一节的依据。
• Remaud 2024 —— 对进位链加法器与比较器一并做 Clifford+T 的 CNOT/T 数与深度最优化。
• Cuccaro–Draper–Kutin–Moulton 2004 —— $O(n)$ 门、$O(1)$ 辅助比特的量子–量子加法器，是 QA034 明确对照的 2004 年基线。

延伸阅读

• negadd-and-subtraction —— 常量加法的一个高频用例
• cdkm-adder —— 通用加法器，常数版本通常由它特化而来
• adder-resource-comparison —— 两条路线的数字对照
• negadd-and-subtraction —— 常量加法的一个高频用例