前面两词条讲"为什么"与"折中"，本词条讲"怎么生成"：给定一个经典函数，产出 Toffoli/CNOT 网络。这门学问在 2003–2012 年间形成了一条独立文献线——变换式综合、置换分解、模板化简、专用语言与工具——然后与容错量子计算的主流成本口径（T 数、魔法态）脱节了。今天写量子算术的人重新发明可逆综合技巧，多数不知道那条线早就存在。本词条把三条综合路线摆出来，把断点指出来。
问题形式与三条路线
输入：经典函数（真值表、布尔网络、或程序片段）；输出：NOT/CNOT/Toffoli 网络，作用在 个数据位加若干辅助位上。三条已核验的路线：
| 路线 | 代表文献 | 做法 | 规模边界 |
|---|---|---|---|
| 变换式综合（transformation-based） | Miller–Maslov–Dueck 2003（QRC009） | 把恒等排列逐步变换到目标真值表，每步落一个 Toffoli/CNOT | 小 （）实用；无辅助位版本最坏指数 |
| 置换环分解 | Shende–Prasad–Markov–Hayes 2003（QRC010） | 真值表排列的环结构直接分解为门；给出紧的最坏界与辅助位折中 | 一般排列最坏 量级门数——综合是指数难的 |
| 逻辑网络合成（XAG/MIG → 可逆） | Soeken–Roetteler–Wiebe–De Micheli 2017（QRC016） | 先做经典逻辑综合（异或-与图、多数-反相图），再可逆化；目标函数含 T 深度 | 大 可扩展；质量取决于逻辑综合阶段 |
第三条路线值得单独强调：它明确把量子成本（T 深度）写进了经典逻辑综合的目标函数，是”可逆综合”与”容错口径”之间少数已核验的桥。同方向的后续 Häner–Soeken 2020 证明重排逻辑网络的乘法深度可以直接降 T 深度——把综合问题从”门数最小”转向”乘法深度最小”。
可逆 ALU：一门复用
综合文献的代表作之一不是单函数，而是把加、减、与、或、异或等一整套运算塞进同一条可逆数据通路的 ALU 设计（Thomsen–Glück–Axelsen 2010，标题即 “for quantum arithmetic”）。思路：运算选择位作为额外控制线，公共的进位/传播结构被各运算共享，避免”每个运算各配一套线路 + 各自的垃圾”。它的实用价值有限（算术卷的专用加法器几乎总是更省），概念价值很高：它证明”可逆数据通路”可以像经典处理器一样被复用——这条思路在今天的 QRAM 与 oracle 设计里反复重现，却很少被归功。
语言与工具：一条断代的线
可逆计算有过自己的语言与工具生态：
- 语言层：Yokoyama–Axelsen–Glück 的可逆语言运行语义（PEPM 2008）确立了”程序可逆 ⇔ 每条语句可逆”的组合原则与语义不变式；Axelsen–Glück 刻画了可逆程序的计算能力边界（FoSSaCS 2011）。这类语言把 “uncompute” 写进语义，让编译器保证垃圾回零——比在量子 HDL 里手工管辅助位先进一代。
- 工具层：RevKit（Soeken–Frehse–Wille–Drechsler 2012）把上述综合路线做成开源工具链，也是 Häner 等 2018 构造浮点线路用的两大验证工具之一。
- 验证与优化层：Häner–Hoefler–Troyer 的断言传播（1810.00375）在可逆经典逻辑上证明”某段计算不影响观测输出”并整段删除——把编译器优化做进量子语义层面。
断代发生在 2012 年之后：RevKit 停止演进，可逆语言研究离开主流，而量子工具链（Qiskit 等）的 classical function synthesis 重新实现了其中一小部分技巧、几乎不引用那条文献线。两边的清单对不上：工具有的文献没有，文献有的工具丢了。引用本卷文献时要知道这个断层——“工具不存在”不等于”方法不存在”。
Open Problems
- 最小 T 数可逆综合。 以 Toffoli/CNOT 数为目标的三条路线都成熟；以 T 数（或 T 深度）为主目标函数的系统综合只有 Häner–Soeken 2020 的乘法深度重排这一个方向性结果。目标函数换了，问题没有重新解过。
- 大规模真实代码的自动化可逆化。 密码学代码（真 SHA-2/AES）、稀疏线性代数这类”真实世界规模”的子程序，没有已核验的端到端可逆化流程文献；论文里的 oracle 都是小函数手写或 toy 综合。
- 置换综合下界与算法的 gap。 一般排列最坏门数与已知构造之间的缝隙（对数因子级）在 T 数口径下完全没有分析。
- 可逆语言与量子工具链的重新对接。 语义层保证垃圾回零的语言设计，与当代量子编译 IR（QASM/Q#）之间没有一座已核验的桥——断言方法是最接近的一篇。
论文依据
- Miller–Maslov–Dueck 2003 —— 变换式综合的原始文献。
- Shende–Prasad–Markov–Hayes 2003 —— 置换环分解综合与最坏界。
- Soeken–Roetteler–Wiebe–De Micheli 2017 —— XAG/MIG 逻辑网络合成进可逆线路，目标函数含 T 深度。
- Häner–Soeken 2020 —— 乘法深度重排降 T 深度。
- Thomsen–Glück–Axelsen 2010 —— 可逆 ALU：一门复用的数据通路设计。
- Yokoyama–Axelsen–Glück 2008、Axelsen–Glück 2011 —— 可逆语言的语义原则与计算能力刻画。
- Soeken–Frehse–Wille–Drechsler 2012 —— RevKit 工具链。
- Häner–Hoefler–Troyer 2018 —— 断言传播：在语义层删垃圾计算。
- Häner–Soeken–Roetteler–Svore 2018 —— RevKit 作为浮点线路验证工具的实际使用。
延伸阅读
- reversible-computation-basics —— 门集与嵌入的定义层
- bennett-trick-pebbling —— 综合产出的线路怎么被折中调度
- 线路图谱 —— Toffoli 分解与相对相位变体的图集
- 编译器工具链 —— 可逆综合在当代工具栈里的位置