可逆计算

可逆计算(英语:Reversible Computing),是一种计算模型,它的计算过程是可逆的。在这种计算模型中,使用的能量很低,的增加会最小化,换句话说,它几乎不会产生额外的热。

在可逆计算模型中,转换函数的前一个状态,与下一个状态之间的关系,是一对一的反函数。因此,它的逻辑门,除了产生出我们想要的答案之外,还需要包含许多额外的位元,用以记忆运算的历史。最早提出可逆计算的先驱,是IBM的工程师罗夫·兰道尔(Rolf Landauer)。

可逆电路

对于可逆电路的实现,人们一般以逻辑门为模型研究可逆计算,并计算能量消耗,确定极限。例如,非门是可逆的,因为它的操作可以取消。异或门不可逆,因为它的输出无法明确一对一地映射回它的输入。不过,可控非门(CNOT),通过保存一个输入状态,成为异或门的可逆版本。具有三个输入端的可控非门称作 Toffoli 门。它保留了两个输入   ,而把第三个输入替换为  。当   时,其操作为与非门,而与非门是一种通用逻辑门。这样, Toffoli 门可以实现所有的可逆布尔函数。

参见

  • 兰道尔原理