模减与取负

“减法”在量子算术文献里是一个几乎没有独立线路的类型。原因很实际：量子线路必须可逆，而减法不是位排列，也不是简单地调用加法器——但取负（negation）是位排列。于是取负加加法就覆盖了全部减法需求，线路侧不必再单独发明一个减法原语。本词条讲清取负为什么便宜、补码加法为什么比普通加法器便宜，以及条件减法在模归约里究竟承担什么角色。

一、取负是位排列，加法才是贵的部分

$n$ 比特无符号取负，即 $x\mapsto 2^n-x$，等于

$$-x=(\neg x)+1$$

其中 $\neg$ 是逐位取反。逐位取反加一次加一——取反是 $X$ 门阵列（Clifford，零 T），加一是一个常数的加法器。所以取负的成本几乎全部落在那个”加一”上，而不是取反本身。

这条观察有一个直接后果：任何需要 $a-b$ 的地方，都可以写成 $a+(\neg b)+1$，从而完全复用普通加法器与常量加法器的构造。这是模算术线路图里几乎看不到独立”减法框”的原因。

取负 = 逐位取反 + 加一；减法 = a + ¬b + 1

图中只有一次真正的加法（最后那个 ADD 框），前后的取反与加一都是便宜的。这也解释了为什么减法在文献里不需要单独的线路论文：它的成本完全寄生在加法器上。

二、补码加法：为什么模 $2^n+1$ 的减法特别便宜

当减法出现在归约里时，通常不是免费的 $a-b$，而是条件减法：只有在某个条件成立时才执行 $z\leftarrow z-N$。这里有一个能省掉很多门的情形。

考虑模 $2^n+1$ 的情形。此时 $-N\equiv 1(\mathrm{mod}{2}^n+1)$，也就是说”减去 $N$“等价于”加 1”。加一是整个算术里最便宜的运算——一个常量的加法器，甚至在配合进位保存表示时可以只是一串受控加一。Gaur 与 Thapliyal 选择这个模数正是为此：他们的 Diminished-1 模 $2^n+1$ 乘法器是 RNS 分布式量子乘法的核心部件，而模 $2^n+1$ 的减法是补码加法，比一般模减法便宜。

这条经验值得记住：设计量子模乘线路时，模数的选择是一个真实的优化自由度。一个在位宽与常数特性上更”合身”的 $N$，可能比一个更小的 $N$ 便宜很多。

模 2^n+1 的条件减法：−N ≡ +1（补码加法）

对照着看差别就清楚了：模 $2^n+1$ 的条件减法是”受控加一”（一串便宜的加法），一般模 $N$ 的条件减法则需要一整条 $n$ 比特受控加法器。后者正是modular-reduction 里 $O(2^n)$ T 深度的来源之一。

三、条件减法在归约中的角色

回顾模归约的通用做法：“只要 $\ge N$ 就减一次 $N$“。这里每一步都是一次条件减法。三个设计上的自由度：

1. 减几次：最坏情况需要覆盖最大可能的商，位数决定次数。
2. 条件怎么来：读一次试减的借位（要先算一次减法），还是靠进位直接读（加法器的溢出位）。
3. 加还是减：如果换个模数或换个表示，“减 $N$“可能变成”加 $N^{\prime }$“，其中 $N^{\prime }\equiv -N$。

第 3 点是 Barrett 型归约能存在的原因：它的目标是尽量减少条件减法的次数，用一次乘法把商估计出来之后，剩下的减法次数就少了。这解释了为什么modular-reduction 里 Barrett 归约的 T 深度能到 $O(n^2)$ 而通用路线是 $O(2^n)$——不是加减法本身变便宜了，而是做的次数变少了。

四、两处需要如实说明的空白

第一，减法的独立线路文献。 本轮调研的结论是：算术线路文献里”减法”就是 negadd（取负加加法），没有独立的减法线路奠基论文。这一条不是缺陷而是设计后果——上面的推导说明取负是位排列，因此减法的成本已经完整地包含在加法器里。

第二，半精确减法/借位优化的专门工作。 与半精确模加法相关的奠基性工作本轮未能核实（检索结论为不在 arXiv 上，Crossref/DataCite 无收录）。本词条因此不对任何”半精确减法”构造做陈述。

需要说明的是：上面第三节第 3 点提到的”借位读出大小关系”是纯数学事实（$a-b$ 的进位即 $a\ge b$），它不依赖任何文献，详见comparators-and-equality。

论文依据

• Gidney（2018） —— 加法器层面的 T 数减半构造（$8n+O(1)\to 4n+O(1)$，临时逻辑与），明确适用于整数算术与模算术；减法通过 negadd 复用加法器，因此这条改进同样传导到减法。
• Gaur 与 Thapliyal（2025） —— Diminished-1 模 $2^n+1$ 乘法器：模 $2^n+1$ 的减法为补码加法，这是条件减法可以极便宜的模数选择实例；报告 Toffoli 深度最多降 46.018%、T 门降 34.483%–86.25%（对比规模 6–16 比特输出）。
• Zhang 等（2025） —— 其 Barrett 归约的核心正是把条件减法的次数压到最少，从而把 T 深度从通用路线的约 $O(2^n)$ 降到 $O(n^2)$。
• Pavlidis 与 Gizopoulos（2012/2014） —— 其架构中显式构造了”除常量”块并组装进模乘子，是减法/除法作为独立装配块存在的实例。

未核实项

半精确/近似模加法方向的奠基工作未核实到（不在 arXiv 上）。本词条按纪律不引用、不转述。

延伸阅读

• modular-addition —— 减法寄生其上的加法器。
• comparators-and-equality —— 借位如何读出大小关系。
• modular-reduction —— 条件减法次数的优化。