Rolf Landauer的工作表明:事实与Von Neumann,Gabor和Brillouin等优秀学者的直觉并不相符:只有将信息摧毁的运算会伴随着耗散,以Landauer命名的原理量化了信息擦除和熵增之间的联系,换言之:只有逻辑不可逆的操作必须以热力学意义上的不可逆过程执行。Landauer指出:可用添加保存计算历史的流程等方式杜绝消灭信息的不可逆操作,将计算改为可逆,从而可能实现最大限度的计算节能(至多节约到0)。Landauer本人猜测:可逆计算将会受到比普通的计算更加严重的限制:一者是可能无法执行所有可能的计算(如果不存在图灵完备的可逆模型),一者是保存计算历史会导致垃圾信息在内存中积累,从而给整体计算添加一个随着问题规模指数飙升的空间复杂度的负担。这两点(尤其是后者)会导致可逆计算无法进行复杂的工作。
Charles Bennett进一步发展了可逆计算的理论,证明了Landauer的限制完全是多余的——不耗能的可逆计算能力几乎一点都不弱于传统的计算!通过名为Lecarf-Bennett反演的技巧,一台可逆通用机可以完全模拟任意的图灵机,并且每一步都能自行将计算历史可逆地消除,至多以计算时间4倍为代价。当然,只将经典计算可逆化是不足以保证计算不耗能的,逻辑可逆仅仅是一个必要条件。Edward Fredkin 和Tommaso Toffoli的撞球计算机可以看做是一个比较直观的可逆计算理想模型,它演示了从底层直接进行无耗散的经典计算是可以符合物理直觉的。
图1 Lecarf-Bennett反演通过进行正逆两重计算的途径,巧妙摆脱了计算历史积累的负担
与经典逻辑门不同,所有的量子逻辑门都是天然可逆的(它们本质上都是幺正变换)。因此,通用量子计算本身就是对可逆计算的一个支持。在某种意义上说:找到一组恰好能做通用计算的简单量子门比对应的经典情形要容易得多,但是用它们逼近一个任意的幺正变换的复杂度很可能是惊人的。一方面:至今为止我们还没有足够有效的量子计算设备。另一方面:我不认为量子计算对解释人类意识活动有额外帮助,目前的研究证据表明人脑处理信息的方式是经典的。因此关于量子计算将不在这里进行更多讨论。
图2 麻省理工大学的Josie Ammer, Nicole Love, Scott Rixner和Carlin Vieri等人设计的第一代可逆芯片,它们确实显示出低功耗的特征。