模乘逆元

Shor 算法要计算 $a^x\mathrm{mod}N$，第一步就得先求 $a$ 在模 $N$ 下的逆——若 $\gcd (a,N)\ne 1$ 则直接给出因子。所以求逆是一个必须实现的量子原语。牛顿迭代 $x_{k+1}=x_k(2-a{x}_k)$ 在结构上很美：每步只要一次模乘和一次减法，$O(\log n)$ 步收敛，除法被化成”求逆”、求逆又被化成”模乘”。但本轮调研确认了一件事：这个漂亮的结构在文献里缺少对应的量子线路，可核实到的只有纯经典的算法与浮点除法。本词条把数学结构讲全，然后把空白如实标出。

一、求逆在 Shor 里的位置

标准 Shor 预处理随机取 $1<a<N$，计算 $\gcd (a,N)$：

• 若 $\gcd >1$，$N$ 被分解，结束；
• 否则需要计算 $a$ 的阶，而阶的计算走的是 $a^x\mathrm{mod}N$ 的周期搜索。

问题在于随机选出的 $a$ 未必对 $N$ 可逆。标准做法是先算 $a^{N-1}\mathrm{mod}N$（用模幂线路，这是已有原语），读出结果判断它是否为 1；不为 1 则说明 $a$ 在模 $N$ 下可逆，才继续。因此求逆不需要单独造一条”求逆线路”——它可以用已有的模幂 + 测量 + 条件判断完成。

这一点很重要：它解释了为什么”模乘逆元的专用量子线路”在文献里不常见——主流 Shor 实现根本不需要把逆元作为相干寄存器算出来。真正的需求是”判断可逆性”，而这由模幂加测量解决。

Shor 预处理：用模幂 + 测量判断可逆性，而非显式求逆

二、牛顿迭代：结构上为什么优雅

若要真的在相干态上算逆（其他算法或变体 Shor 需要时），自然的想法是牛顿迭代：

$$x_{k+1}=x_k(2-a{x}_k)$$

误差分析是干净的：若 $e_k=1-a{x}_k$，则

$$e_{k+1}=1-a{x}_k(2-a{x}_k)=(1-a{x}_k{)}^2=e_k^2$$

即每步误差平方，$t$ 步后精度达到 $2^t$ 位，因此对 $n$ 比特模数只需 $O(\log n)$ 步。每步的代价是一次模乘 + 一次条件减法——注意这就是本卷反复出现的模乘原语。因此牛顿迭代的量子实现可以完全复用已有的模乘与减法线路，代价是总代价约乘以 $\lceil {\log }_{2}n\rceil$。

初始猜测的选择是这套方法的关键难点。 牛顿迭代是局部收敛的，必须有一个粗略正确的初值；而”猜一个初值”在量子线路里不能靠经典输入直接给定（除非模数已知——但它确实已知）。模数 $N$ 是经典常量这一点大大简化了问题：初值可以对 $N$ 在经典机器上算好后作为常量比特线接入。

三、文献现状：三处相邻区域与一处空白

按本轮核实的边界，可以画一张清晰的能力地图：

方向	核实结果	能否引用
纯经典的模 $2^w$ 乘法逆元算法	有：Hurchalla 改进 Dumas 方法，给出证明，并说明该算法与牛顿迭代密切相关	可引，但须标注”纯经典”
量子浮点除法线路（Newton–Raphson）	有：QM021	可引，但须标注”浮点”
Barrett 型归约（避开显式求逆/除法）	有：QM010	可引
Shor 模乘的通用架构（含”除常量块”）	有：QM008	可引
量子模乘逆元线路（Shor 求逆所需）	无	不可引

Hurchalla 的经典算法值得多说一句，因为它不只是”一个经典算法”：他的摘要明确指出该算法与更广为人知的牛顿迭代法密切相关，并顺带证明了一批 $k=1,2,3,4,5$ 的小规模直接公式（其中 $k=4,5$ 的公式此前缺证明）。所以它是本词条第二节那条牛顿迭代式在经典侧的严格基础——但它本身是纯经典算法，模数限定为寄存器的原生位宽 $2^w$，不能当作量子求逆线路的来源。

牛顿迭代的每一步：模乘 + 条件减法，可复用已有原语

图里两段 box 分别是迭代式的两项：先算 $ax$，再算 $x(2-ax)$。整条求逆线路的结构就是 $O(\log n)$ 次”模乘 + 条件减法”的循环，这正是它结构上优雅的原因，也是它依赖模乘原语的原因。

四、如实说明：这是一处确认的空白

文献空白

Shor 求逆所需的模乘逆元量子线路，本轮未能核实到文献。 检索覆盖 arXiv API、Crossref、DataCite；可核实到的最接近的两条是 QM023（纯经典算法，模数限定 $2^w$）与 QM021（浮点除法），两者都不能充当量子求逆线路的来源。本词条因此不给该方向任何引用，也不转述任何声称的量子求逆线路结果。

与之对照，“回避显式求逆”的方向是有文献的——Barrett 型归约让模乘根本不需要除法或求逆：Zhang 等报告通用模归约 T 深度约 $O(2^n)$，而 Barrett 归约 $O(n^2)$；Pavlidis 与 Gizopoulos 的架构则用”除常量块”覆盖了常量除法的需求。这两条是本词条推荐的可引替代路线，理由与 modular-division 一致：Shor 的实际需求是判断可逆性（模幂 + 测量即可）与不做显式除法（Barrett 即可），而不是在相干态上求逆。

论文依据

• Hurchalla（2022） —— 给出模 $2^w$ 下乘法逆元的高效经典算法（改进 Dumas 方法，附证明），并明确说明它与牛顿迭代法密切相关；同时证明 $k=\mathrm{1..5}$ 的小规模逆元直接公式，其中 $k=4,5$ 为首个证明。
• Zhang 等（2025） —— Barrett 型归约把模归约的 T 深度从通用路线的约 $O(2^n)$ 降到 $O(n^2)$，是”在模乘中回避显式除法/求逆”这条替代路线的可引证据。
• Pavlidis 与 Gizopoulos（2012/2014） —— 提供含”除常量块”的 Shor 模幂架构（深度约 $2000n^2$、$9n+2$ 比特、总代价 $1600n^3$），覆盖了常量除法需求。
• Gayathri、Kumar 与 Dhanalakshmi（2022） —— 本轮唯一核实到的 Newton–Raphson 量子除法线路，但对象是浮点除法，不能替代精确整数模求逆线路。

未核实项

量子模乘逆元线路未核实到文献。本词条按纪律不给它引用，也不用 QM023（经典）或 QM021（浮点）替代它。

延伸阅读

• modular-division —— 与求逆纠缠的另一处空白。
• modular-multiplication —— 牛顿迭代所依赖的模乘原语。
• index —— Shor 预处理与周期搜索的全流程。