减法与 negadd

研究阶段核验的一个结果是：没有找到任何一篇以”量子减法线路”为独立题目的可核验论文。这不是检索不足，而反映了事实——在所有已发表的量子算术方案里，减法不是一条独立线路族，而是 negadd：先把加数取负，再走一遍已有的加法器。本词条如实记录这个空白，说明文献里减法实际上是怎么做的，以及这个取舍在资源上意味着什么。

事实陈述：文献里没有独立的量子减法论文

先说清楚结论，因为这一点容易被想当然地补上一条不存在的引用。

核验结果：量子算术文献中没有专门针对”减法线路”的奠基性论文。减法在真实方案中的唯一做法是 negadd。这个名字由 QA008（Gidney–Ekerå 2019）在其大规模 RSA 分解资源估算中固定下来——negadd 是该文的规范出处。

需要澄清的两点常见误解：

• negadd 是一种实现约定，不是一个线路族。 它没有独立的门级构造，因为”取负 + 相加”里”取负”部分在经典可逆逻辑里是平凡的（就是异或），剩下的一切都是既有加法器。把它当成一个新家族来比较资源是错位的。
• 不要给它安一个来源。 有把 negadd 归给 Beauregard 的说法，但在本次核验中无法解析出对应的可核验记录，因此不予引用、也不在正文里断言归属。同理，有几篇”Peres 门式进位链改进”的论文只出现在搜索摘要里、无法经权威渠道解析，同样不引用。

这个空白其实是有信息量的。它说明在量子算术里，减法不是一个需要独立研究的问题——因为可逆逻辑下的减法完全被加法支配，研究的全部张力都集中在”用哪种加法器”上。

negadd 具体在做什么

设要算 $x-y$。经典算术里这是加一个负数；量子里同理，只是”负数”必须用位模式表示。最自然的选择是 $n$ 比特两’s 补码：$-y\mathrm{mod}{2}^n=2^n-y$，其二进制位模式就是 $y$ 各位取反再加 1。

于是 negadd 的实现是三步：

1. 把加数寄存器 $y$ 就地取反（每位一个 X 门）；
2. 把进位入 $c_0$ 设为 $1$（“再加 1”）；
3. 调用既有的加法器，把 $x$ 加到 $y$ 上。

negadd：取负 + 带进位入的加法，就地得到 b − a

注意这里复用了同一个 $b$ 寄存器：取负是就地做的，加法也是就地做的，所以 negadd 的空间代价与同类就地加法器相同。这就是为什么它值得被当作一个”约定”而不是”族”——它的成本完全由被调用的那个加法器决定。

negadd 在 QFT 路线里也有对应物：把常量 $\bar{a}+1$ 按傅里叶基展开成一列受控相位即可，无需改动 QFT 加法器本身。这是相位加法器能”把经典数加到量子叠加态上”这一性质的直接推论，见takahashi-qft-adder。

两’s 补码、借位与模 $2^n$ 的关系

减法在线路层面与加法的差别只有三处：加数各位取反、进位入设为 1、以及最后丢弃/处理进位出。理由是两’s 补码恒等式

$$x-y\equiv x+\overline{y}+1(\mathrm{mod}{2}^n),$$

其中 $\overline{y}$ 为按位取反。这个恒等式对叠加态同样成立，因为它是一个逐状态的恒等映射（对任意 $x,y\in [0,2^n)$ 成立），因此可以在计算基上直接实现为受控门，不需要”读出”任何东西。

由此得到两条实用推论：

• 借位不需要单独的线。 借位是减法的进位取反，从线路角度看与加法的进位同构。
• 溢出检测是免费的副产品。 加法的进位出 $c_n$ 在减法中恰好就是”借位出”，可用于比较或分支；无需额外电路。

文献里是怎么用它的

QA008（Gidney–Ekerå 2019）是 negadd 的规范出处。该文的整个模幂线路建立在 negadd 加法器与无辅助工作区的模加法之上，给出的抽象线路模型口径是：分解 $n$ 比特 RSA 整数需 $3n+0.002n\lg n$ 个逻辑比特、$0.3n^3+0.0005n^3\lg n$ 个 Toffoli、$500n^2+n^2\lg n$ 的测量深度。摘要还说明在包含噪声、需重复尝试与时空布局等因素的假设下，其时空体积比早期估算低两个数量级。

QA031（Gidney 2025）是这条线的最新更新，在同样的假设下（最近邻方格、门错误率 $0.1\%$、表面码周期 1 微秒、控制系统反应时间 10 微秒）把比特数降到百万以下，代价是运行时间从 8 小时延长到一周以上；比特数的下降主要来自近似剩余算术、用轭合表面码存储空闲逻辑比特、以及用魔法态培植减少蒸馏空间，而更长的运行时间主要来自更多 Toffoli 与更少的魔法态工厂。

这两条记录共同说明：减法电路的成本，从来是由它调用的加法器决定的；改进 negadd 本身没有空间，能改进的是加法器选择与调度。

近似补码：连取负都可以省

QA026（Gidney 2019）提供了一个更激进的观察。它引入”无意识进位滑行道”（oblivious carry runways）与分段加法器，把加法的渐近深度降到 $O(\lg \lg n)$，并证明余数集合表示（coset representation，Zalka 2006）本身就是一种近似编码的模加法，可与无意识进位滑行道组合使用。论文给出了这些近似表示的误差界，并据此构造了成本低于既有工作的 2’s 补码加法器与模加法器。

也就是说，两’s 补码运算可以整体交给近似编码去做，代价是结果带误差——而误差界是论文给出的，不是工程口号。若下游算法对低若干位的正确性不敏感，这条路的深度收益相当可观。

更激进的近似是 QA027（Gidney–Humble–Thapliyal 2024）给出的五种 NISQ 近似加法器：三种带进位出、两种不带。其中”直通式”设计直接由输入近似求和位，深度为零（不需要任何量子门）；第二种设计风格只用单个 CNOT 近似求和位，常数深度 $O(1)$。在 IBM Qiskit 上用热、退极化、幅度阻尼、相位阻尼与位翻转五种噪声模型评测：相对不带进位出的精确进位链加法器，保真度提升 8.34%–219.22%；相对带进位出的版本提升 8.23%–371%。引用这类结果时必须同时给误差界——这些设计本来就不给精确结果。

模减法与相关的模加法器

顺带说明另一处覆盖情况：量子模加法器这一侧有可核验的工作，例如 QA038（Gaur–Thapliyal 2024）专门面向 $2^n+1$ 模加法给出四个设计（QMA1–QMA4），论文明确指出此前不存在量子 mod $(2^n+1)$ 加法器的设计；QMA2 相对 QMA1 减少 37.5% CNOT 门数、46.15% CNOT 深度、26.5% Toffoli 门数与深度，QMA3 用零复位复用比特省下 25% 比特数，在 IBM Washington（127 比特 Eagle R1）上的 5 比特配置实验使 QMA1 误差降低 28.8%。这类工作属于模运算卷，本词条只作边界说明。

论文依据

• Gidney–Ekerå 2019 —— negadd 的规范出处。在无辅助工作区的模幂线路上使用 negadd 加法器，并给出 2048 位 RSA 在 2000 万噪声比特上 8 小时完成的资源口径（$3n+0.002n\lg n$ 逻辑比特、$0.3n^3+0.0005n^3\lg n$ 个 Toffoli、$500n^2+n^2\lg n$ 测量深度）。本词条”文献里是怎么用它的”一节主要依据。
• Gidney 2025 —— 同一路线的更新：在相同物理假设下把所需比特降到百万以下、运行时间延长到一周以上，并说明比特下降与时间延长的具体来源。
• Gidney 2019 —— 提出无意识进位滑行道与分段加法器，把加法渐近深度降到 $O(\lg \lg n)$；证明余数集合表示本身是近似编码的模加法；给出误差界并据此构造成本更低的 2’s 补码加法器与模加法器。本词条”近似补码”一节的主体来源。
• Gaur–Humble–Thapliyal 2024 —— 五种 NISQ 近似加法器（含零门深度与单 CNOT $O(1)$ 深度的直通式设计），在五种噪声模型下相对精确进位链加法器提升保真度 8.23%–371%。引用时须同时给出其误差前提。
• Gaur–Thapliyal 2024 —— 指出此前不存在量子 mod $(2^n+1)$ 加法器设计，并给出四个改进设计与硬件实验；用于说明模加法一侧的覆盖边界。
• Draper 2000 —— 相位加法器允许把经典数加到量子叠加态而无需编码进量子寄存器；这是 negadd 在 QFT 路线下同样只需替换常量展开的原因。
• Cuccaro–Draper–Kutin–Moulton 2004 —— negadd 调用的即此类就地进位链加法器；文献另讨论了带进位入与就地取负的变体。

延伸阅读

• cdkm-adder —— negadd 通常调用的就是它
• constant-and-increment-adders —— 常量加法与递增的专门线路
• adder-resource-comparison —— negadd 的成本取决于调用哪个加法器
• 进位与借位 —— 补码、借位与符号扩展的统一视角