Bennett 技巧与鹅卵石游戏

上一词条的 compute-copy-uncompute 有一个明显的浪费：反计算把整段计算原样重跑一遍，时间翻倍；不反算则垃圾堆积，空间爆炸。Bennett 1989 年给出的答案是折中可以连续调节：沿途存若干检查点，反算时从最近的检查点恢复——存 $S$ 个检查点，时间从 $2T$ 变到约 $(2+\frac{1}{S})T$ 量级。这个”鹅卵石”构造是量子算法工程里最常被引用却最少被正式计账的工具：Grover oracle、模幂、QRAM 查询里都有它，而它自己的成本模型在容错口径下还没有被重做过。

朴素两端的失败，与折中的形状

设经典子程序 $F$ 需要 $T$ 步、峰值工作空间 $W$。两端的做法：

• 全反算（uncompute）：时间 $2T$，垃圾空间 $W$ 常驻。空间最省，时间翻倍。
• 不反算：时间 $T$，垃圾空间 $W$ 之外还要为每次调用囤积输出——嵌套调用（$f(g(h(x)))$）时垃圾线性叠加，叠加态下不能读出区分，实际上不可用。

Bennett 1989 的构造：正向计算时每隔 $T/k$ 步存一个完整状态检查点（共 $k$ 个），然后从最后一个检查点出发完成计算并反算，逐级回退。时间变成 $T\cdot (1+2/k+2/k^2+\cdots )<3T$，峰值空间变成 $W$ 加上 $k$ 个检查点。折叠因子（trade-off factor）$\alpha$：时间 $\sim \alpha T$、空间 $\sim W\cdot k$，$\alpha =1+2/(k+1)$ 附近连续可调——这是可逆计算里少有的”鱼与熊掌各取一半”的定量结果。

把这道折中表述干净的语言是鹅卵石博弈（pebble game）：计算依赖图是一条长为 $T$ 的链（每步依赖上一步），鹅卵石放在”当前存得住的中间值”上，规则是放一颗要算一步、拿走一颗要反算一步。问题变成：给定 $S$ 颗鹅卵石，走完 $T$ 个节点再清空，最少走多少步？Bennett 的答案是上界 $O(T\log T/\log S)$ 量级的存在性结果；Levine–Sherman 改进了时间项；Li–Tromp–Vitányi 用同样的博弈语言给出了下界方向的结果（三篇的准确表述见文末依据）。这是纯组合数学的一章，与物理无关——量子性只在最后”鹅卵石必须存在量子比特上”这一步进入。

在量子算法里它叫什么

同一个构造在量子文献里的出场方式：

场景	Bennett 折中的角色
Grover oracle	oracle 内部的经典计算做完相位踢动后必须恢复——compute-copy-uncompute 是最小配置，检查点变体省深度的文献几乎没有
Shor 模幂	幂次链 $a^{2^i}$ 的中间结果留不留，是显式的检查点取舍；Gidney–Ekerå 的窗口化（QA008）就是把检查点策略做到极致的实例
QRAM 查询	查询路由的垃圾要么反算要么沿查询路径分发，是鹅卵石折中在二维连接图上的版本（QRAM 百科有专论）
嵌套振幅估计	内层 oracle 的垃圾预算直接乘进外层的迭代次数，折中因子进指数

一个必须写出来的事实是：量子算法论文引用”Bennett’s trick”时，多数引的是 Knill 1996 年的伪代码约定（reverse/uncompute 关键字的出处，文献页），而不是 Bennett 1989 的折中定理本身——真正把检查点折中定量用进资源估算的量子论文是少数。“引用了技巧的名字、没引用技巧的成本”是本卷观察到的系统性口径缺口。

折中不是免费的：三笔隐藏账

1. 检查点存取本身是算术。 存/恢复一个 $W$ 位状态要 $O(W)$ 个 CNOT（受控复制进检查点区），这条线性成本在鹅卵石博弈里是”免费的”，在量子账本上不是。
2. 叠加态下的检查点是纠缠源。 检查点寄存器在计算过程中与主寄存器纠缠，恢复时必须完整还原到基态才能复用——任何”部分恢复”都会以干涉退化的形式出现在算法末端。经典 pebbling 理论完全没有这一章。
3. 深度 vs T 数的错位。 鹅卵石构造压的是空间与门数；容错成本模型的硬通货是 T 数与魔法态吞吐，而检查点的存取全是 Clifford。折中在错误的账本上最优，就可能在正确的账本上次优。

Open Problems

1. 容错成本下的重新最优化。 以 T 数（或魔法态工厂吞吐）为目标函数的鹅卵石问题没有任何文献——现有 pebbling 文献全部以”计算步数 × 比特数”计账（Bennett 1989、Levine–Sherman 1990、Li–Tromp–Vitányi 1998）。第 3 笔隐藏账说明这不是纯形式问题。
2. 纠缠约束下的鹅卵石博弈。 把”检查点必须可完整恢复”作为约束加入博弈定义，最优策略是否还是 Bennett 式均匀检查点，没有结果。
3. 实际连接图上的折中。 Bennett 构造隐含全连接；二维最近邻上检查点区的物理布局成本没有系统分析。
4. Grover/模幂/QRAM 三个场景的检查点策略对比。 三处都在用同一构造的不同切法，没有一篇把它们放在同一口径下比较过。

论文依据

• Bennett 1989 —— 检查点折中的原始构造：时间 $\alpha T$ 与空间 $Wk$ 连续可调。
• Levine–Sherman 1990 —— 折中时间项的改进界。
• Li–Tromp–Vitányi 1998 —— 可逆模拟开销的鹅卵石表述与下界方向。
• Bennett 1973 —— “可逆模拟可能”的存在性起点（无折中、空间无界）。
• Knill 1996 —— reverse/uncompute 伪代码约定；量子文献里 “Bennett’s trick” 引用的实际落点。
• Gidney–Ekerå 2019 —— 检查点策略在模幂里的工程极致（窗口化 + 临时逻辑与）。

延伸阅读

• reversible-computation-basics —— compute-copy-uncompute 的最小形态
• reversible-logic-synthesis —— 被折中的那段计算本身怎么生成
• 窗口化模幂 —— 检查点取舍的量子算术实例
• QRAM 百科 —— 查询路由上的同款折中，站群独立成卷