Karatsuba 乘法器

Karatsuba 乘法的全部内容是一个恒等式：$ab=z_0+2z_1+4z_2$，其中 $z_1$ 不需要单独做 $a_0{b}_1+a_1{b}_0$，而是用一次半位宽乘法 $(a_0+a_1)(b_0+b_1)$ 再减回来。于是 4 次半位宽乘法变成 3 次，递归后门数从 $O(n^2)$ 降到 $O(n^{\lg 3}\approx n^{1.585})$。真正困难的不在代数而在可逆性：三个子结果怎么存放、交叉项的减法什么时候做、ancilla 什么时候能回零。本词条把这两层分开讲。

一、代数层：为什么 4 次变 3 次

把操作数按位宽对半劈开：

$$a=a_1{2}^m+a_0,b=b_1{2}^m+b_0,m=n/2$$

展开得

$$ab=a_0{b}_0+2^m(a_0{b}_1+a_1{b}_0)+2^{2m}{a}_1{b}_1$$

朴素做法需要四个半位宽乘法：$z_0=a_0{b}_0$、$w=a_0{b}_1$、$v=a_1{b}_0$、$z_2=a_1{b}_1$。Karatsuba 的替换是

$$z_1=(a_0+a_1)(b_0+b_1)-z_0-z_2$$

因为 $(a_0+a_1)(b_0+b_1)=a_0{b}_0+a_0{b}_1+a_1{b}_0+a_1{b}_1$，所以 $z_1$ 恰好等于交叉项之和。递归方程随之是

$$T(n)=3T(n/2)+O(n)$$

的 $O(n^{\lg 3})$。

一个容易忽略的细节：$z_1$ 的位宽是 $m+1$ 而不是 $m$，因为 $a_0+a_1$ 可能溢出。多出来的这一位让三次递归变多了一个比特位宽，这正是 Parent、Roetteler 与 Mosca 提到”操作数宽度不到原来两倍”这类折衷的来源之一。另一个细节是 $2z_1$（即左移一位）在线路层面是纯置换，理论上门开销为零——同样属于结构性推论，本卷未在文献中核实到明确陈述。

Karatsuba 顶层：4 次半位宽乘法 → 3 次，三个子区间

三个 box 分别标出输出寄存器的三个子区间：z₀ 落在最低半段、2z₁ 落在中段、4z₂ 落在最高半段。图上画的是骨架——三个递归调用的内部结构完全相同，因此不在这里展开；递归的终止条件（半宽为 1 时退化成一次 AND）也省略。

二、可逆层：交叉项的减法是免费的还是收费的

上面那次”再减回来”在代数上是零成本的，在线路里却不是自动的：$z_1=(a_0+a_1)(b_0+b_1)-z_0-z_2$ 需要两次受控减法作用在已经算出的 $z_1$ 上。这引出三种实际做法：

1. 先存后减：把三个子结果分别放进三个暂存寄存器，算完再统一组装。这条路直观但代价高——暂存区占位，而且 $z_0$、$z_2$ 要保持到最后一刻才可释放。
2. 就地累加：每个递归调用直接把结果累加进输出寄存器的对应子区间，交叉项的减法在累加之后立刻做。Gidney 的 $O(n)$ 空间方案走的就是这条路，他的表述是让递归调用”能够把输出直接加进输出寄存器的子区间”，从而避免存储与反计算中间结果。
3. 部分分块：Parent、Roetteler 与 Mosca 用完全三叉树的 pebble game 在两者之间取平衡，把空间从 $O(n^{1.585})$ 压到 $O(n^{1.427})$，同时门复杂度仍是 $O(n^{\lg 3})$。

就地累加：递归结果直接写进输出子区间，交叉项就地反算

图里最关键的信息是 barrier 前后：三次递归共用同一个工作寄存器，中途不保留任何跨调用的中间结果。这就是”辅助比特账”从 $O(n^{1.427})$ 变成 $O(n)$ 的机制——省下的不是门，是 ancilla 的存活期。

三、渐近之外：Karatsuba 在真实位宽下不总是赢

$O(n^{1.585})$ 与 $O(n^2)$ 只在 $n$ 大到掩盖常数时才划算。真实容错实现里，每个受控加法器带自己的进位辅助位，Karatsuba 的额外加法（求 $a_0+a_1$、减 $z_0+z_2$、移位）都是整宽操作，常数不小。Gidney 自己论文的结论是空间改善具有更广的适用性（他把它类比为经典尾调用优化），而不是门数上出现数量级变化。

Zhan 在其指数编码乘法器的对比中直接声称其深度与门复杂度优于 Karatsuba 乘法器与 QFT 型乘法器；AlphaTensor-Quantum 则在自动优化有限域乘法时自行发现了类 Karatsuba 的高效算法。后者特别值得注意：它说明 Karatsuba 的核心恒等式在优化器眼里是”值得重新发现的解”，而不是过时写法。

论文依据

• Gidney（2019） —— 把 Karatsuba 乘法的空间复杂度从 $O(n^{1.427})$ 降到 $O(n)$，做法是让递归调用把输出直接加进输出寄存器的子区间，从而避免存储与反计算中间结果；保持 $O(n^{\lg 3})$ 门复杂度。
• Parent、Roetteler 与 Mosca（2017） —— 给出基于完全三叉树 pebble game 的可逆分析，把空间从 $O(n^{1.585})$ 降到 $O(n^{1.427})$，并指出这一折衷伴随操作数宽度不到原来两倍的条件。
• Dutta、Bhattacharjee 与 Chattopadhyay（2018） —— 用可逆 pebble game 反计算中间结果的方法构造 Toom-Cook 乘法器，给出 Toffoli 数与比特数的界，渐近上优于 schoolbook 与 Karatsuba。
• Zhan（2023） —— 在其指数编码乘法器的对比中把量子 Karatsuba 乘法器列为门复杂度与深度上的对比对象之一。
• Ruiz 等（2024） —— AlphaTensor-Quantum 在有限域乘法的 T 数优化中自动发现了类 Karatsuba 的高效算法。

延伸阅读

• schoolbook-multiplier —— Karatsuba 要优化的那个基准。
• in-place-multiplication —— 空间从 $O(n^{1.427})$ 到 $O(n)$ 的通用视角。
• multiplication-resource-comparison —— 渐近优势在真实位宽下的对照。