跳至內容

可逆計算

維基百科,自由的百科全書

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

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

可逆電路

對於可逆電路的實現,人們一般以邏輯門為模型研究可逆計算,並計算能量消耗,確定極限。例如,非門是可逆的,因為它的操作可以取消。異或門不可逆,因為它的輸出無法明確一對一地映射回它的輸入。不過,可控非門(CNOT),通過保存一個輸入狀態,成為異或門的可逆版本。具有三個輸入端的可控非門稱作 Toffoli 門。它保留了兩個輸入 ,而把第三個輸入替換為 。當 時,其操作為與非門,而與非門是一種通用邏輯門。這樣, Toffoli 門可以實現所有的可逆布爾函數。

參見