量子模幂总览

模幂 $a^e\mathrm{mod}N$ 是量子算术里唯一一个”由 $O(n)$ 次乘法串起来”的操作。加法、乘法、模归约各自都能在 $O(n)$ 深度内做完，把它们串 $2n-1$ 次，深度就线性堆积起来。这就是 Shor 因数分解里最贵的一段——本文要回答的是：这条链的最小结构是什么、每一段消耗哪个算术原语、辅助存储为什么省不掉，以及有哪些办法把这条链压扁。

一、二进制展开直接给出算法

把指数写成二进制 $e={\sum }_{i=0}^{2n-1}{e}_i{2}^i$，则

$$a^e=\prod _i{\left(a^{2^i}\right)}^{e_i}$$

这是恒等式，不需要任何数论。换句话说，模幂的每一步只可能是”什么都不做”或”乘上一个编译期已知的常量”。把它排成算法：从高位到低位扫指数，累加器 $\text{acc}$ 初始化为 $1$，每读一位 $e_i$ 先无条件平方 $\text{acc}\leftarrow {\text{acc}}^2$，再在 $e_i=1$ 时乘一次 $a$。不变量可以直接归纳验证：扫完第 $i$ 位后 $\text{acc}=a^{\lfloor e/2^{2n-1-i}\rfloor }\mathrm{mod}N$。于是整条链是 $2n-1$ 次串行的模乘（平方 $2n-1$ 次、条件乘法至多 $2n$ 次），其中平方无条件、条件乘法受控于指数位。这就是全卷反复出现的那张图。

对指数位做条件乘法：一次迭代 = 受控 MUL + 无条件 MOD

图里 $e$ 那根线是指数寄存器的一条比特线（实际 $2n$ 条），$a$ 是编译期常量，$\text{acc}$ 与 $p$ 各占工作寄存器的两半。MUL 阶段内部是 教科书乘法器：乘以常量 $a$ 意味着控制条件可以编译期求值，受控加法器退化成固定加法，所以这一段没有”选择”也没有垃圾。MOD 阶段把 $2n$ 位的乘积压回 $n$ 位，主体是 模归约，其比较与减法部分回到 模减法 与 CDKM 加法器。这两块的具体成本不在本卷，但它们乘以 $2n$ 就是模幂的成本。

二、Shor 的接口：唯一与群有关的操作

这条链之所以值得单独立卷，是因为它在因数分解里的权重极端不对称。Vedral、Barenco 与 Ekert 在最早的系统性算术线路工作里就明确指出：模幂是 Shor 算法中时间与空间上最困难的部分，并且证明可逆实现所需的辅助存储随被分解数的位数线性增长。Beauregard、Brassard 与 Fernandez 更进一步，把受控乘法称为 Shor 因数分解与离散对数算法中 “唯一与群有关的操作”（the only group-specific operation）——这句话把整个成本归因压缩成了一点：除了这次受控乘法，其余都是与 $N$ 的具体取值无关的通用整数运算。

Singleton 的教科书式综述用另一套口径说同一件事：模幂算子是 Shor 算法的基本组件之一，也是”量子资源部署最多的地方”。两条陈述合起来给出一个结构性判断——想降低 Shor 的成本，先看模幂；而模幂的成本里，$2n$ 次乘法是乘法卷成本与模归约卷成本的直接倍数。

三、辅助存储为什么省不掉

平方-乘法的每一步都写全工作寄存器 $p$，用完要清空。可以就地做（就地乘法），但乘数的位仍要与累加器的位分开存放，否则”边加边乘”进位会污染。加法器本身的进位比特又需要单独回收。于是下界来自三处：累加器 $2n$、乘数 $n$、加法器辅助 $O(n)$，合起来约 $5n$ 比特——van Meter 与 Itoh 把这个量称为最小存储，正文里给出的一切加速都是以它的倍数计的。

把这条路推到极致会撞上另一堵墙：$O(n^3)$ 的门数是乘法宽度造成的，不是模幂结构造成的。窗口化（windowed-exponentiation）把乘法次数从 $O(n)$ 压到 $O(n/\lg n)$，渐近上把 $O(n^3)$ 降到 $O(n^3/{\lg }^{2}n)$；但只要单次模乘还是 $O(n^2)$ 门，这个下限就还在。“减少次数”与”降低单次成本”是两条独立的改进路线，本卷的词条基本沿这两条轴排列。

论文依据

• Vedral、Barenco 与 Ekert（1995） —— 最早系统给出 Shor 所需算术线路的工作，明确判定模幂是因数分解中时间与空间上最困难的部分，并证明可逆实现的辅助存储随被分解数位数线性增长。
• Beauregard、Brassard 与 Fernandez —— 给出 GF 上受控乘法的线路规模/宽度/深度分析，并把受控乘法称为 Shor 因数分解与离散对数算法中”唯一与群有关的操作”，是模幂核心内核的定位来源。
• Singleton（2023） —— 系统发展模幂算子的理论，给出对任意半素数 $N=p\times q$ 构造模幂算子的步骤，并说明后量子处理与连分数抽取这一整段流程；正文用”量子资源部署最多的地方”定位其权重。
• Volovich（2001） —— 讲义体例的教科书式模幂推导，可作为本文二进制展开与不变量论证的常规参考。

延伸阅读

• schoolbook-exponentiation —— 把上面的不变量落成逐层可数的线路，并给出两条比特账。
• shor-circuit-roadmap —— 把这条链放回 Shor 的顶层结构，看它到底占掉多少。
• exponentiation-resource-comparison —— 各家数字的口径差异。