结构化乘法器

教科书乘法与 Karatsuba 都假定两个操作数都是”活的”——线路必须对任意 $n$ 比特输入都成立。只要结构信息能提前拿到，这个假定就可以放松，四类路线各自吃掉一种结构：编译期已知的常量、被编码成叠加态的指数、分布在多台设备上的模分解、以及可以用 QFT 承载的乘加。它们各有明确代价，本词条按”省了什么 / 付了什么”逐条对照，不把渐近记号当成等价交换。

一、常量乘法器：把控制条件编译掉

当一个操作数是编译期已知的常量 $c$，教科书乘法里的 $n$ 次受控加法全部退化为受条件常量控制：$b_i$ 变成一个可求值的比特序列，受控加法器里的 CNOT 链变成固定比特上的加法器阵列。Munoz-Coreas 与 Thapliyal 把这一点写进设计方法：受控加法的操作数为零时，该受控加法器由一组 Toffoli 门替代，进一步节省 T 门。

同一行累加：变量操作数（受控加法器） vs 常量（Toffoli 阵列）

常量的收益在 Shor 模幂里特别大：模幂的每一轮里，$2^r\mathrm{mod}N$ 往往可以作为常量处理。Pavlidis 与 Gizopoulos 的 QFT 路线正是围绕”乘常量 / 除常量”这两类块构造的，他们用 QFT/Draper 加法器族把它们组装成通用模乘子，进而给出深度约 $2000n^2$、$9n+2$ 比特、总代价 $1600n^3$ 的模幂架构；若对每个加法器单元用近似 QFT，深度还可再降三倍以上。Markov 与 Saeedi 走的是另一条路：把”找紧凑的 $Cx\mathrm{mod}M$ 线路”化为最短路问题，说明在有零初始化辅助寄存器时，针对具体 $C$ 与 $M$ 的优化有相当空间。

二、指数编码乘法器：宽度从 $n$ 压到 ${\log }_{2}n$

Zhan 的 QMbead 换了个编码：把两个乘数用指数编码表示成两个叠加态（由状态制备方法准备好），再用量子加法器把这两个态相加，测量加法器输出后算出乘积。结果是：乘两个 $n$ 比特整数只需 ${\log }_2(n)$ 个量子比特，加上 $O(n)$ 个用于态制备的辅助比特；配对数深度 QCLA 时电路深度为 $O(\log n)$、时间复杂度 $O(n\log n)$、门复杂度 $O(n)$。作者报告其深度与门复杂度优于量子 Karatsuba 乘法器与 QFT 型乘法器，时间复杂度与经典最快的 Harvey–Hoeven 算法相同，并在模拟器上用 17 个比特（不含态制备辅助位）算出了最高 273 比特长的乘积。

这条路线的代价写在定义里：它是测量基线上的算法，不产生相干输出，且态制备本身要花 $O(n)$ 个辅助比特与相应门数。它与 Shor 需要的”相干可逆乘法器”不是同一类东西——后者要求输出保持叠加态以继续模幂的累加。

三、RNS 分布式乘法：把宽度平方换成设备数

Gaur 与 Thapliyal 的思路是利用余数系统：整体乘法分解成若干个小的模乘法，分别放到不同量子计算机或不同 job 上跑。核心部件是”Diminished-1”模 $2^n+1$ 乘法器——这种模数的减法是”补码加法”，比一般模减法便宜。他们在 6 到 16 比特输出规模上与一个已有的非分布式乘法器对比，估算 Toffoli 深度最多降低 46.018%、T 门降低 34.483% 至 86.25%。

要读懂这个数字必须连着它的口径一起读：对比对象是特定的一个非分布式乘法器，输出规模是 6–16 比特，而百分比区间跨度极大（34.483%–86.25%）说明收益强烈依赖具体的分解方式。

四、QFT 乘加：不走位宽平方

Maynard 与 Pius 考虑的是混合线路：经典表示的整数送进量子线路做特定计算模式，再读回经典结果，作为常规计算机架构里的量子加速器。其基于 QFT 的量子乘加（QMAC）把”对 $k$ 比特整数做 $n$ 次乘加”的经典并行步数从 $O(n\log k)$ 降到精确结果 $O(n+k)$、近似结果 $O(n+\log k)$。这条路线的结构特点是深度极浅但门数多——同一位移在 Noto 的 QFT 型平方器上体现为 $O(n^3)$ 门、零辅助比特，正好是加法器型平方器（$O(n^2)$ 门 + ancilla）的镜像取舍。

五、四条路线的对照

路线	被利用的结构	主要收益	付出的代价
常量乘法	编译期已知的乘数	去掉控制链与大量 T 门	只对固定常量成立；$4n+1$ 比特的宽度仍在（QM004）
QFT 型	傅里叶域上的乘加	深度浅（$O(n)$ 量级），$2000n^2$ / $9n+2$（QM008）	门数高；精确 QFT 型平方器 $O(n^3)$ 门（QM019）
指数编码	乘数以叠加态编码	量子线压到 ${\log }_{2}n$、深度 $O(\log n)$（QM015）	需测量读出；$O(n)$ 态制备辅助比特与门
RNS 分布式	模分解到多设备	Toffoli 深度最多 −46.018%（QM017）	跨设备通信；对比口径限于 6–16 比特输出

论文依据

• Munoz-Coreas 与 Thapliyal（2017） —— 明确指出受控加法器的操作数为零时可用 Toffoli 门阵列替代以节省 T 门；给出 $4n+1$ 比特、无垃圾输出的整数乘法器与 T 数对比。
• Pavlidis 与 Gizopoulos（2012/2014） —— 用 QFT/Draper 加法器族构造乘常量/除常量块并组装成模乘子，提供深度约 $2000n^2$、$9n+2$ 比特、总代价 $1600n^3$ 的报价，以及近似 QFT 带来的三倍以上深度下降。
• Markov 与 Saeedi（2012） —— 把面向具体 $C$、$M$ 的紧凑模乘线路搜索化为最短路问题，指出部分构造渐近小于既有方案但最坏与平均规模仍为 $\Theta (n^2)$。
• Zhan（2023） —— 指数编码乘法器 QMbead：${\log }_2(n)$ 个量子比特加 $O(n)$ 态制备辅助位，深度 $O(\log n)$、时间 $O(n\log n)$、门 $O(n)$。
• Gaur 与 Thapliyal（2025） —— RNS 分布式量子乘法与 Diminished-1 模 $2^n+1$ 乘法器，报告 Toffoli 深度最多降 46.018%、T 门降 34.483%–86.25%（对比规模为 6–16 比特输出）。
• Maynard 与 Pius（2013） —— 基于 QFT 的混合量子乘加，$n$ 次 $k$ 比特乘加从经典 $O(n\log k)$ 步降到精确 $O(n+k)$、近似 $O(n+\log k)$ 步。
• Noto（2020） —— 加法器型平方器 $O(n^2)$ 门 + ancilla 与 QFT 型平方器 $O(n^3)$ 门无 ancilla 的并置对比。

延伸阅读

• schoolbook-multiplier —— 常量化的起点。
• modular-multiplication —— 常量与 QFT 两条路线的汇合处。