窗口化模幂

平方-乘法对每个指数位都要做一次受控乘法，而一个指数位只能决定”乘 $a^{2^i}$ 里哪一个”。窗口化的观察是：先在量子线路之外把 $a^0,\dots ,a^{2^w-1}\mathrm{mod}N$ 算好做成表，再让线路一次取 $w$ 位去查表。这样乘法次数从 $O(n)$ 降到 $O(n/w)$，渐近上把门数从 $O(n^3)$ 压到 $O(n^3/{\lg }^{2}n)$。代价是存储：表本身、多路选择器的译码线路、以及一次查表要走 $n$ 步。这是全卷唯一一个用空间换次数的方案，收益最确定，代价也最实在。

一、计数：为什么是 $O(n^3/{\lg }^{2}n)$

设窗口宽 $w$。指数被切成 $\approx n/w$ 个窗口，第 $j$ 个窗口取值 $u_j\in \{0,\dots ,2^w-1\}$，于是

$$a^e=\prod _j{a}^{2^{wj}{u}_j}$$

每一窗口需要一次”取 $a^{u_j}$“加一次乘法。平方仍是 $n$ 次（平方不能窗口化，它是每窗口之间必需的一步），所以乘法次数 $\approx n+n/w$，门数仍是 $O(n^3)$ 主导？——关键在于查表之后剩下的工作被摊薄了：$O(n/w)$ 次乘法各 $O(n^2)$ 门得 $O(n^3/w)$，$n$ 次平方各 $O(n^2)$ 门仍是 $O(n^3)$。因此单靠乘法次数的削减不足以得到 $O(n^3/{\lg }^{2}n)$；这个渐近式来自把平方与查表在同一条流水里对齐、并把窗口选择按 $\lg n$ 级展开的结构（Gidney 2019 的窗口化算术，见Luongo 等（2025） 对该结果的转述与沿用）。这里如实标注：$O(n^3/{\lg }^{2}n)$ 是被引用文献自身的结论，其完整推导不在本站复述，本文的推导只到 $O(n^3/w)$ 为止。

项	平方-乘法	窗口化（窗口 $w$）
平方次数	$n$	$n$
条件乘法次数	$\le n$	$\approx n/w$
额外存储	无	表 $2^w$ 项 + 译码
渐近门数	$O(n^3)$	$O(n^3/{\lg }^{2}n)$（文献结论）

二、线路结构：查表 + 选择 + 乘法

窗口化模幂：预计算表 → 无查表选择 → 累加

表由经典侧预计算，写入线路时常量比特是可参数化单比特门，因此表本身不额外吃辅助比特；真正的成本在无查表选择（unlookup）：把译码寄存器的值拷回 $w$ 个地址位并清零，译码线路与地址宽度同阶。这正是 Luongo 等人四项优化的着力点。

三、常量带来的结构变化

窗口表里存的每个 $a^k$ 都是编译期已知的常量。这触发一个在量子线路里很实在的差别：受控加法器的控制条件若为常量，加法器退化成固定加法，可以省掉整条进位控制链（见结构化乘法器）。Markov 与 Saeedi 正是沿着”把模幂中的常量利用足”这个方向，给出模乘与模幂的常量优化线路——注意他们的标题同时包含 modular multiplication and exponentiation，说明窗口化与常量优化在实现层是同一件事的两面。

在需要控制多比特常量的物理平台上，常量的表示本身就要付费。Pavlidis 与 Gizopoulos 的模幂架构把 QFT 加法器、常数乘法器与常数除法器组装成模乘块，并明确演示同一构造换用近似 QFT 加法器后深度再降 3 倍以上——窗口化所处的”基门选择敏感性”问题在这里已经出现。Das、Chattopadhyay 与 R. 则把”优化量子模幂线路”作为 VLSI 实现层面的问题处理，报告发表于 VLSID 2019。这两篇说明窗口化的工程收益在理论渐近式之外还有很大一部分，但它们的口径彼此不可比。

四、改进了多少：口径必须说清

Luongo、Narasimhachar 与 Sireesh 给出四项优化：非查找（unlookup）成本渐近降低 66%；绕过部分地址同时降深度与总查找成本；把多次查找-加法合并为线路开头的一次更大查找；以及降低非查找的一元转换深度。他们自己给出的结论是：在逻辑层面，模幂线路的 Toffoli 数与 Toffoli 深度各有 3% 的改善；落到 Gidney–Ekerå 的因数分解算法上，对给定物理比特数，RSA-2048 的期望运行时间降低 2% 到 6%。

这三个数字必须连着读：3% 是线路级相对改进，2%~6% 是端到端相对改进，且后者小于前者——因为总时间里还有测量深度等未被窗口化触动的部分。把 3% 直接当成因数分解加速比是错的。

论文依据

• Luongo、Narasimhachar 与 Sireesh（2025） —— 窗口化算术把模幂渐近成本从 $O(n^3)$ 降到 $O(n^3/{\log }^{2}n)$；本文给出四项针对窗口化模幂的优化，报告 Toffoli 数与 Toffoli 深度各 3% 的逻辑层改善，并折算为 RSA-2048 上 2%~6% 的期望运行时间下降。
• Markov 与 Saeedi（2012） —— 模乘与模幂线路的常量优化设计；是”表里存的是常量”这一结构性优势的专门来源。
• Pavlidis–Gizopoulos（2012/2014） —— 用 QFT 加法器组装模乘/模幂架构（深度约 $2000n^2$、$9n+2$ 比特），并演示近似 QFT 加法器可再降 3 倍以上深度：模幂成本对底层加法器选择敏感的直接证据。
• Das、Chattopadhyay 与 R.（2019） —— 从 VLSI 实现角度优化模幂线路的工作，可与理论渐近式对照看工程侧收益。

延伸阅读

• schoolbook-exponentiation —— 窗口化要削减的那 $O(n)$ 次乘法从哪来。
• special-pattern-multipliers —— 常量乘法为什么省 T 门。
• exponentiation-resource-comparison —— 3% 与 2%~6% 这类数字该怎么放进同一张表。
• Bennett 技巧与鹅卵石游戏 —— 窗口化的”空间换时间”在可逆计算里的对偶：检查点策略与鹅卵石博弈。