指数削减技巧

本卷此前的改进都在”把每次乘法做便宜”，或者”把乘法次数做少”。还有一整类改进根本不动乘法结构，而是直接删掉算子的一部分。它的依据只有一句话：Shor 在测量之后用连分数法从相位里抽取周期，而连分数只需要近似的相位值。既然如此，模幂算子就不必精确实现。这是本卷找到的最激进的深度削减方案，实测在这些小例子上能省掉一半以上的层数。

一、三个观察

Singleton 的截断模幂方案由三个观察叠成。

观察一：工作寄存器初态是 $|1⟩$。 因此不必构造一个接受一般输入的模幂算子 $U$，只需要它作用在周期状态序列 $|f(x)⟩$ 上，其中 $x\in \{0,1,\dots ,r-1\}$，$f(x)$ 是周期为 $r$ 的模幂函数。这个约束极强：$U$ 的输入被限制在 $r$ 个特定状态上，而不是整个 $2^{2n}$ 维空间。

观察二：$U$ 可以分成 $r$ 层。 第 $x$ 层的门把 $|f(x)⟩$ 增到 $|f(x+1)⟩$；低于 $x$ 的层对 $|f(x+1)⟩$ 完全不影响。于是”逐层执行 $U$“就是沿周期走一圈，每层只负责一步。这把一个深度为 $O(n^3)$ 的黑箱算子换成了 $r$ 层可枚举的门——层数与深度的关系从此变成线性的。

观察三：这套做法有一个自我否证的陷阱。 如果已经知道算子 $U$，那么也就知道周期 $r$，Shor 算法本身就没有必要了。这是方案在提出时最难处理的一点。

二、深度换不回来，但抽取够用

Singleton 给出的处理方式是：不去解决那个陷阱，而是证明模幂算子”相当宽容”——省略了部分层的截断近似形式，抽取因子的效果与精确算子一样好。他在 $N=21,33,35,143,247$ 上用不到所需层数一半的层完成因数分解。同一组结论在他的教科书式综述里也出现过（模幂算子”somewhat forgiving”，截断近似形式能一样好地抽取因子），那里的解释相同：连分数法只需要输入一个近似的相位值。

被省略的层不是被”补偿”回来的，而是靠后续组合抹平的。Singleton 给出的完整策略是一个逐步填充的过程：给模幂算子里的线路逐渐填入更多门，利用各个复合算子 $U^p$（$p$ 为 2 的幂）之间的相关性来补偿缺失的层。也就是说，“少做一半”的线路单独看是不准的，但在 $U,U^2,U^4,\dots$ 构成的测量序列里，误差互相抵消。

按层截断：第 x 层把周期上的相邻两个状态连起来

图中”保留”与”省略”两层是同一结构在层计数推进下的两种状态。注意省略的是层，不是门：省略一层意味着那一整段模乘门全部不做，这是 $O(n^2)$ 量级的节省，而不是常数优化。

三、能推广到哪里、不能推广到哪里

这个方案成立的前提有两个，缺一不可。其一，下游算法对相位精度宽容——连分数法满足这一点，但如果下游需要精确相位（例如要把 $U^p$ 用在受控方式下做精确幂运算），前提就不成立。其二，$r$ 相对于模幂本身的层数足够小；否则”分成 $r$ 层”这一步本身就不可行。这两条限制决定了它目前只在小规模与中等规模的因数分解上被完整演示过，而不是一个能替代窗口化方案的普适改进。

它与本卷其它路线的关系是正交的：窗口化削减乘法次数，指数削减削减层数，QFT 型加法器削减单次乘法深度，三者可以叠乘。Singleton 早前的教科书式综述与本条一起，构成”模幂算子可以按需裁剪”这一主张的完整证据链。

论文依据

• Singleton（2024） —— 提出按周期 $r$ 分层的模幂算子构造方法，指出工作寄存器初态为 $|1⟩$ 因而不必构造接受一般输入的算子、低于 $x$ 的层对 $|f(x+1)⟩$ 无作用；用不到一半层数分解 $N=21,33,35,143,247$；给出”通过逐步填充更多门、利用 $U^p$ 之间的相关性补偿缺失层”的完整策略。
• Singleton（2023） —— 教科书式综述中独立给出同一结论：模幂算子”somewhat forgiving”，截断近似形式抽取因子的效果与精确算子相同，原因是连分数法只需要近似相位值。

延伸阅读

• modular-exponentiation-overview —— 未截断的模幂算子长什么样。
• windowed-exponentiation —— 与本条正交的另一条削减路线。