量子算法里每一道”把经典函数作用到叠加态上”的算子——Shor 的模幂、Grover 的 oracle、QRAM 的查询、哈密顿模拟里的查表——在线路层都是一段经典可逆逻辑。这段逻辑不是量子算术的新发明:它有自己的一条文献线,从 Bennett 1973 的可逆图灵机,到 1989 年的时间-空间折中,到 2003–2012 年的可逆综合与语言工具,比量子算术文献老得多。这条线与量子算术线几乎互不引用:CDKM 不引 Bennett 1989,Bennett 1989 不引任何加法器;两边的成本口径(空间×时间折中因子 vs T 数/深度/辅助位)也没有对齐过。本卷是本站第一次把两条线放进同一张地图。
本卷的分工:基础词条立定义(双射门、通用门集、嵌入与垃圾),Bennett 词条讲折中(检查点、pebbling、隐藏账),综合词条讲生成(三条综合路线、ALU 复用、语言与工具、断代)。
| 词条 | 读完能回答 |
|---|---|
| 可逆计算基础 | 为什么量子线路必须可逆;Toffoli 为什么通用;垃圾从哪来、两种处置的代价;哪些门集”不够用”是定理。 |
| Bennett 技巧与鹅卵石游戏 | 垃圾回零的时间-空间折中怎么连续调节;pebbling 博弈怎么表述;在容错成本模型下哪三笔账被漏记。 |
| 可逆逻辑综合与工具链 | 真值表怎么自动变成 Toffoli 网络;可逆 ALU 证明了什么;RevKit 断代之后工具与文献怎么对不上。 |
本卷的 Open Problems 汇总
- 鹅卵石折中在容错成本(T 数、魔法态吞吐、二维连接)下的重新最优化——现有 pebbling 文献全部按”步数×比特”计账。
- 纠缠约束下的鹅卵石博弈(检查点必须可完整恢复)——经典理论没有这一章。
- 最小 T 数可逆综合——目标函数从门数换成 T 数后问题没有重新解过。
- 大规模真实代码的端到端可逆化——真实规模(SHA-2、稀疏线性代数)没有已核验文献。
- 守恒量分类与 T 数成本的对接、脏辅助位变体的资源理论——两个”共识先行、理论缺席”的位置。
阅读顺序建议
- 从量子算术过来的读者:可逆计算基础 直接读——你已经在用它的全部概念(每条加法器都是可逆网络)。
- 要估资源的读者:Bennett 技巧与鹅卵石游戏 的”三笔隐藏账”是给成本账本补漏的。
- 要写编译器的读者:可逆逻辑综合与工具链 的 Open Problems 就是现状清单。