模算术总览

模算术的基本量只有三个：模数 $N$（经典输入，编译期已知）、被运算的 $n=\lceil {\log }_{2}N\rceil$ 比特寄存器、以及一个决定要不要执行的 $n$ 比特控制寄存器。几乎所有量子模运算线路的结构都由这三条推出：模 $2^n$ 加法丢弃进位即可，模 $N$ 加法必须比较并条件减去 $N$，而比较又需要减法——这就是本卷几乎所有词条互相咬合的原因。本词条先建立这个坐标系，再指出 Shor 里真正的瓶颈在哪里，最后给出本卷三处文献空白的明确边界。

一、三个基本量与由此推出的结构

设模数为 $N$，$n=\lceil {\log }_{2}N\rceil$。一个通用模运算 $z\leftarrow (z\mathrm{op}a)\mathrm{mod}N$ 通常有三类输入：$a$（$n$ 比特，全连接）、$N$ 与相关常量（经典输入，在 $N$ 已知时可编译进去）、以及一个控制位 $c$（决定是否执行）。整条线路在量子比特上是可逆映射：$|a,z,c⟩\mapsto |a,(z\mathrm{op}a)\mathrm{mod}N,c⟩$。

从这个坐标系直接可以推出两件事：

第一，模 $2^n$ 加法天然精确。 把 $z+a$ 在 $n$ 比特寄存器里算出来，进位被丢弃，剩下的就是 $(z+a)\mathrm{mod}{2}^n$。不需要任何比较器或条件减法线路。

第二，模 $N$ 加法必须额外处理。 $z+a$ 可能是 $[0,2N)$ 里的任一值，需要判断它是否 $\ge N$ 并条件减去 $N$。判断 $\ge N$ 就是一次比较，条件减去就是一次受控减法——而比较本身通常又是用减法实现的（读进位）。这个循环依赖解释了为什么模算术线路图上总是同一批部件反复出现。

模运算的通用骨架：输入三件套 + 归约

二、“半精确”：在误差容限内省掉比较器

模 $2^n$ 加法精确、模 $N$ 加法需要归约，两者之间的差别可以用一组折衷参数化。“半精确”指的是：在给定的误差容限内，用可控的进位链省掉比较器这一段。 直观地说，如果下游只关心结果的高若干位、允许一定出错概率，那么”是否 $\ge N$“这个判断就可以用一个近似条件替代，从而把比较器（通常是线路里最贵的一段）从关键路径上移除。

需要强调的是：这是一个精度与成本的折衷框架，不是某个具体线路的名字。它的具体实现在不同文献里形态差别很大，本卷只把它作为理解模加法成本结构的坐标系，具体线路见modular-addition。

三、Shor 里的瓶颈定位

Shor 因子分解的核心是 $a^x\mathrm{mod}N$，其中 $a$ 与 $N$ 都是经典已知量。展开二进制幂，模幂的实际计算就变成一串”乘常量并归约”：每一轮迭代（$\sim n$ 轮）做一次模乘，模乘里做一次乘法与一次归约。因此：

• 真正的资源大头是模乘，而不是模幂本身；
• 模乘里真正的资源大头是归约，而不是乘法（乘法还有 Karatsuba 等手段）；
• 归约的主流实现刻意回避除法——这是本卷最重要的一条工程结论，理由见modular-division。

一个完整的公开架构报价来自 Pavlidis 与 Gizopoulos：他们用 QFT/Draper 加法器族构造出乘常量、除常量块并组装成通用模乘子，给出深度约 $2000n^2$、$9n+2$ 比特、总量子代价 $1600n^3$ 的模幂架构，并指出若对每个加法器单元使用近似 QFT，深度还能再降三倍以上。这类报价的价值在于它是端到端的：乘法和加法器被组装进一个真实算法后，成本结构会与单独测量时明显不同。

四、本卷的三处文献空白

以下是本轮调研确认存在的空白，不是”暂时没查到”，而是检索了 arXiv、Crossref、DataCite 后仍无对应条目：

空白	检索结论	本卷的处理
精确 Newton–Raphson 整数模除法	只核实到浮点除法（QM021）；精确整数版未核实到原始文献	modular-division 如实说明，并解释 Shor 方案为何回避显式除法
Shor 求逆所需的模乘逆元量子线路	未核实到；唯一相关的 QM023 是纯经典算法且模数限定 $2^w$	modular-inverse 如实说明，给出可引的替代路线
”模算术反向传播”方法论	QM013 是用 ZX 重写规则做线路优化，不是模算术反向传播	zx-backpropagation 明确区分两者

关于半精确模加法的奠基性工作，调研中一个常被引用的作者组合（半精确/近似模加法方向）经 arXiv 标题检索返回 totalResults = 0（有效空响应），Crossref 与 DataCite 标题检索亦无收录，机构页面 404——可确定其不在 arXiv 上，因此本卷不引用，也不转述其内容。

论文依据

• Pavlidis 与 Gizopoulos（2012/2014） —— 提供端到端的 Shor 模幂架构报价（深度约 $2000n^2$、$9n+2$ 比特、总代价 $1600n^3$），并给出用近似 QFT 再降三倍以上深度的条件。
• Gidney（2018） —— 提供加法器层面的 T 数改善（$8n+O(1)\to 4n+O(1)$，临时逻辑与），并明确其适用范围包含整数算术、模算术、旋转合成、QFT 与 Shor 的 oracle。
• Zhang 等（2025） —— 提供 Barrett 型归约与通用递归减法式归约的直接对比：后者 T 深度约 $O(2^n)$，前者 $O(n^2)$。
• Wang 与 Chattopadhyay（2026） —— 综述性章节，作为模算术的二级入口；本站未取得其摘要，不对其具体论断做引用。

延伸阅读

• modular-reduction —— 瓶颈所在。
• modular-division —— 本卷最重要的诚实性讨论之一。
• modular-multiplication —— 装配处。