托佛利閘

维基百科,自由的百科全书
跳转至: 导航搜索

托佛利閘英文: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年提出了 托佛利门[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


\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}

即,三路输入abc映射到输出端的结果为abc\oplus (a\cdot b)。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. Reversible computing//J. W. de Bakker and J. van Leeuwen, Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. 1980: pp. 632-644. doi:10.1007/3-540-10003-2_104. ISBN 3-540-10003-2. 
  2. ^ Barenco, Adriano; Bennett, Charles H.; Richard, Cleve; DiVincenzo, David P.; Margolus, Norman; Shor, Peter; Sleator, Tycho; Smolin, John A. et al. Elementary gates for quantum computation. Phys. Rev. A (American Physical Society). 1995年Nov月, 52 (5): 3457–3467. arXiv:quant-ph/9503016. Bibcode:1995PhRvA..52.3457B. doi:10.1103/PhysRevA.52.3457. PMID 9912645. 
  3. ^ Fredkin, Edward; Toffoli, Tommaso. Conservative logic. International Journal of Theoretical Physics (Springer Netherlands). 1982年April月, 21 (3): 219–253. Bibcode:1982IJTP...21..219F. doi:10.1007/BF01857727. ISSN 0020-7748.