重复平方与折叠

平方-乘法的 $2n-1$ 次模乘里有大量结构重复：平方本身就是”把同一个操作做两次”，连续平方是”做 $2^k$ 次”。如果能直接实现 $U^{2^k}$，链条就折成 $n$ 个 $k$ 比特计数器。本文讲这条路的通用形式（$n$ 次相同操作 → 一次受控幂）、它对物理互连的异常敏感（同一份线路在邻居架构上是 $O(n)$、在非邻居架构上是 $O(\lg n)$），以及一条完全绕开折叠、改用离散傅里叶变换构造模乘的替代路线。

一、折叠的一般形式

要实现”把 $U$ 做 $n$ 次”，最直接的办法是加一个计数器：每次作用给计数器加一，作用完后按计数器的值施加 $U^{2^k}$。计数器用 $n$ 比特的半加器链实现——每次作用把最低位翻转，若翻转则向高位进位，一路传播。因此每个作用位需要一次受控非门加一层受控相位门。

折叠 n 次作用为一次受控幂：半加器链计到 2^k

图里 u 是承载算术作用的那根线，计数器三根线用 repeat 示意可扩展到 $n$ 根。这个结构有一个容易被忽略的性质：进位是串行传播的。 计数器加一的深度是 $O(n)$，而不是 $O(\lg n)$——因为进位必须逐位走完。这意味着折叠并不能自动降低深度，它只是把”串行模乘”换成了”串行进位”。

二、互连方式为什么会改写渐近式

van Meter 与 Itoh 对模幂的系统分析里，最有迁移价值的一条不是任何一个倍数，而是这句对比：加法在只允许邻居互连的架构上受限于 $O(n)$ 时间，而允许非邻居互连的架构可以达到 $O(\lg n)$。 这解释了为什么同一个线路图在不同硬件上渐近行为会变——平方-乘法的深度下界有相当一部分来自物理互连与进位传播，而不是来自线路设计本身。他们的具体结论是在存储取 $100n$（最小 $5n$ 的二十倍）时，$n=128$ 的模幂比优化过的基本算法快两百到七百倍，视架构而定。

van Meter 的博士论文把同一套分析推到 qubus 多计算机架构：量子多计算机由大量小节点加一条 qubus 互连组成，其首要性能指标就是 Shor 算法里的模幂步骤；他给出的算法把 $n$ 位数模幂的深度从 $O(n^3)$ 降到 $O(n{\lg }^{2}n)$ 或 $O(n^2\lg n)$，视架构而定，并在 6000 位因数分解上报告一百万倍与一万三千倍两种加速。论文还考察了五种 qubus 互连拓扑，并找到两种进位链加法器在大部分性能参数下最快。

这条线的价值在于它把”架构”变成了模幂优化的一等变量。 后来的端到端成本估算继承了这个视角：Gidney–Ekerå 的物理假设明确写着平面最近邻网格、$10^{-3}$ 特征门错误率、表面码周期 1 微秒、反应时间 10 微秒——最近邻互连是一个被写进成本模型的参数，不是默认前提。

三、另一条路：不折叠，直接用 DFT 构造模乘

Patoary、Vikram 与 Galitski 换了个出发点：先建立模乘算子与离散傅里叶变换的各种推广之间的关联，据此给出模幂线路，其线路可以完全由标准的傅里叶变换线路及其变体构成，门复杂度为 $O(L^3)$（$L$ 是待分解数的存储位数）。他们强调两点：其一，实验上实现 Shor 的瓶颈正是模幂；其二，这种构造不需要针对具体待分解数做定制，与已有实现”常常显式地为待分解数调整线路”形成对比。常数乘法在窗口化路线里的价值见windowed-exponentiation。

四、这条路线在整体谱系中的位置

Gidney 与 Ekerå 的摘要直接列出了他们所综合的技术来源：Shor 1994、Griffiths–Niu 1996、Zalka 2006、Fowler 2012、Ekerå–Håstad 2017、Ekerå 2017、Ekerå 2018、Gidney–Fowler 2019、Gidney 2019。这份清单里没有”van Meter–Itoh 折叠”的身影，但包含 Griffiths–Niu 1996（即 Yoran–Short 用来做模拟论证的那条半经典路线）与 Zalka 2006。当代端到端估算走的其实是半经典路线，折叠路线更多贡献的是对深度与互连关系的理解。 各条路线的比特数与深度数字见exponentiation-resource-comparison。

论文依据

• van Meter 与 Itoh（2005） —— 系统分析架构特征与并发门执行对模幂的影响，给出 $100n$ 存储下 $n=128$ 快两百至七百倍的结论，以及”邻居架构加法受限于 $O(n)$、非邻居架构可达 $O(\lg n)$“这一互连相关性结论。
• van Meter（2006） —— 博士论文，把模幂深度从 $O(n^3)$ 降到 $O(n{\lg }^{2}n)$ 或 $O(n^2\lg n)$，在 qubus 多计算机架构上比较五种互连拓扑与两种进位链加法器，并报告 6000 位因数分解上一百万倍与一万三千倍的加速。
• Patoary、Vikram 与 Galitski（2025） —— 基于模乘算子与离散傅里叶变换推广之间的关联构造模幂线路，线路完全由标准 DFT 线路及其变体构成，门复杂度 $O(L^3)$，且无需按待分解数定制。
• Gidney 与 Ekerå（2019/2021） —— 摘要明确列出所综合的技术谱系（Shor 1994、Griffiths–Niu 1996、Zalka 2006、Fowler 2012、Ekerå–Håstad 2017、Ekerå 2017、Ekerå 2018、Gidney–Fowler 2019、Gidney 2019），并把最近邻互连明确写进物理假设。

延伸阅读

• schoolbook-exponentiation —— 被折叠的那条 $2n-1$ 次乘法链。
• semiclassical-exponentiation —— 折叠在模幂一侧的另一种形态。