平方-乘法指数化

平方-乘法（square-and-multiply）是模幂最直接的量子实现：$n$ 次平方加上至多 $n$ 次条件乘法，串起来就是整条链。它慢，而且慢得没法回避——但它是所有后续改进的参照系。本文先把它的深度与比特账逐项算清，再给出三条改变账目的路线：极低比特（$2n+3$、$9n+2$）、以空间换延迟（$100n$）、以及把乘法链折成算术序列叠加。

一、逐层可数的结构

从高位往低位扫指数位，累加器初值 $1$，第 $i$ 步：

$$\text{acc}\leftarrow {\text{acc}}^2\mathrm{mod}N,\text{acc}\leftarrow a^{\pm e_i}\cdot \text{acc}\mathrm{mod}N$$

不变量：扫完第 $i$ 位，$\text{acc}=a^{e\gg (2n-1-i)}\mathrm{mod}N$。因此平方 $2n-1$ 次、条件乘法至多 $2n$ 次，全部串行。门数方面，单次 $2n$ 位乘 $n$ 位再归约约 $O(n^2)$，故总量 $O(n^3)$；深度若严格串行同样是 $O(n^3)$。注意这里有两个独立的 $O(n)$（次数、位宽）与一个 $O(n^2)$（单次模乘）相乘——所有改进都落在其中一项上。

比特账的下界来自三处必须同时存在的存储：累加器 $2n$、被乘常量 $n$、加法器进位 $O(n)$，约 $5n$。van Meter 与 Itoh 正是把这个量当作单位记为”最小 $5n$“，他们给出的所有加速都以它的倍数计。

平方-乘法：平方无条件，条件乘法受控于指数位，两步串行重复

图中只有一条指数线，迭代层数用 repeat 展开。$e$ 线上的受控是唯一的控制点：MUL 阶段里”乘不乘 $a$“由它决定，MOD 阶段无条件执行。把这条链拆成这两段，就得到了模幂总览里的阶段划分。

二、三条改账路线

极低比特。 Beauregard 给出用 $2n+3$ 个比特、$O(n^3\lg n)$ 个初等门、深度 $O(n^3)$ 的完整因数分解线路，并强调它不依赖待分解数的任何性质，因此完全通用；关键设计是把测量基的傅里叶变换显式算出来，从而摆脱原论文里”需要量表寄存器”的实现负担。Pavlidis 与 Gizopoulos 走得更极端：用 QFT 型加法器搭出乘常量与除常量的算术块，组装成通用模乘器，再嵌进模幂，得到的线路深度约 $2000n^2$、需要 $9n+2$ 个比特、总量子成本 $1600n^3$。$2n+3$ 与 $9n+2$ 不是同一条路线上的两个数字：前者靠改写顶层结构（省掉量表寄存器），后者靠换加法器与乘法器的实现族（深度换比特）。两者不可直接比较。

以空间换延迟。 van Meter 与 Itoh 系统考察架构特征对模幂的影响：存储取 $100n$（最小 $5n$ 的二十倍）时，$n=128$ 的模幂比优化的基本算法快两百到七百倍，视架构而定；他们同时指出，加法在只允许邻居互连的架构上被限制在 $O(n)$ 时间，而允许非邻居互连的架构可以做到 $O(\lg n)$。这句话的后半段常被略去，但它才是重点：平方-乘法的深度下界有相当一部分来自物理互连，而不是来自线路本身。van Meter 的博士论文把这条线推到 qubus 多计算机架构上，把 $n$ 位数的模幂深度从 $O(n^3)$ 降到 $O(n{\lg }^{2}n)$ 或 $O(n^2\lg n)$（视架构），并在 6000 位因数分解上报告快一百万倍与一万三千倍两种结果。

把乘法链折起来。 Zalka 的《更少（纯）量子比特的 Shor 算法》给出三点：其一，在约 $2n$ 个量子比特中没有一个需要被初始化（尽管后续仍要做通常的 $2n$ 次测量）；其二，模加法可以用”算术序列的叠加”完成，这让 Shor 的并行化更容易；其三，最终可以只用约 $1.5n$ 个比特完成因数分解，也许还能更少。第二点是本卷半经典模幂的入口：把 $n$ 次受控模乘折叠成”初始态是一次算术序列的叠加”，深度结构因此改变。

三、为什么它是参照系

窗口化（windowed-exponentiation）把乘法次数降到 $O(n/\lg n)$，半经典路线（semiclassical-exponentiation）把次数折起来，更激进的指数削减直接按层删除。任何一条改进要证明有效，都得先用本文这套计数在同一位宽上跑一遍基线。

论文依据

• Beauregard（2003） —— 给出 $2n+3$ 比特、$O(n^3\lg n)$ 门、深度 $O(n^3)$ 的完整 Shor 线路，并说明其通用性来自不依赖待分解数的性质；该文是”显式计算测量基 QFT”路线的原始出处。
• Pavlidis 与 Gizopoulos（2012/2014） —— 给出深度约 $2000n^2$、比特数 $9n+2$、总量子成本 $1600n^3$ 的模幂架构，并用 QFT 型加法器构成乘/除常量的算术块；给出用近似 QFT 可再降三倍以上深度的判断。
• van Meter 与 Itoh（2005） —— 以 $100n$ 存储换 $n=128$ 时两百至七百倍加速，并给出”邻居架构加法受限于 $O(n)$ 时间、非邻居架构可达 $O(\lg n)$“这一架构相关性结论，同时确立”最小 $5n$“存储的基准记法。
• van Meter（2006） —— 博士论文，把模幂深度从 $O(n^3)$ 降到 $O(n{\lg }^{2}n)$ 或 $O(n^2\lg n)$，并在 qubus 多计算机架构上评估拓扑与进位链加法器的选择。
• Zalka（2006） —— 给出”约 $2n$ 个比特中无一需要初始化”、用算术序列的叠加完成模加法从而更易并行、以及约 $1.5n$ 个比特完成因数分解三点。

延伸阅读

• repeating-exponentiation —— 把”重复 $n$ 次”直接折成一个受控幂。
• shor-circuit-roadmap —— 这条链在 Shor 顶层里占多大比例。