托佛利閘

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

但是，只使用这两种逻辑门（非门和异或）并不能实现所有的布尔函数。如果要使用可逆逻辑门实现任意布尔函数，还需要额外的逻辑门。托瑪索·托佛利于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	${\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}}}$

即，三路输入${\displaystyle a}$ 、 ${\displaystyle b}$ 、${\displaystyle c}$ 映射到输出端的结果为${\displaystyle a}$ 、 ${\displaystyle b}$ 和${\displaystyle 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.
• 可以使用五个两比特量子门构建托佛利门^[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 , 编. (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. . 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）.