可逆計算

可逆計算(英語:Reversible Computing),是一種計算模型,它的計算過程是可逆的。在這種計算模型中,使用的能量很低,的增加會最小化,換句話說,它幾乎不會產生額外的熱。

在可逆計算模型中,轉換函數的前一個狀態,與下一個狀態之間的關係,是一對一的反函數。因此,它的邏輯閘,除了產生出我們想要的答案之外,還需要包含許多額外的位元,用以記憶運算的歷史。最早提出可逆計算的先驅,是IBM的工程師羅夫·蘭道爾(Rolf Landauer)。

可逆电路

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

參見