托佛利閘 (英文 :Toffoli gate),又被稱作控-控-非門 (英文 :controlled-controlled-not gate ,縮寫 :CCNOT )是計算機科學 中,由托瑪索·托佛利(Tommaso Toffoli)提出的通用可逆 邏輯閘 ,其中任意可逆電路可由托佛利門構造得到。它具有三路輸入和三路輸出。如果前兩位置一,它將倒置第三位,否則所有位保持不變。
托佛利門的提出是從研究可逆計算發展而來的。自1960年代人們開始研究可逆邏輯門,初衷是減少計算過程的能量耗散,因為原則上可逆邏輯門在計算過程中不產生熱量。對於一般邏輯門,輸入狀態在運算後會丟失,這導致輸出的信息少於輸入信息。根據熵原理 ,信息的損失以熱的形式耗散到環境中。而可逆邏輯門只將信息狀態從輸入搬移到輸出,不會損失信息。
由鴿巢原理 可知,任何可逆邏輯門,需要具有相同數量的輸入端與輸出端。對於一個輸入端,存在有兩個可能的可逆邏輯門。一為非門 (NOT),另一種為 YES 門,即輸入與輸出相同。對於兩個輸入端,存在的可逆邏輯門為受控反閘 ,它把第一個輸入對第二個輸入進行異或操作,並保持第一個輸入不變。
More information ...
真值表
置換陣
輸入
輸出
0
0
0
0
0
1
0
1
1
0
1
1
1
1
1
0
[
1
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
]
{\displaystyle {\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\\end{bmatrix}}}
Close
但是,只使用這兩種邏輯門(非門和異或)並不能實現所有的布爾函數。如果要使用可逆邏輯門實現任意布爾函數,還需要額外的邏輯門。托瑪索·托佛利於1980年提出了 托佛利門 。[ 1]
該邏輯門具有三個輸入端和三個輸出端。如果前兩個比特置位,它將翻轉第三個比特:
More information ...
真值表
置換陣
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
[
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
]
{\displaystyle {\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\\\end{bmatrix}}}
Close
即,三路輸入
a
{\displaystyle a}
、
b
{\displaystyle b}
、
c
{\displaystyle c}
映射到輸出端的結果為
a
{\displaystyle a}
、
b
{\displaystyle b}
和
c
⊕
(
a
⋅
b
)
{\displaystyle c\oplus (a\cdot b)}
。Toffoli 門具有通用性,這意味着,通過托佛利Toffoli 門可以以可逆計算的方式實現任意布爾函數。
Fredkin & Toffoli 關於托佛利門的撞球模型
Fredkin 門 是一種可逆三位邏輯門,輸入端第一位為控制位,如果為1,輸出將交換後兩位。
n 位托佛利門是托佛利門的擴展。 它有 n 位輸入 x 1 , x 2 , ..., x n 和 n 位輸出。前 n −1 位輸出等於 x 1 , ..., x n −1 。 最後一個輸出位為 (x 1 AND ... AND x n −1 ) XOR x n .
可以使用五個兩比特量子門構建托佛利門[ 2]
托佛利門可以通過撞球模型得到解釋,如圖所示。[ 3]
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).
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 .