模归约

模归约是把一个 $n$ 比特以上的值压回 $[0,N)$ 的步骤，它通常是模乘线路里最贵的一段，因为它必须回答”减几次 $N$“。两条主流路线的差别正在这里：通用递归减法式归约老老实实地减，代价是深度随 $n$ 指数增长；Barrett 型归约改问”商是多少”，而商可以用一次乘以预计算常量近似得到——于是”除法”被替换成”一次乘法 + 移位 + 一次条件减法”。本词条先画出两段结构，再解释 Barrett 为什么能绕开除法。

一、ADD / MOD-REDUCE 两段结构

模乘的标准装配是两段：先做一次（可能超出 $n+1$ 位的）乘法得到一个宽乘积，再做归约把它压回 $n$ 位。这两段之间是所有成本权衡发生的地方。

模乘的两段结构：ADD 段与 MOD-REDUCE 段

ADD 段是可以优化的，乘法有 Karatsuba；MOD-REDUCE 段往往不是。 这就是为什么本卷的重心偏向归约而非乘法。Pavlidis 与 Gizopoulos 的架构也遵循同样的判断：他们用 QFT/Draper 加法器族构造的”乘常量 / 除常量”块被组装成通用模乘子，而其中的归约正是靠这类专用块完成的。

二、通用归约为什么贵

最直观的归约是”只要结果 $\ge N$ 就减一次 $N$“，反复做。但在一个 $n$ 比特位宽的线路里，要判断与执行一次受控减法都需要一整条加法器；而且要保证做足够多次才能覆盖最坏情况，最坏情况需要 $2^k$ 次量级的重复——这正是深度爆炸的来源。

Zhang 等把这条路线称为通用模归约，并指出它依赖递归减法器与受控加法器来避免除法操作，其 T 深度约为 $O(2^n)$，其中 $n$ 是模数的位长。这个数字应该怎么读：它不是说”实际跑 $2^n$ 次”，而是说这类结构的 T 深度随位宽指数增长。这是本卷最刺眼的一个渐近记号。

三、Barrett 型归约：把除法换成乘法

Barrett 归约的思路是绕开”减几次”。设 $p$ 是宽 $n$ 比特以上的乘积（$p<N^2$），真实的商约等于 $\lfloor p/N\rfloor$。Barrett 归约预先算好一个常量

$$\mu =\lfloor \frac{2^{2n}}{N}\rfloor$$

然后用一次（更窄的）乘法估计商：

$$q=\lfloor \frac{p\mu }{2^{2n}}\rfloor$$

这个 $q$ 是一个近似商，与真商相差很小（具体差值依赖 $N$ 与 $n$ 的关系），于是剩下要做的只是一次或两次条件减去 $qN$——而 $qN$ 本身可以用移位与加法便宜地得到。整个过程中没有出现除法。

Zhang 等实现了 Barrett 归约的三个量子线路版本（含他们的优化版折叠 Barrett），并把它们与量子-量子、量子-经典乘法线路集成，分析并对比了三者的量子资源需求。其折叠 Barrett 方案报告T 深度仅为 $O(n^2)$，与前述通用归约的 $O(2^n)$ 形成对照。这一对比的定性含义很清楚：归约的深度从指数级降到多项式级，代价是常量的选择与乘法段宽度都要重新调。

Barrett 型归约：一次乘近似商 + 少量条件减法，全程无除法

这里的 shift 那根线标的就是关键点：移位等价于除以 $2^{2n}$，它是免费的（纯比特重排）。所以 Barrett 归约本质上是把”除以 $N$“变成”乘以 $\lfloor 2^{2n}/N\rfloor$ 再除以一个 2 的幂”，两件事分别由一次乘法与一次移位承担。

四、归约的下游：前导零与比较

归约输出之后往往还有一段”归一化”工作：判断结果的有效位到哪儿、是否溢出等。这一段的核心子线路是前导零检测器，见comparators-and-equality。Orts 等对前导零检测器电路给出了优化实现，把它定位为模归约与归一化路线的关键子线路。

另一条更工程化的改进是针对具体常量的优化。Markov 与 Saeedi 指出，通用构造关注的是渐近门数与深度而非具体数值，产生的线路对特定 $C$ 与 $M$ 往往偏大；他们把”在有零初始化辅助寄存器时寻找紧凑的 $Cx\mathrm{mod}M$ 线路”化为最短路问题，自底向上从最方便的 $C$ 值开始优化。其结果中部分模乘线路渐近小于既有构造，但最坏界与平均规模仍为 $\Theta (n^2)$。

论文依据

• Zhang 等（2025） —— 提出基于 Barrett 归约的优化模运算方案，实现三个版本的 Barrett 归约线路；明确给出通用模归约（递归减法器 + 受控加法器）的 T 深度约 $O(2^n)$ 与其折叠 Barrett 方案的 $O(n^2)$ 对照，并把线路与量子-量子、量子-经典乘法电路集成。
• Pavlidis 与 Gizopoulos（2012/2014） —— 用 QFT/Draper 加法器族构造除常量块并组装成通用模乘子，给出深度约 $2000n^2$、$9n+2$ 比特、总代价 $1600n^3$ 的模幂架构；近似 QFT 可再降三倍以上深度。
• Markov 与 Saeedi（2012） —— 把针对具体 $C$、$M$ 的紧凑模乘线路搜索化为最短路问题；部分构造渐近更小，但最坏界与平均规模仍为 $\Theta (n^2)$。
• Orts 等（2022） —— 前导零检测器的优化实现，是模归约与归一化路线的关键子线路；本站未取得其摘要，不转述其具体门数结论。
• Gaur 与 Thapliyal（2025） —— 其 Diminished-1 模 $2^n+1$ 乘法器属于归约友好的模数选择：模 $2^n+1$ 的减法即补码加法，比一般模减法便宜。

延伸阅读

• modular-division —— 为什么”回避除法”是一条设计原则。
• modular-multiplication —— 两段结构如何组装。
• comparators-and-equality —— 归约之后的归一化。