乘法资源对比

把三篇论文里的乘法器成本排成一张表，几乎总会得到错误的结论。原因不在于谁在夸大，而在于口径不同：T 数可能只算加法器的 T 而不计多控分解的 T；深度可能按”逻辑层深度”或”物理层深度”报；比特数可能包含或不包含纠错开销；对比基线可能是一个特别弱的实现。本词条给出一套可以照着做的对齐口径，并把各篇论文报告的数字连同它们的限定条件一起列出——限定条件和数字同样重要。

一、三种量不能互相换算

容错算术的标准口径是三个量：$T$ 数（Clifford+T 门集下非 Clifford 门的个数）、逻辑比特数、逻辑电路深度。它们的换算依赖于表面码距离 $d$、魔法态工厂吞吐率、路由开销等具体假设，而不同论文用的假设常常完全不同（见gate-cost-models）。

一个具体的错位例子：Gidney 报告把 $n$ 位加法器的 T 数从 $8n+O(1)$ 降到 $4n+O(1)$（用”临时逻辑与”），这个改进适用于整数算术、模算术、旋转合成、QFT、Shor 的 oracle 等一整类构造。若一篇乘法论文的 T 数是在 $4n+O(1)$ 的加法器上测的，另一篇是在 $8n+O(1)$ 的加法器上测的，两者的 T 数不可比。

同一乘法器的三种报法，各自缺了什么

图中三段是同一份算术结构的三个层次。跨论文对比前必须先确定对方报的是哪一层，否则数字差三倍也可能只是口径差。

二、逐篇报告的数字与限定条件

以下数字全部来自各文献自述，每一条都附上它自己的限定条件：

来源	报告内容	限定条件
QM001	空间 $O(n^{1.427})\to O(n)$，保持 $O(n^{\lg 3})$ 门	门复杂度未变；收益在辅助比特一侧
QM002	空间 $O(n^{1.585})\to O(n^{1.427})$	条件是操作数宽度不到原来两倍
QM003	Toom-Cook 的 Toffoli 数与比特数的界	渐近上优于 schoolbook 与 Karatsuba
QM004	$4n+1$ 比特、无垃圾输出；T 数相对 Babu/Lin/Jayashree 省 47.55%/62.71%/26.30%	相对特定基线；基线本身的口径未统一
QM005	在离子阱 / 超导 / Majorana 上用 Azure Resource Estimator 对 Karatsuba、schoolbook、windowed 乘法做对比	是跨平台对比，不与文献中的绝对 T 数混用
QM006	$n$ 位加法器 T 数 $8n+O(1)\to 4n+O(1)$	加法器层面的改进，会传导到所有用到它的乘法器
QM008	深度约 $2000n^2$、$9n+2$ 比特、总代价 $1600n^3$	$n$ 为待分解数的位宽；用近似 QFT 可再降三倍以上深度
QM010	通用模归约 T 深度约 $O(2^n)$，Barrett 归约 T 深度 $O(n^2)$	针对模乘器中的归约步骤，不是整个乘法器
QM013	ZX 重写后辅助比特与 T 门显著下降	未给出与 Karatsuba 等的并置绝对值对比
QM014	在算术基准上 T 数优于既有优化方法	优化器输出未必保持线路可解释性
QM015	量子线 ${\log }_{2}n$、深度 $O(\log n)$、时间 $O(n\log n)$、门 $O(n)$	另需 $O(n)$ 态制备辅助比特；测量基线算法
QM016	深度与 T 深度均 $O({\log }^{2}n)$、$O(n^2)$ 门与辅助比特	作者称其为 Clifford+T 模型下最低 T 深度
QM017	Toffoli 深度最多降 46.018%、T 门降 34.483%–86.25%	对比对象是 6–16 比特输出规模下的一个非分布式乘法器
QM019	加法器型平方器 $O(n^2)$ 门 + ancilla；QFT 型 $O(n^3)$ 门无 ancilla	平方器，不是通用乘法器
QM024	提出量子累加器/乘法器/除法器模型	应用导向建模，非算术线路的优化工作

从这张表能读出一个共同问题：几乎所有百分比都是”相对某一个基线的改进”，而不是绝对值。QM004 与 QM017 尤其典型——把它们与其他论文的绝对 T 数并置是错的。

三、跨平台对比的第三条路

Hansen、Joshi 与 Rarick 的做法绕开了口径不一致：他们不自己写线路，而是用 Azure Resource Estimator 在离子阱、超导与 Majorana 三类平台上，对 Karatsuba、schoolbook、windowed 三种乘法算法做统一假设下的资源估算。这种做法的价值在于同一套假设贯穿所有被比较的对象，因此结论（哪种算法在哪种平台上更划算）是站得住的；而跨论文摘数字则没有这个保证。

实践中的建议顺序是：先确定自己的成本模型（物理比特预算、魔法态吞吐、容错周期数），再在这个模型内比较算法族；如果目的是挑算法而非报数，优先看 QM005 这类统一假设下的对比；如果目的是引用别人的数，必须连同限定条件一起引。

同一算法在三种成本口径下的对比流程

论文依据

• Hansen、Joshi 与 Rarick（2023） —— 用 Azure Resource Estimator 在离子阱、超导与 Majorana 上对 Karatsuba、schoolbook、windowed 乘法做资源对比，是本卷口径最统一的对比工作。
• Gidney（2019） —— 提供”辅助比特可改善而门复杂度不变”的具体范例（$O(n^{1.427})\to O(n)$，保持 $O(n^{\lg 3})$ 门）。
• Munoz-Coreas 与 Thapliyal（2017） —— 提供”相对基线的百分比”式报告的典型案例（$4n+1$ 比特；相对 Babu/Lin/Jayashree 省 47.55%/62.71%/26.30% T）。
• Gidney（2018） —— 提供加法器层面 T 数的改善（$8n+O(1)\to 4n+O(1)$），说明为什么跨论文的乘法器 T 数不可直接并置。
• Gaur 与 Thapliyal（2025） —— 提供”百分比 + 有限对比规模”的典型案例（Toffoli 深度最多 −46.018%、T 门 −34.483% 至 −86.25%，规模 6–16 比特输出）。
• Dobbs 等（2021） —— 提出把量子线路建模为排队网络以快速提取并行度与 SWAP 持续时间，是布局布线阶段成本预测的一条工具性证据。

延伸阅读

• gate-cost-models —— 三种量为什么不能互相换算。
• in-place-multiplication —— 辅助比特这一侧能优化到什么程度。
• modular-multiplication —— 把乘法包进模归约后的成本结构。