模幂变体的资源对比｜量子算术运算线路知识库

模幂是整个量子算术里最贵的一段，也是各家方案分歧最大的一段。但"哪个方案更好"这个问题，如果只报 T 数，答案往往会反过来——因为降低 T 数的手段通常同时抬高了深度，而深度才是魔法态工厂能不能跟上的瓶颈。这一页把本卷的七种变体放在同一张表上，并说明每一列的口径为什么不能直接比。

先说清楚：四列指标的口径

指标	含义	常见误读
量子比特	工作比特 + 辅助比特 + 工厂比特	有人只报工作比特，不含魔法态工厂的几十个逻辑比特
T 数	非 Clifford 门总数	把 Toffoli 直接当 1 个门报（实为 7 个 T）
深度	最长门依赖链	与 T 深度混用；只对 mod $2^{n}$ 有意义的”丢弃进位”版本深度会虚低
墙钟时间	工厂产 T 的速度能否喂饱深度	用 T 数直接排序，忽略工厂规模差异

同一张表里，只要两篇论文的工厂规模假设不同，墙钟时间就不可比。 这是模幂文献最常见的伪比较。

变体	量子比特	结构	主要取舍	详见
教科书式	$O (n)$ 工作 + $O (n)$ 辅助	平方-乘，逐位条件乘	最好懂、最容易验证；T 数与深度都在 $O (n^{3})$ 量级	schoolbook-exponentiation
窗口化	预计算表 $O (2^{w})$ + 工作	预计算 $a^{2^{i}}$ 表，再按窗口位选	预计算表吃比特，但把模乘次数从 $2 n$ 降到 $2 n / w$	windowed-exponentiation
Zalka 半经典	$O (1)$ 工作 + $O (n)$ 经典	每轮只留一个量子比特	量子比特大幅下降；需要 $O (n)$ 轮串行，且每轮都要测量	semiclassical-exponentiation
semi-QPE	$O (1)$ 工作 + $O (n)$ 经典	相位比特逐位消耗	同上，但用更省的相位比特安排	semi-qpe
复合方案	表 + 半经典	把 $n$ 次调用折叠成 $2^{k}$ 次	深度显著下降；进位链变成新瓶颈	repeating-exponentiation
抽取与归约	同上	$k_{1} / k_{2}$ 层数、指数预处理	常是最大的单点收益，且不改变线路结构	exponent-reduction-tricks
端口与架构	同上	非邻居互连 vs 最近邻	互连模型直接改写渐近式，见下	shor-circuit-roadmap

多数论文把”换个模幂结构”当作主要贡献，但在固定 $N$ 的因数分解里，先决定抽多少位、指数取哪一层、是否提前归约，往往能省下比换结构更多的东西——而且不增加任何比特。这些都是编译期决策，与线路结构正交。见exponent-reduction-tricks。

van Meter 与 Itoh 的分析给出一条值得记住的对比：加法在只允许邻居互连的架构上受限于 $O (n)$ 时间，而允许非邻居互连的架构可以达到 $O (l g n)$ 。 同一个模幂线路图，在不同互连模型下渐近行为完全不同。这把”架构”从实现细节变成了模幂优化的一等变量。

Vedral、Barenco 与 Ekert 在最早的系统性算术线路工作里就指出：模幂是 Shor 中时间与空间上最困难的部分，且可逆实现所需的辅助存储随被分解数的位数线性增长。这决定了 Shor 的物理比特估算里，很大一块是给算术辅助位而非工作位的——参见门代价模型。

按顺序问四个问题：