模乘

模乘是 Shor 算法里唯一值得反复优化的原语：模幂展开成二进制幂后，每一轮迭代就是一次模乘，它的成本直接乘进整条线路的报价。模乘本身是一个装配：乘法段给出一个宽乘积，归约段把它压回 $n$ 比特。本词条讲清装配的边界条件（哪些输入是常量、哪些是全连接、控制位怎么处理），然后给出三份可引的端到端报价——它们的价值在于包含了控制位与常量比特的账，而不是孤立的乘法器数字。

一、装配的输入与输出

模乘的通用形式是 $z\leftarrow (c\cdot a+z)\mathrm{mod}N$，其中：

• $a$、$z$：$n$ 比特全连接寄存器；
• $N$：经典常量，可编译进受控门序列；
• $c$：控制位，决定这一步是否执行。

模乘装配：受控乘法段 + 归约段，控制位贯穿全程

图里 p 宽 $2n$，这正是modular-reduction 里两段结构的分界。控制位与常量的处理方式是模乘报价差异的主要来源——报一个不带控制位的 $z\leftarrow za\mathrm{mod}N$ 与报一个带控制位、且常量需另存寄存器的版本，深度可以差很多。

二、QFT/Draper 加法器族给出的端到端架构

Pavlidis 与 Gizopoulos 是目前本卷能引到的、最完整的端到端模幂架构报价。他们的做法是：用基于 QFT 的 Draper 加法器族构造出更复杂的算术块——乘常量/累加的量子乘法器与除常量的量子除法器——再把这些块组装成一个通用模量子乘法器，也就是模幂线路里最耗资源的那个基本块。

他们报告的报价是：模幂线路深度约 $2000n^2$、需要 $9n+2$ 个量子比特（$n$ 为待分解数的位宽）、总量子代价 $1600n^3$；若对每个加法器单元使用近似 QFT 实现，深度还能再降三倍以上。

这组数字值得三读。第一，$9n+2$ 比特说明归约与乘法的中间寄存器都被压到了线性，代价是深度到了 $n^2$ 量级——这与”辅助比特账”和”深度账”是两种资源完全一致。第二，“除常量块”的存在说明在这个架构里除法是显式做掉的，但它是除常量——一个在线路上有专门结构的操作，见modular-division。第三，近似 QFT 的三倍深度收益提示：在深层结构里，QFT 族的近似截断是一条独立于算法层级的优化。

三、针对具体常量的优化

Markov 与 Saeedi 的出发点是一个具体的批评：既有的通用构造关注的是渐近门数与电路深度而非实际数值，因此针对具体的 $C$ 与 $M$ 产生的线路偏大。他们的做法是自底向上地优化，从最方便的 $C$ 值开始；在有零初始化辅助寄存器可用时，把寻找紧凑 $Cx\mathrm{mod}M$ 线路的搜索化为最短路问题。

他们的结果值得如实转述其边界：部分模乘线路渐近小于既有构造，但最坏界与平均规模仍为 $\Theta (n^2)$。这个诚实的结论说明常量化优化拿到的是常数因子与针对特定 $C$、$M$ 的实际收益，而不是新的渐近界。他们还指出，在模幂背景下这些常数因子的改进，以及一个对少比特线路（当前实验室 Shor 实验的规模）相当显著的常数加性项改进。

常量化模乘的搜索视角：节点=部分和状态，边=受控加法

这张图是对”最短路优化”最直白的解释：把部分和的取值当作图上的状态，把一次受控加法当作一条边，那么最短路径长度就是最少的受控加法次数。这个图论化的视角之所以成立，是因为 $C\cdot 2^n\mathrm{mod}N$ 的部分和序列本身是一个可达状态图。

四、让模乘变便宜的三条外围路线

选友好的模数。 Gaur 与 Thapliyal 用余数系统把大乘法拆成多个小的模乘法，其中 $2^n+1$ 这个模数因为减法即补码加法而格外便宜。分布式执行把 Toffoli 深度最多降低 46.018%、T 门降低 34.483%–86.25%——但对比口径是 6 到 16 比特输出规模下的一个非分布式乘法器。

面向有限域的乘法。 AlphaTensor-Quantum 在 T 数优化中自动发现了类 Karatsuba 的有限域乘法算法，并在 Shor 相关的算术计算上找到了与人工设计最好的方案。它说明模乘里的乘法段还有优化空间，而且是搜索得来的。

图重写。 Joshi 等用 ZX 微积分的重写规则优化容错乘法器，报告辅助比特与 T 门数量都有显著下降。这是在不改变算法结构的前提下从图层面压缩成本。

论文依据

• Pavlidis 与 Gizopoulos（2012/2014） —— 用 QFT/Draper 加法器族构造乘常量/除常量块并组装成通用模量子乘法器；给出深度约 $2000n^2$、$9n+2$ 比特、总量子代价 $1600n^3$ 的模幂架构，并指出近似 QFT 可再降三倍以上深度。
• Markov 与 Saeedi（2012） —— 把针对具体 $C$、$M$ 的紧凑模乘线路搜索化为最短路问题（前提是有零初始化辅助寄存器）；部分构造渐近更小但最坏界与平均规模仍为 $\Theta (n^2)$，并给出对少比特线路显著的常数加性项改进。
• Zhang 等（2025） —— 折叠 Barrett 归约把模乘的归约段 T 深度降到 $O(n^2)$（对照通用归约的约 $O(2^n)$），并把模运算线路与量子-量子、量子-经典乘法电路集成。
• Gaur 与 Thapliyal（2025） —— RNS 分布式量子乘法与 Diminished-1 模 $2^n+1$ 乘法器；报告 Toffoli 深度最多降 46.018%、T 门降 34.483%–86.25%（规模 6–16 比特输出）。
• Ruiz 等（2024） —— AlphaTensor-Quantum 自动发现有限域乘法中类 Karatsuba 的高效算法，并在 Shor 相关算术计算上找到最优人工方案。
• Joshi 等（2023） —— 用 ZX 微积分重写规则压缩容错乘法器的辅助比特与 T 门数量。

延伸阅读

• modular-reduction —— 归约段，内部空间最大。
• modular-division —— 为什么除法不在这套装配里。
• multiplication-overview —— 乘法段能优化到什么程度。