模除法

精确的整数模除法（求 $p\mathrm{mod}N$ 或 $\lfloor p/N\rfloor$，$p$ 保持相干态）在线路层面是出了名的难写：商是一个”跳变”的函数，不像加法那样局部可算。于是主流方案的态度是一致的——回避显式除法，用乘以预计算常量、移位、条件减法把它替掉。本词条先讲清这条回避策略的数学根据，再如实说明一处文献空白：本轮检索到的唯一 Newton–Raphson 除法量子线路是浮点的，不是 Shor 需要的精确整数模除法。

一、为什么除法难，而”绕开”是共识

加法之所以适合量子线路，是因为它是局部的：第 $i$ 位的输出只依赖第 $i$ 位与低位传来的进位，所以可以用进位链逐位算。除法则不局部——商 $\lfloor p/N\rfloor$ 的第 $k$ 位依赖于全局的比较结果，正是这条依赖链导致除法无法被拆成便宜的逐位部件。

减法同样不局部（借位从低位往高位传播），但它可以由取负 + 加法实现（见modular-subtraction-negation）。除法没有这样的替身：把除法写成”减法 + 取模”需要先知道商是多少，循环依赖。

于是有了两种可行策略：

1. 回避：不做除法，改用 Barrett 型归约——用一次乘以 $\mu =\lfloor 2^{2n}/N\rfloor$ 得到近似商，再用移位与少量条件减法收尾，全程无除法。Zhang 等给出的对照是这一策略的收益：通用模归约依赖递归减法器与受控加法器来避免除法操作，T 深度约 $O(2^n)$；改用 Barrett 归约后 T 深度仅 $O(n^2)$。
2. 特殊化：只在操作数是常量时做除法。Pavlidis 与 Gizopoulos 的架构里就有显式的”除常量”块——除数编译期已知时，除法的实现可以退化成固定加法器阵列，失去的只有通用性。

回避除法：条件减法式归约 vs Barrett 型归约

两条路线都不含除法框——这不是巧合，而是模算术线路设计的一条原则：除法永远被换成乘法 + 移位 + 条件减法的组合。

二、Newton–Raphson：结构上可行，但这条文献是浮点的

Newton–Raphson 求逆的迭代式

$$x_{k+1}=x_k(2-a\cdot x_k)$$

每一步只需要一次模乘和一次减法，迭代 $O(\log n)$ 次，精度每步翻倍。它的吸引力在于：把”求逆”化成”模乘 + 减法”，再把”求逆”进一步用于”求除法”（因为 $a/b=a\cdot b^{-1}$）。这是一种很自然的思路，也是经典算法里的标准做法。

但本轮检索到的唯一量子 Newton–Raphson 除法线路文献是浮点的。 Gayathri、Kumar 与 Dhanalakshmi 提出的是用 Newton–Raphson 除法算法实现浮点除法的量子线路模型；他们报告相对当时最快的除法算法工作，量子比特节省约 17% 与 20%、T 数节省约 59.03% 与 20.31%、T 深度节省约 77.45% 与 24.33%。

这些数字必须带着”浮点”这个限定读。浮点除法与精确整数模除法是两个不同的问题：前者允许近似结果与规格化的指数域表示，后者要求对任意相干输入给出精确的商与余；后者的中间值不能溢出、不能截断，因此对进位保存宽度与归约精度的要求严格得多。用浮点除法的 T 数节省去推断整数模除法的成本是不成立的。

文献空白

精确 / 半精确 Newton–Raphson 整数模除法的量子线路，本轮未能核实到原始文献。 检索覆盖了 arXiv API、Crossref 与 DataCite；上表唯一相关的 QM021 处理的是浮点。本词条因此不给出该技术的任何引用，也不转述任何声称的精确整数模除法线路结果。

一个必须说明的口径事实：调研底稿的线路族谱里点名”精确 Newton–Raphson 模除法”是一个需要核查的方向，但结论是未核实。因此本站不写”某某提出了精确 Newton–Raphson 模除法线路”这类句子——如果需要引用这个方向，请自行到文献库核实。

三、可以引的替代路线

既然显式精确模除法缺文献，实际可引的、有出处的替代路径有两条：

Barrett 型归约。 Zhang 等（2025）折叠 Barrett 归约 明确对比了两条路线：通用模归约（递归减法器 + 受控加法器，刻意回避除法）T 深度约 $O(2^n)$；Barrett 归约 T 深度 $O(n^2)$。这条替代路线不仅有文献，还有可引的数字。

除常量块。 Pavlidis 与 Gizopoulos（2012/2014）Shor 模幂架构 的架构里显式构造了”除常量的量子除法器”，并把它组装进通用模乘子。这说明”做除法”在量子线路里是可以做到的——代价是除数必须是编译期已知的常量。这正是 Shor 场景下最常见的情形：模数 $N$ 在整个算法运行期间不变。

除常量的可行结构 vs 通用精确模除法的空白

四、结语：一个诚实的对照表

需求	有文献？	可引来源
量子 Barrett 型归约（避开除法）	有	QM010（$O(n^2)$ vs $O(2^n)$）、QM008
量子除常量线路	有	QM008（架构内的除常量块）
面向具体常量的模乘线路优化	有	QM009（最短路，$\Theta (n^2)$ 最坏界）
量子浮点除法（Newton–Raphson）	有	QM021（须标注浮点）
量子精确整数模除法（Newton–Raphson）	无	——
量子精确整数半精确模除法	无	——

这张表的价值在于它同时说明了本卷的原则与局限：Shor 不需要精确整数模除法（用 Barrett 替掉即可），所以这条路上的文献少并不是算法发展的漏洞，而是这条路本身被主流方案放弃了。真正需要警惕的是相反的情况——有人用”浮点除法”或”除常量”的数字去冒充”通用精确模除”的成本，那才是会误导资源估计的错误。

论文依据

• Zhang 等（2025） —— 明确指出通用模归约依赖递归减法器与受控加法器以避免除法操作，T 深度约 $O(2^n)$；其 Barrett 归约方案 T 深度仅 $O(n^2)$，是”用乘法与移位替代除法”这条替代路线的直接证据。
• Pavlidis 与 Gizopoulos（2012/2014） —— 其架构显式构造了”除常量的量子除法器”并组装进通用模乘子，给出深度约 $2000n^2$、$9n+2$ 比特、总代价 $1600n^3$ 的整体报价。
• Gayathri、Kumar 与 Dhanalakshmi（2022） —— 本轮唯一核实到的量子 Newton–Raphson 除法线路，但对象是浮点除法；报告量子比特节省约 17%/20%、T 数节省约 59.03%/20.31%、T 深度节省约 77.45%/24.33%。
• Markov 与 Saeedi（2012） —— 面向具体 $C$、$M$ 的模乘线路最短路优化，最坏界与平均规模仍为 $\Theta (n^2)$；说明针对具体常量的优化不改变渐近结构。

未核实项

精确 / 半精确 Newton–Raphson 整数模除法的量子线路未核实到文献。本词条按纪律不给它任何引用，也不用 QM021（浮点）替代它。

延伸阅读

• modular-reduction —— Barrett 型归约的实现细节。
• modular-inverse —— 与除法纠缠的另一处空白。
• modular-multiplication —— 除法在这套装配里被放在哪。
• fixed-point-arithmetic —— 整数（非模）除法的三条迭代路线与定点舍入：Thapliyal 系列与 Mukhopadhyay–Gheorghiu–Krovi 的线路在数值格式卷有定位。本词条的空白（精确整数模除法）与那边的文献（整数除法）不是同一个问题。