托佛利閘英文:Toffoli gate),又被稱作控-控-非閘英文controlled-controlled-not gate縮寫CCNOT)是計算機科學中,由托瑪索·托佛利(Tommaso Toffoli)提出的通用可逆邏輯閘,其中任意可逆電路可由托佛利閘構造得到。它具有三路輸入和三路輸出。如果前兩位置一,它將倒置第三位,否則所有位保持不變。

背景

編輯

托佛利閘的提出是從研究可逆計算發展而來的。自1960年代人們開始研究可逆邏輯閘,初衷是減少計算過程的能量耗散,因為原則上可逆邏輯閘在計算過程中不產生熱量。對於一般邏輯閘,輸入狀態在運算後會丟失,這導致輸出的信息少於輸入信息。根據熵原理,信息的損失以熱的形式耗散到環境中。而可逆邏輯閘只將信息狀態從輸入搬移到輸出,不會損失信息。

托佛利閘

編輯

鴿巢原理可知,任何可逆邏輯閘,需要具有相同數量的輸入端與輸出端。對於一個輸入端,存在有兩個可能的可逆邏輯閘。一為非閘(NOT),另一種為 YES 閘,即輸入與輸出相同。對於兩個輸入端,存在的可逆邏輯閘為受控反閘,它把第一個輸入對第二個輸入進行異或操作,並保持第一個輸入不變。

真值表 置換陣
輸入 輸出
 0   0   0   0 
0 1 0 1
1 0 1 1
1 1 1 0

 

但是,只使用這兩種邏輯閘(非閘和異或)並不能實現所有的布爾函數。如果要使用可逆邏輯閘實現任意布爾函數,還需要額外的邏輯閘。托瑪索·托佛利於1980年提出了 托佛利閘[1]

該邏輯閘具有三個輸入端和三個輸出端。如果前兩個比特置位,它將翻轉第三個比特:

真值表 置換陣
INPUT OUTPUT
 0   0   0   0   0   0 
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0

 

即,三路輸入   映射到輸出端的結果為   。Toffoli 閘具有通用性,這意味着,通過托佛利Toffoli 閘可以以可逆計算的方式實現任意布爾函數。

相關邏輯閘

編輯
 
Fredkin & Toffoli 關於托佛利閘的桌球模型
  • Fredkin 閘 是一種可逆三位邏輯閘,輸入端第一位為控制位,如果為1,輸出將交換後兩位。
  • n位托佛利閘是托佛利閘的擴展。 它有 n 位輸入 x1, x2, ..., xnn 位輸出。前 n−1 位輸出等於 x1, ..., xn−1。 最後一個輸出位為 (x1 AND ... AND xn−1) XOR xn.
  • 可以使用五個兩比特量子閘構建托佛利閘[2]
  • 托佛利閘可以通過桌球模型得到解釋,如圖所示。[3]

參見

編輯

參考

編輯
  1. ^ Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: Toffoli, Tommaso. J. W. de Bakker and J. van Leeuwen , 編. Reversible computing (PDF). Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag: 632–644. 1980. ISBN 3-540-10003-2. doi:10.1007/3-540-10003-2_104. (原始內容 (PDF)存檔於2010-04-15).  |author=|last=只需其一 (幫助)
  2. ^ Barenco, Adriano; Bennett, Charles H.; Richard, Cleve; DiVincenzo, David P.; Margolus, Norman; Shor, Peter; Sleator, Tycho; Smolin, John A.; Weinfurter, Harald. Elementary gates for quantum computation. Phys. Rev. A (American Physical Society). Nov 1995, 52 (5): 3457–3467. Bibcode:1995PhRvA..52.3457B. PMID 9912645. arXiv:quant-ph/9503016 . doi:10.1103/PhysRevA.52.3457. 
  3. ^ Fredkin, Edward; Toffoli, Tommaso. Conservative logic. International Journal of Theoretical Physics (Springer Netherlands). April 1982, 21 (3): 219–253. Bibcode:1982IJTP...21..219F. ISSN 0020-7748. doi:10.1007/BF01857727. (原始內容存檔於2012-03-11).