托佛利閘

托佛利閘（英文：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	${\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\\end{bmatrix}}$

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

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

真值表	置換陣
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	${\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}}$

即，三路輸入$a$、 $b$、$c$映射到輸出端的結果為$a$、 $b$和$c\oplus (a\cdot b)$。Toffoli 閘具有通用性，這意味著，通過托佛利Toffoli 閘可以以可逆計算的方式實現任意布爾函數。

相關邏輯閘

Fredkin & Toffoli 關於托佛利閘的撞球模型

• Fredkin 閘 是一種可逆三位邏輯閘，輸入端第一位為控制位，如果為1，輸出將交換後兩位。

• n位托佛利閘是托佛利閘的擴展。 它有 n 位輸入 x₁, x₂, ..., x_n 和 n 位輸出。前 n−1 位輸出等於 x₁, ..., x_n−1。 最後一個輸出位為 (x₁ AND ... AND x_n−1) XOR x_n.
• 可以使用五個兩比特量子閘構建托佛利閘

• 托佛利閘可以通過撞球模型得到解釋，如圖所示。

參見

• 可逆計算
• 量子電腦
• 量子閘