Shor 算法常被当成一个整体来讲，但它在线路层面是四段结构，而且只有第二段消耗真正的算术原语。第一段是 个 H 门，第三段是线性代数的逆傅里叶变换，第四段是测量加经典数论。第二段——受控模幂——把本站加法卷、乘法卷、模运算卷的全部内容乘以 ，因此它决定了整条线路的成本。本文逐段点名每个算术原语的归属，是本卷与其它各卷之间的接口图。
一、四段结构与各自的账
① 制备叠加。 对指数寄存器上的每根线施加 H 门， 个门，不涉及任何算术。它唯一的作用是把指数的二进制展开变成均匀叠加，让第②段可以把 次条件乘法的结果叠加而不是顺序执行。
② 受控模幂。 唯一昂贵的一段。把它展开就是本卷的核心结构：
按图中每一步点名原语的归属：
- MUL 阶段：乘以常量 ，主体是教科书乘法器；窗口化版本进一步用表驱动，见窗口化模幂；而”乘常量导致受控加法器退化”这一结构差别写在结构化乘法器里。
- MUL 内部的加法：每一行部分积的累加都是一次受控加法，本体是CDKM 加法器（进位链 versus 进位先行的取舍见adder-taxonomy）。
- MOD 阶段： 位压回 位的主体是模归约，它内部的比较与减法回到模减法，加减法的基础件是VBE 进位链。
- 辅助比特：累加器与乘数不能共用同一组线，否则进位会污染乘数，因此这段的空间复杂度由就地乘法决定。
- 整体结构：MUL/MOD 的重复与折叠见重复平方，直接删层见指数削减。
Beauregard、Brassard 与 Fernandez 把受控乘法称为 Shor 算法中唯一与群有关的操作——上面这张账单里，只有”乘什么”与 有关，“怎么乘”是通用整数算术。
③ 逆傅里叶变换。 纯线性代数，不消耗算术原语。Beauregard 方案的贡献正是把这一段的测量基 QFT 显式算出来，从而摆脱原论文中”需要量表寄存器”的负担。若改用逐比特迭代的半经典相位估计，指数寄存器可以从 比特降到 比特，见semi-QPE 与本卷的semi-qpe。
④ 测量与经典抽取。 测得近似相位后用连分数法抽取周期 ，再做经典检验。Singleton 的教科书式综述把这一整段称作后量子处理，并系统给出对任意半素数构造模幂算子的步骤；这也是为什么”截断近似算子一样够用”的结论能在因数分解层面成立，见指数削减。
二、顶层数字为什么差一倍还不可比
| 方案 | 比特 | 出处 | 改的是哪一段 |
|---|---|---|---|
| 门、深度 | Beauregard | 第③段：显式算 QFT | |
| 深度约 、总成本 | Pavlidis–Gizopoulos | 第②段：换 QFT 型加法器 | |
| 约 | — | Zalka | 第②③④段全部半经典化 |
| Toffoli、 测量深度 | Gidney–Ekerå | 端到端，含纠错与调度假设 |
这四行不能排成一张名次表：Beauregard 报的是初等门数与深度，Pavlidis–Gizopoulos 报的是特定加法器族下的深度，Gidney–Ekerå 报的是含物理假设的端到端估算，而三者的比特数分别对应三种不同的第③段处理方式。比特数纪录的差异主要来自第③段与第②段的实现选择，不来自第②段的算术本身。
端到端数字的变化更能说明原语升级如何传导：Gidney 与 Ekerå 估计 2048 位 RSA 可在 8 小时、2000 万噪声比特内分解，其时空体积比 Van Meter 等 2009、Jones 等 2010、Fowler 等 2012、Gheorghiu 等 2019 的估计低一百倍。Gidney 2025 把比特数降到不到一百万、时间放宽到不到一周，比特下降的三个来源是近似剩余算术、yoked surface codes 与 magic state cultivation，运行时间变长的原因是执行了更多 Toffoli、用了更少的魔态工厂。同一方向上，Gouzien 与 Sangouard 用 13436 个处理比特加一台可存 2800 万空间模式与 45 个时间模式的存储器，给出 177 天的分解时间；Xue 与 Covey 则在 50 万比特的模块化原子处理器上、以每秒 个贝尔对的通信率，得到只比单模块多 16% 的运行时间。
三、把整卷接起来
模幂是资源大头（Vedral 等：时间与空间上最困难的部分；Singleton：量子资源部署最多的地方），但顶层结构本身几乎是不可动的——能动的只有第②段的实现。因此本卷的每一个词条都可以被读成对第②段的一次替换：换乘法器结构（平方-乘法）、换乘法次数（窗口化）、换折叠方式（重复平方）、换测量形态（半经典模幂）、直接删层（指数削减）。窗口化那 3% 的线路级改善折算成 RSA-2048 上 2%~6% 的端到端期望时间下降，正是这个传导链条的实测长度。
论文依据
- Beauregard（2003） —— 给出 比特、 门、深度 的完整线路，其关键设计是显式计算测量基 QFT，从而不依赖待分解数的任何性质。
- Beauregard、Brassard 与 Fernandez —— 把受控乘法称为 Shor 算法中唯一与群有关的操作，并给出其线路的规模/宽度/深度分析；这是”第②段之外都是通用整数算术”这一判断的来源。
- Vedral、Barenco 与 Ekert（1995） —— 判定模幂是 Shor 算法中时间与空间上最困难的部分，并证明其可逆实现的辅助存储随待分解数位数线性增长。
- Singleton（2023） —— 发展模幂算子理论并覆盖后量子处理与连分数法，给出对任意半素数 系统构造模幂算子的步骤。
- Pavlidis 与 Gizopoulos（2012/2014） —— 以 QFT 型加法器构成乘/除常量的算术块并组装为通用模乘器，给出深度约 、 比特、总成本 的顶层设计。
- Gidney 与 Ekerå（2019/2021） —— 给出端到端抽象线路成本（ 逻辑比特、 Toffoli、 测量深度）、物理假设，以及 2048 位 RSA 在 8 小时 / 2000 万噪声比特下的估计与时空体积比对照。
- Gidney（2025） —— 把 2048 位 RSA 降到不到一百万噪声比特、不到一周，并指明比特下降来自近似剩余算术、yoked surface codes 与 magic state cultivation，时间变长来自更多 Toffoli 与更少魔态工厂。
- Gouzien 与 Sangouard（2021） —— 处理器加存储器的架构：13436 处理比特、2800 万空间模式与 45 个时间模式存储器，2048 位 RSA 分解耗时 177 天。
- Xue 与 Covey（2026） —— 模块化原子处理器上的分布式 Shor 编译与优化：50 万比特模块、每秒 个贝尔对、1 ms 测量时间，运行时间只比单模块多 16%。
- Zalka（2006） —— 约 个比特中无一需要初始化、用算术序列的叠加完成模加法从而更易并行、最终约 个比特完成因数分解。
延伸阅读
- modular-exponentiation-overview —— 第②段的通用结构。
- exponentiation-resource-comparison —— 上表数字的口径差异。