就地乘法

同一个乘法算法，写成 out-of-place 还是半就地（in-place），差别不在门而在辅助比特的峰值占用与存活期。Out-of-place 写法把子结果放进一块专用暂存区，算完主结果再把它们读出来组装；就地写法让每个递归调用直接把自己的输出累加进输出寄存器的对应子区间，于是没有中间结果需要保存，也就不需要反计算它们。Gidney 正是用后一手法把 Karatsuba 的空间从 $O(n^{1.427})$ 降到 $O(n)$。本词条说明这套记账，以及它为什么独立于门数成为一条优化轴。

一、两种写法的账

设乘法器输出为 $z$（宽 $2n$）。三种常见组织方式：

• Out-of-place：$a$、$b$ 保持不变，全部结果写进新的 $z$，暂存区用于递归间的中间量。
• 半就地（in-place）：借 $a$ 或 $b$ 之一作为输出寄存器，结果直接覆盖上去。Karatsuba 天然适合这种写法，因为三个子区间的目标位置在输出里是预先确定且互不重叠的。
• 尾调用式：Gidney 的措辞——让递归调用能够把输出直接加进输出寄存器的子区间，类比经典的尾调用优化。

同一子结果的两种处置：暂存后组装 vs 直接累加进输出子区间

图里 barrier 分隔的两种组织方式，同一个子结果 $z_0$：上面要占一块 tmp 并在组装时清空（还要一次复制），下面直接进输出子区间。这就是 $O(n^{1.427})\to O(n)$ 那一步的全部内容——没有新门型，只有子结果的处置方式变了。

二、为什么”能直接累加”不是理所当然的

三个子区间的目标位置在输出里预先可定，这依赖于 Karatsuba 的结构：$z_0$ 落在最低半段、$2z_1$ 落在中段、$4z_2$ 落在最高半段，互不重叠。但要注意两点：

1. $z_1$ 有额外一位宽度。 因为 $(a_0+a_1)(b_0+b_1)$ 可能溢出，$z_1$ 的宽度是 $m+1$，所以”中段”并不严格等于中间那 $m$ 位。
2. 交叉项的减法有时机约束。 $z_1$ 必须先减去 $z_0$ 与 $z_2$ 才是真正的交叉项。如果 $z_0$、$z_2$ 已经被就地累加进了输出，交叉项的减法就得对着输出做（即”反计算已加的部分”），而不是对一个干净的暂存副本做。前者省了比特，后者多了一次跨区间的受控减法。

因此”in-place”并不是免费升级，它要求算法结构允许子区间的写入顺序与代数依赖一致。Karatsuba 恰好允许；教科书乘法在结构上无所谓（它本来就是直接累加）；Toom-Cook 因为插值步骤要多处组合，实现时的取舍更多——Dutta、Bhattacharjee 与 Chattopadhyay 用可逆 pebble game 反计算中间结果，给出 Toffoli 数与比特数的界，正是处理这类依赖关系的通用工具。

三、辅助比特账是一条独立的优化轴

在容错模型下，辅助比特与 T 门是两种不能互相换算的资源（见gate-cost-models）。就地优化只动辅助比特这一侧，而这一侧的收益常常比降门数更实在：Gidney 报告的成果是”空间从 $O(n^{1.427})$ 降到 $O(n)$，保持 $O(n^{\lg 3})$ 门复杂度”——门数一点没变。Parent、Roetteler 与 Mosca 的 $O(n^{1.585})\to O(n^{1.427})$ 也是同一轴上的部分进展，代价是操作数宽度不到原来两倍。

另一条同轴的进展是线路重写降 ancilla：Joshi 等用 ZX 微积分的重写规则优化容错乘法器，报告辅助比特与 T 门数量都有显著下降。这条路线与”就地”是互补的——一个在算法组织层面，一个在图重写层面，两者都指向同一个目标：让中间态的存在时间尽可能短。

辅助比特的三段生命周期：暂存期越长，越贵

这张图画的是”记账对象”：门数统计的是 barrier 之间的内容，而比特账统计的是从写入到清零的跨度。就地优化的作用就是压缩这个跨度。

论文依据

• Gidney（2019） —— 提出让递归调用把输出直接加进输出寄存器子区间，从而避免存储与反计算中间结果，把 Karatsuba 空间复杂度从 $O(n^{1.427})$ 降到 $O(n)$ 并保持 $O(n^{\lg 3})$ 门复杂度；作者把它类比为经典的尾调用优化并认为可推广到其他递归量子算法。
• Parent、Roetteler 与 Mosca（2017） —— 提供同一优化轴上的较早成果（$O(n^{1.585})\to O(n^{1.427})$）及其条件：完全三叉树 pebble game，操作数宽度不到原来两倍。
• Dutta、Bhattacharjee 与 Chattopadhyay（2018） —— 用可逆 pebble game 反计算中间结果，处理 Toom-Cook 插值步骤带来的多处中间值依赖，给出 Toffoli 数与比特数的界。
• Joshi 等（2023） —— 用 ZX 微积分重写规则优化容错乘法器，报告辅助比特与 T 门数量均有显著下降；这是在图重写层面上的同一条辅助比特优化轴。

一处文献空白

本卷未能核实到以 “semi-in-place multiplier” 为题的独立奠基文献。上面的做法都是通过具体算法论文（MOD001、MOD002、MOD003）间接支撑的。若需要为”半就地乘法器”这个术语本身给出出处，请自行查证，不要引用本站。

延伸阅读

• karatsuba-multiplier —— 就地写法最自然适用的算法。
• multiplication-resource-comparison —— 辅助比特与 T 门两种口径为何必须分开报。