可逆计算有一条绕不开的下界：不能破坏信息。它直接推出算术线路的一些渐近限制，其中最刺眼的一条是——对输入做经典算法意义上的原地修改是不可行的，因此”原地乘法”在渐近意义上根本做不到 。理解了这条，Karatsuba 的 为什么多年无人突破、为什么近期”多对数深度”的结果都带 辅助位，就都不再奇怪了。
可逆性的下界
定理（可逆计算的基本限制）：若一个计算过程可逆且不引入额外比特，则它对输入的每个比特都是双射的。
推论一：原地修改是不可能的。经典的”把 乘以常数 ”（，丢弃原来的 ）不是双射，因此必须保留原值或另找空间。
推论二：平方不是原地可逆的。 丢失了 的符号信息（ 与 同映），因此平方必须配一个”寄存器”来区分分支。这一点在平方器设计中反复出现（见平方与乘法）。
推论三： 比特乘 比特，输出至少需要 比特（进位/溢出需要额外空间）；若要求”输出与输入同址”，则渐近上不可行。
乘法：为什么 卡在那里
经典整数乘法有已知的渐进下界（，Harvey–van der Hoeven），但可逆/量子设置下的下界要弱得多，实践中形成如下格局：
| 方案 | 门数 | 辅助比特 | 备注 |
|---|---|---|---|
| 教科书（schoolbook） | 或就地复用 | 门数最劣，但深度浅、结构简单、辅助位少 | |
| Karatsuba | 可压到 | 递归三次半宽乘法 | |
| Toom-Cook | 更优 | 更高 | 5 段分裂 + 插值，渐近优于 Karatsuba |
| 近期多对数深度方案 | 门 | 辅助位 | 深度 ，用辅助位换深度 |
这张表最能说明问题的是最后一行：新的深度改进几乎都是用辅助位换来的，且门数反而退回 。原因就是可逆性下界——想并行就要有地方存放中间结果，而可逆又要求把那些地方还回去。
最后一行有了一个可引的代表构造：Sun–Borissov 的多对数深度乘法器（QM016）用指示函数控制的复制生成部分积、二叉加法树并行累加，把电路深度与 T 深度同时压到 ，代价是门数与辅助位都回到 ——折中方向与这张表的预测一致。
Karatsuba 的空间优化之所以珍贵，正是因为它同时改善了空间（，见Karatsuba 乘法器）而没有牺牲门数——它靠的是”不存储中间结果”，而不是”用更多比特”。
进位链的深度下界
对加法这类线性运算，情况相反：门数已经到 ，深度才是瓶颈。经典进位链深度 ；进位先行用平衡树把它压到 ，但需要 辅助比特——用辅助位换深度。
于是出现了本站反复出现的一个模式：
线性算术（加法）已经”位最优”，它的改进只能沿”用辅助位换深度”这一个方向走；非线性算术（乘法）已经”深度最优”，它的改进只能沿”用结构换门数”这一个方向走。
这也解释了为什么加法卷与乘法卷的论文长得不一样：加法论文比的是 T 数与深度，乘法论文比的是辅助位与门数。
近似与截断：绕开下界的第二条路
下界只对精确算术成立。因此还有一整类做法是接受近似来换资源：
- 分带（banding）：把 QFT 加法器里极小角度的受控相位量化为有限集合，误差与进位/借位率挂钩。
- 截断 QFT：丢掉小角度受控相位，直觉上它们”看起来是恒等”，但实际上只是改变了一个小相位——在特定读出下等价。
- 分段加法：把进位链切成若干段，段内并行、段间串行，深度降到 。
这类方法的代价必须说清楚：结果是近似的，误差界要随结果一起引用，否则没有意义。近年的趋势是把误差分析也做成算术线路的一部分——这本身就是一个有意思的元问题。
硬件连接带来的额外下界
上述都是全连接（all-to-all）设定下的结论。在受限连接架构上，还有额外的几何下界：受控门需要两个比特”物理上接近”，而算术线路的进位传播天然是局域的，因此架构会引入距离相关的深度代价。
对 维最近邻架构，精确加法器有 的深度下界。二维架构上可达到 深度 / 比特。这个 相比全连接的 大了一个数量级，直接影响近期硬件上的算术可行性——架构不再是实现细节，它进入了复杂度本身。
延伸阅读
- 门代价模型 —— 指标之间的张力
- 经典可逆计算与编译卷 —— 本词条可逆性下界的”工程面”：Bennett 嵌入、检查点折中与自动综合
- Karatsuba 乘法器 —— 空间优化的代表作
- 加法器资源对比 —— 同一权衡的加法版本
- 混合加法器 —— 近似路线的代表