可逆计算基础

量子线路的每一条门都必须是酉的，而经典程序里到处是擦除、覆写、分支合并这些不可逆操作。于是一段经典子程序要进量子线路，必须先被翻译成双射门网络——这道工序的理论基础在 1973 年就打好了（Bennett），与量子计算无关；量子计算只是把它从"热力学上的可选项"变成了"工程上的必选项"。本词条讲这门理论的最小内核：门是双射、Toffoli 通用、Bennett 嵌入产生垃圾、垃圾怎么处理、以及哪些门集"不够用"的定理边界。

可逆门：双射，仅此而已

一个 $n$ 比特经典门可逆，当且仅当它是 $\{0,1{\}}^n$ 上的双射。三个基本事实：

1. NOT 与 CNOT 可逆，AND、OR 不可逆——后两者把两个输入压成一个输出，信息被擦除。
2. Toffoli（CCNOT）+ CNOT + NOT 对可逆经典计算通用：$\{\cdot ,\oplus \}$ 足以表达任意布尔函数，而 Toffoli 补上了”可逆地实现 AND”的最后一块（目标位初始为 0 时，Toffoli 就是在目标位写入 AND，两个控制位原样保留）。Toffoli 门 1980 年的形式化与Fredkin 门 1982 年的”保守逻辑”（弹道模型、粒子数守恒）是这条线的两块奠基石——都早于量子计算的可行性的讨论，动机是热力学：擦除一个比特至少耗 $kT\ln 2$（Landauer 原理的可逆规避）。
3. 可逆 ≠ 无成本：双射只保证信息不丢，不保证门数少、深度浅或辅助位少。可逆计算的资源理论（时间-空间折中）是独立的一门学问，见bennett-trick-pebbling。

量子侧的全部不同，只是把”双射”升级为”酉”：同样的 Toffoli 变成了受控受控 X，同样的通用性论证照样成立。量子算术文献里的每一条加法器，都是这门理论里的一个可逆门网络——加法与减法卷就是它的最大应用。

Bennett 嵌入与垃圾问题

给定经典函数 $f:\{0,1{\}}^n\to \{0,1{\}}^m$（一般不可逆），可逆嵌入的标准形式：

$$|x⟩|0{⟩}^{\otimes g}|0{⟩}^{\otimes m}⟼|x⟩|\text{garbage}(x)⟩|f(x)⟩.$$

输入原样保留（可逆性要求），输出进干净寄存器，中间的垃圾寄存器记着”算出 $f(x)$ 的过程中产生的一切”。垃圾不是实现瑕疵——它是可逆性的账单：$f$ 丢掉的信息必须存在某个地方。

垃圾有两种处置方式，对应量子算法里两种真实成本：

• 反计算（uncompute）：把计算过程逆着跑一遍，垃圾回零，留下 $|x⟩|0⟩|f(x)⟩$。总成本 = 2 倍计算成本 + 一根逆转深度的线。“compute-copy-uncompute”三段式因此是量子算法的默认骨架——它的标准化来自 Knill 1996 年的量子伪代码约定（文献页），这也是现代论文里 “Bennett’s trick” 这个词的实际出处。
• 留着不反算：垃圾与输出纠缠，留到算法后期统一处理（如振幅放大的 oracle 里垃圾仅在相位踢动时被动用）。省一半门数，但要论证垃圾不破坏后续干涉——每次都要单独论证，没有免费午餐。

compute-copy-uncompute：垃圾回零，输入与输出留存

洁辅助位与脏辅助位的区分是这个结构的直接推论：洁辅助位（clean ancilla）初态 |0⟩、终态 |0⟩；脏辅助位（dirty ancilla）允许任意初终态。脏辅助位比洁的便宜得多——不需要制备与验证初态——而 Bennett 结构保证”计算-反计算”夹层里的辅助位可以全是脏的。这个观察在现代算术线路里被用到极致：Gidney–Ekerå 2019 的模幂线路（见 CDKM 词条的引用）把临时逻辑与（temporary logical AND）的擦除成本做到零 T 数，靠的就是”脏辅助位 + 延迟反计算”。

哪些门集”不够用”：守恒量分类

可逆门集不是都能互相模拟的。Aaronson–Grier–Schaeffer 给出了可逆比特运算按守恒量的完全分类（文献页）：每个可逆门集都守恒某种量（如海明重量、重量的奇偶性），守恒什么就决定了它不能构造什么——例如只含 CNOT 的线性门集守恒所有仿射结构，永远表达不了 AND。这给”为什么必须上 Toffoli”一个定理级别的回答，也给”在某些硬件原生门集上算术要不要重构”提供了判据：目标门集守恒的量，就是你在那个门集上丢掉的表达能力。

与量子算术各卷的接口

• VBE 加法器与 CDKM 是可逆加法的两条经典路线——本站加法卷整体上就是这门理论的下游。
• 可逆性推出来的下界（原地修改不可能、平方必须留符号位、$n+m$ 位输出）在算术复杂度卷已有系统陈述，本卷不重复。
• QFT 加法器一类的相位基线路表明：可逆经典逻辑不是唯一的可逆算术语言——傅里叶基里的加法没有进位链。本卷的”可逆编译”针对计算基线路；相位基路线的账本不同。

Open Problems

1. 守恒量分类与 T 数成本的对接。 分类回答”能不能”，不回答”多贵”：在一个给定守恒量的门集里，Toffoli 的最小 T 数分解是否存在系统结果，没有文献。
2. 脏辅助位 Bennett 变体的资源理论。 “夹层里全用脏辅助位”是工程共识（QA008 的实现是代表作），但”脏辅助位能省多少、什么时候反而不省”没有理论文献。
3. 计算基之外的”可逆编译”。 本卷的全部工具针对计算基布尔网络；对相位基（QFT 型）与 ZX 型线路，对应的”经典子程序编译”框架没有文献。

论文依据

• Bennett 1973 —— 一切可逆模拟的起点：可逆图灵机与 Bennett 嵌入。
• Toffoli 1980 —— 可逆计算的形式化与 Toffoli 门。
• Fredkin–Toffoli 1982 —— 保守逻辑：守恒约束下的可逆门集原点。
• Feynman 1985 —— 把可逆经典逻辑作为量子计算底层的历史节点。
• Knill 1996 —— compute/uncompute/reverse 伪代码约定的出处。
• Aaronson–Grier–Schaeffer 2015 —— 可逆门集按守恒量的完全分类。
• Gidney–Ekerå 2019 —— 脏辅助位与延迟反计算的工程极致。

延伸阅读

• bennett-trick-pebbling —— 时间-空间折中：垃圾回零的代价怎么省
• reversible-logic-synthesis —— 从真值表到 Toffoli 网络的自动综合
• VBE 加法器 —— 这门理论的第一个量子算术应用
• 门代价模型 —— Toffoli 在 Clifford+T 口径下的真实价格