教科书乘法器

教科书乘法器（schoolbook multiplier）是把经典竖式乘法逐位翻译成可逆线路的结果：每个操作数比特做一次受控加法，部分积直接累加进输出寄存器。它没有递归、门数是 $O(n^2)$ 渐近，但它是这一卷里唯一可以逐位验证正确性的结构——所有递归与结构化方案都要拿它当基准。它的真实价值不是速度，而是可核对性：一个 Karatsuba 实现对不对，只要和它在小位宽上逐个比对就能确定。

一、经典竖式的三行对应

写出 $a={\sum }_i{a}_i{2}^i$、$b={\sum }_j{b}_j{2}^j$，则

$$ab=\sum _{i,j}{a}_i{b}_j{2}^{i+j}$$

经典竖式乘法做的正是按行聚合：第 $j$ 行把 $a\cdot b_j$ 左移 $j$ 位加进结果。量子版本逐行翻译，第 $j$ 行不是”加不加”的经典选择，而是一个以 $b_j$ 为控制的加法器：

$$z\leftarrow z+(a\ll j)\cdot b_j$$

于是乘法器的主循环是 $n$ 次受控加法，每次加法作用于越来越宽的输出区间：第 $j$ 步之后，输出的高 $j$ 位已经定型、不再变化。这一点直接给出移位即置换的观察——把部分积对齐到位权上的左移，在线路上是纯粹的比特重排，不产生门计数。这一条是结构性推论，本卷未在文献中核实到明确陈述，用到它时应意识到这一点。

教科书乘法：n 次受控累加，循环用 ×n 展开

图中每一对 box 是同一次受控加法作用在输出 $z$ 的不同区间上——加法器与控制线 $b_j$ 的关系被省略，因为受控加法器内部结构属于加法卷。

二、部分积的生成方式与常量特例

上面的写法里，“部分积”是隐式的：加法器直接读 $a$ 的寄存器。另一种写法先显式生成部分积 $a\cdot b_j$，再无条件累加。前者在门数上更省，后者更贴近经典描述。

Munoz-Coreas 与 Thapliyal 明确指出了一个特例：当受控加法的一个操作数为零时（即乘的是编译期已知的常量），受控加器退化为一组 Toffoli 门，能进一步省下 T 门。他们给出的常数优化整数乘法器使用 $4n+1$ 比特、无垃圾输出，并报告相对 Babu、Lin、Jayashree 三种已有设计的 T 数分别节省 47.55%、62.71%、26.30%。这三个百分比是该文自述的对比结果，口径依赖于对比基线本身，不能直接与别家的绝对 T 数并置。

常量的效果：受控加法器退化为 Toffoli 阵列（无 T 门）

这段图要说明的是：“乘常量”和”乘变量”在量子线路层面是两个难度完全不同的问题，因为常量意味着控制条件可以编译期求值。Shor 的模幂里大量出现的就是乘常量，special-pattern-multipliers 对此有专门讨论。

三、平方：把两个操作数接起来

平方是乘法的特例 $b=a$，线路层面的做法就是把两次读的寄存器接成同一组线。Noto 在其 $\pi$ 估计线路里系统比较了两种平方器：由 $O(n)$ 门量子加法器实现的平方器需要 $O(n^2)$ 门与至少一个辅助比特；由 QFT 实现的平方器需要 $O(n^3)$ 门但不需要辅助比特，最终用 QFT 型平方器把线路实现在 $4n+1$ 比特、$2^{2n}$ 次采样的配置下。这组数字说明教科书路线的一个特点：它在门数与比特数之间总有一处要付账，而不像 Karatsuba 那样在两个方向同时改善。

论文依据

• Gidney（2019） —— 其 Karatsuba 论文附带 Q#/Python 参考实现，其中同时提供 SchoolbookMultiplication 与 SchoolbookSquaring，是本族最易复现与逐位核对的公开工件。
• Munoz-Coreas 与 Thapliyal（2017） —— 明确给出”受控加法器的操作数为零时退化为 Toffoli 阵列”的观察，并提供 $4n+1$ 比特、无垃圾输出的常量优化整数乘法器及其 T 数对比（相对 Babu/Lin/Jayashree 分别省 47.55%/62.71%/26.30%）。
• Noto（2020） —— 比较加法器型平方器（$O(n^2)$ 门 + ancilla）与 QFT 型平方器（$O(n^3)$ 门、无 ancilla），并把平方器接入 $\pi$ 的量子振幅估计线路。
• Hansen、Joshi 与 Rarick（2023） —— 用 Azure Resource Estimator 在离子阱、超导与 Majorana 三类平台上对 Karatsuba、schoolbook、windowed 乘法做统一口径的资源对比，见multiplication-resource-comparison。

延伸阅读

• karatsuba-multiplier —— 把这 $n$ 次受控加法换成 3 次递归。
• special-pattern-multipliers —— 常量与结构化操作数的专门路线。
• 定点数算术 —— 定点乘法的舍入与混合小数位格式，都以本词条的受控加法列为底盘。
• 浮点数算术 —— 浮点乘法流水线的中段”尾数乘法”，就是本词条的线路加一层舍入。