從此便有了可逆計算的概念。什麼是可逆計算？經典計算由電子電路實現，那麼，什麼樣的電路是可逆電路呢？通俗地說，一個電路是可逆的，就是說如果將輸入與輸出交換一下，從輸出的值可以得到輸入的值。舉個最簡單的例子，圖2的左上圖·，是一個不包括進位的十進制加法器S=A+B，如果將輸入輸出交換一下，成了右上圖。然而，看看圖2的右上圖就發現，從輸出不能唯一地還原輸入。例如你用S=7+3得到10，但用10作為輸入，你不能唯一地得到7和3！因此，我們就說圖2左上圖的電路是不可逆的。不過，使用一個額外的輸出端P=A，就將圖2的左上圖變成了兩個輸入兩個輸出的左下圖。雖然增加的這個輸出端沒有作任何運算，只是直接輸出A而已，但卻把原來的不可逆電路變成了可逆電路。因為當我們將輸入輸出交換一下，成為右下圖時，可以還原原來的輸入值7和3。
▲ 圖2 不可逆與可逆計算的簡單例子
圖2例子的重點在於，輸入端和輸出端數目不相等的電路，一定是不可逆的電路。但可以增加額外的端口，將不可逆線路變成可逆的。要增加幾個端口，得看具體情況而定。圖2例子用的是10進制，對2進制邏輯，原則上是一樣的。例如圖1最下面的圖中，左邊的異或門是2比特輸入，1比特輸出的經典門，輸入輸出端數目不相等，當然不能交換，所以不可逆。但這個經典的不可逆異或門電路，可以用增加一個輸出端P的辦法，改造成可逆異或門，如圖1下圖中右邊的電路（兩個輸入端，兩個輸出端）所示。現代計算機是許多“bit”構成的十分複雜的布爾邏輯電路，一般都不可逆，所以要耗散很多能量。但是，如果將電路加上許多額外的“比特位”，就可以將經典計算機重新設計成可逆的經典計算機，讓能量耗散達到最小。微觀來說，可逆的意思就是要“初態”與“末態”一一對應，才能保證在計算過程中不引入任何新的不確定性，可以讓系統“原路返回”。這要求執行計算的物理系統滿足時間反演對稱性，還要求系統與環境完全隔絕。但是在實際計算中，不存在這樣的物理系統，因而便有了“計算導致熵增加”的蘭道爾原理。用一個比喻來說，可逆計算就如同可逆的卡諾熱機一樣只有理論上的意義。在實際中很難實現這樣理想化的模型。因此，蘭道爾原理的直接後果是導致所謂摩爾定律的終結。因為現有的不可逆計算機物理上必須消耗能量，並以熱量的形式散發。當計算的速度越快或集成元件數目越多，產生的熱量就越多。蘭道爾等提出的可逆計算概念突破了這種極限。1973年，貝奈特證明了那種不要擦除信息的邏輯上可逆的計算原則上是可行的，經典計算可以靠改進電路來實現可逆，就如上面兩個例子中的電路那樣，而以下我們會提到：量子計算本質上就是可逆的。
▲ 圖3 不可逆邏輯門和可逆邏輯門
因此，人們從兩個不同的側重點提出了量子計算的想法：費曼從模擬的角度，而蘭道爾等從計算的可逆性（圖3），即受熱力學限制的物理極限之考量。
研究量子信息和量子計算，還有第三個目的，不僅僅出於實用的需要，也涉及到從物理理論的層面上深入理解信息、物質、能量的關係等基礎問題，並有助於更好地詮釋量子理論。
對早期的科學家來說，信息的概念十分縹緲抽象而空靈，直到香農的信息論問世，才將“信息“解釋為不確定性的度量。蘭道爾原理更為真實地將信息與物質及能量的概念聯繫起來，正如蘭道爾經常告誡他的IBM同事：”信息不可避免地是物理的，信息植根於現實世界，必須通過應用嚴肅的物理定律來理解。”
“蘭道爾是一位老IBM類型，做事正直、狹窄，對那些足以成為時尚但過於宏大和簡單無用的想法有着敏銳的洞察力。”貝內特博士如此回憶他的朋友和同事。
蘭道爾1961年發現蘭道爾原理後，有幾位物理學家研究過可逆計算。例如，在德國計算機專家楚澤（Konrad Zuse）的書《計算空間》（1969年）中，提到了可逆計算的重要性。認為在這種可逆計算模型中，使用的能量很低，熵的增加會最小化。
1972年，蘭道爾和貝內特，從理論上證明了計算機以可逆方式執行計算可以避免熵的增加。後來發現，另一位MIT的教授埃德·弗雷德金（Ed Fredkin，1934-2023）獨立地得出了同樣的結論。弗雷德金更進一步，他發明了一個Fredkin門，後來托弗利又發明了Toffoli門，這兩種門代表了可逆電路研究中根本性的突破，有了它們，才使得可逆的經典計算機得以具體實現。這兩種門是通用的，使用它們可以實現所有的可逆布爾函數[3]。Fredkin門是⼀個3×3可逆門，輸出為P=A、Q=AB+AC和R=AB+AC，保留了一個輸入端（P=A）；Toffoli門是具有三個輸入端的可控非門，保留了兩個輸入端，見圖4。
▲ 圖4 弗雷德金門和托弗利門
我們之前介紹過的弗雷德金，是美國計算機科學家和商人，是數字物理學的早期先驅。托弗利（Toffoli，1943-）是一位意大利人，1969年移居美國，之後成為了美國計算機工程教授。托弗利1976年在意大利獲得了第一個博士學位，研究領域是宇宙射線探測器的電子器件。他在美國的密西根大學與Art Burks（圖5右）一起研究二維元胞自動機，數學家阿特·伯克斯Art Burks是“元胞自動機”這個名字的創造者。此外，托弗利對可逆計算感興趣，寫了一篇論文，展示了如何通過存儲普通計算機必須忘記的所有內容來構建可逆計算機。正當他1978年剛剛完成他的第二個博士學位之時，他的可逆計算文章被MIT的弗雷德金教授發現了。該論文令弗雷德金對托弗利注目，因為當年作可逆計算及元胞自動機的人不算多，真正設想具體實現的人更是寥寥無幾，托弗利是其中之一。於是，弗雷德金決定雇用托弗利來幫助自己研究可逆計算。後來，弗雷德金用他獲得的DARPA的一筆資助，支持Toffoli和弗雷德金在MIT的一位唯一的“物理學博士生”，Norm Margolus，建造了一個越來越大的“細胞自動機”。因此，弗雷德金將Toffoli帶到了麻省理工學院，1981年，他們兩人都出現在MIT的著名會議上（圖5）。他們在MIT建造了一台元胞自動機，還合作寫了一篇關於保守邏輯的論文，最終於1982年發表，其中包含弗雷德金門和托弗利門。托弗利門可以算是弗萊德金門的一個特例，兩種門可以加上其它基本邏輯門而互相轉換。Toffoli的⼯作挑戰了可逆計算中不允許反饋的觀念，並為可逆邏輯電路設計的研究開闢了新途徑。他的結果表明，通過仔細設計電路的組合部分，可以引⼊反饋並仍然保持可逆性。這導致了更先進的可逆邏輯電路的發展，這些電路能夠實現複雜的操作，同時仍然保持較低的量⼦成本。
▲ 圖5 MIT會上與可逆計算有關的幾位科學家
在MIT，托弗利作為一名研究科學家，從1978年開始，工作了近二十年。其間托弗利不僅研究可逆計算機，也將可逆的概念首次引用到元胞自動機中，提出了可逆元胞自動機的概念。但是，可逆計算機或細胞自動機，都不是當年麻省理工學院計算機研究的主要課題。最後，這個項目被關閉了，托弗利1995年轉到波士頓大學成為教授。近年來，經典計算系統的可逆邏輯重新受到關注，因為其降低功耗的能力，在低功耗CMOS設計、光學信息處理、DNA計算、量子計算和納米技術等方面有着廣泛的應用。特別是在新型的納米技術中，可逆邏輯可以顯着減少的能量耗散，確保計算過程中不會丟失任何信息，從而避免因散熱而浪費能量，這不僅提高計算的效率，也有利於環保。例如在可穿戴和便攜式設備中，應用可逆計算的思想，可以將能量耗散降低到最小。
本文到此為止，說的都是經典的可逆計算。那麼，量子電路中可逆性的概念又是什麼？為什麼它在量子計算中很重要？量子現象與經典現象完全不同，因而描述它們的數學理論也不一樣[4]。兩種理論的一個重要區別就是物理量的算符化。在經典物理中也使用算符，比如平移算符、旋轉算符等，但是算符對經典物理而言，是為了方便，對量子力學而言卻是不可或缺的。因為在經典物理學中，諸如粒子的坐標、動量、能量、角動量等力學量，理論上有明確的定義，實驗測量有確定的數值。而在量子力學中，即使研究的對象只有1個粒子，它的運動也需要用瀰漫整個時空的波函數來描述。因此，物理量的經典概念必須加以改造方能使用，算符化便是一種改造方式。也就是說，量子理論中的物理量被作用在波函數上的算符所替代，這樣更容易描述量子規律。在量子理論的統計詮釋下，每次實驗測到的物理量數值不是確定的，而只是以一定幾率出現的算符的本徵值中的1個。在量子物理中，物理量的狀態（量子態）用算符來表示，狀態與狀態之間的轉換（計算門）也是用算符來表示，它們是兩類不同的算符。量子力學中的可觀測量都是由厄米算符來表示，表示量子態之間的轉換的，叫做幺正算符，或酉算符。用通俗點的實數矩陣表示來說，就分別對應於自共軛矩陣和正交矩陣。計算的過程就是物理狀態變換的過程，這種變換用各種“量子門電路”來實現。因此，量子門便對應於酉變換。厄密算符的本徵值為實數，因而才能在量子力學中描述與經典物理量相對應的可觀測量。物理量間的變換為酉變換，它的幺正性（Unitarity）指的是於時刻t在全空間找到某個粒子的總概率等於1，即歸一化條件。因此，酉變換描述的是微觀過程的物質不滅原理。酉變換是可逆的，這個特性確保了量子態的演化始終是可逆的，所以說，量子計算天生可逆。而對經典可逆計算機的研究成果（邏輯構造）可以方便地用到量子計算中，只需要認真考慮量子信息相對於經典信息的不同之處即可，尤其是“量子比特”相對於“比特”之不同，這是我們下一篇文章的內容。
