查看“︁托佛利閘”︁的源代码

{{noteTA
|T=zh-cn:托佛利门; zh-hk:托佛利閘; zh-tw:托佛利閘;
|1=zh-cn:门; zh-hk:閘; zh-tw:閘;
}}
'''托佛利閘'''（[[英文]]：Toffoli gate），又被称作'''控-控-非门'''（[[英文]]：'''controlled-controlled-not gate'''，[[縮寫]]：'''CCNOT'''）是[[计算机科学]]中，由托瑪索·托佛利（Tommaso Toffoli）提出的通用[[可逆計算|可逆]][[邏輯閘]]，其中任意可逆电路可由托佛利门构造得到。它具有三路输入和三路输出。如果前两位置一，它将倒置第三位，否则所有位保持不变。

== 背景 ==
托佛利门的提出是从研究可逆计算发展而来的。自1960年代人们开始研究可逆逻辑门，初衷是减少计算过程的能量耗散，因为原则上可逆逻辑门在计算过程中不产生热量。对于一般逻辑门，输入状态在运算后会丢失，这导致输出的信息少于输入信息。根据[[熵 (資訊理論)|熵原理]]，信息的损失以热的形式耗散到环境中。而可逆逻辑门只将信息状态从输入搬移到输出，不会损失信息。

== 托佛利门 ==
由[[鸽巢原理]]可知，任何可逆逻辑门，需要具有相同数量的输入端与输出端。对于一个输入端，存在有两个可能的可逆逻辑门。一为[[非门]]（NOT），另一种为 YES 门，即输入与输出相同。对于两个输入端，存在的可逆逻辑门为[[受控反閘]]，它把第一个输入对第二个输入进行异或操作，并保持第一个输入不变。

{|
! 真值表 !! 置换阵
|-
| 
{| class="wikitable"
! colspan="2" | 输入
! colspan="2" | 输出
|- align="center"
| &nbsp;0&nbsp; || &nbsp;0&nbsp; || &nbsp;0&nbsp; || &nbsp;0&nbsp;
|- align="center"
| 0 || 1 || 0 || 1
|- align="center"
| 1 || 0 || 1 || 1
|- align="center"
| 1 || 1 || 1 || 0
|}
|
<math>
\begin{bmatrix}
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 & 0 & 1 \\
 0 & 0 & 1 & 0 \\
\end{bmatrix}
</math>
|}

但是，只使用这两种逻辑门（非门和异或）并不能实现所有的布尔函数。如果要使用可逆逻辑门实现任意布尔函数，还需要额外的逻辑门。托瑪索·托佛利于1980年提出了 '''托佛利门'''。<ref>Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: {{cite conference
 |url         = http://pm1.bu.edu/~tt/publ/revcomp-rep.pdf
 |title       = Reversible computing
 |first       = Tommaso
 |last        = Toffoli
 |authorlink  = Tommaso Toffoli
 |year        = 1980
 |conference  = Automata, Languages and Programming, Seventh Colloquium
 |editor      = J. W. de Bakker and [[Jan van Leeuwen|J. van Leeuwen]]
 |publisher   = Springer Verlag
 |location    = Noordwijkerhout, Netherlands
 |pages       = 632-644
 |doi         = 10.1007/3-540-10003-2_104
 |isbn        = 3-540-10003-2
 |deadurl     = yes
 |archiveurl  = https://web.archive.org/web/20100415041123/http://pm1.bu.edu/~tt/publ/revcomp-rep.pdf
 |archivedate = 2010-04-15
}}</ref>

该逻辑门具有三个输入端和三个输出端。如果前两个比特置位，它将翻转第三个比特：

{|
! 真值表 !! 置换阵
|-
|
{| class="wikitable"
! colspan="3" | INPUT
! colspan="3" | OUTPUT
|- align="center"
| &nbsp;0&nbsp; || &nbsp;0&nbsp; || &nbsp;0&nbsp; || &nbsp;0&nbsp; || &nbsp;0&nbsp; || &nbsp;0&nbsp;
|- align="center"
| 0 || 0 || 1 || 0 || 0 || 1
|- align="center"
| 0 || 1 || 0 || 0 || 1 || 0
|- align="center"
| 0 || 1 || 1 || 0 || 1 || 1
|- align="center"
| 1 || 0 || 0 || 1 || 0 || 0
|- align="center"
| 1 || 0 || 1 || 1 || 0 || 1
|- align="center"
| 1 || 1 || 0 || 1 || 1 || 1
|- align="center"
| 1 || 1 || 1 || 1 || 1 || 0
|}
|
<math>
\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}
</math>
|}

即，三路输入<math>a</math>、 <math>b</math>、<math>c</math>映射到输出端的结果为<math>a</math>、 <math>b</math>和<math>c\oplus (a\cdot b)</math>。Toffoli 门具有通用性，这意味着，通过托佛利Toffoli 门可以以可逆计算的方式实现任意布尔函数。

== 相关逻辑门 ==
[[File:Toffoli BilliardBall-en.svg|thumb|250px|Fredkin & Toffoli 关于托佛利门的撞球模型]]
* [[Fredkin 门]] 是一种可逆三位逻辑门，输入端第一位为控制位，如果为1，输出将交换后两位。

* ''n''位托佛利门是托佛利门的扩展。 它有 ''n'' 位输入 ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub> 和 ''n'' 位输出。前 ''n''&minus;1 位输出等于 ''x''<sub>1</sub>,  ..., ''x''<sub>''n''&minus;1</sub>。 最后一个输出位为 (''x''<sub>1</sub> AND ... AND ''x''<sub>''n''&minus;1</sub>) XOR ''x''<sub>''n''</sub>.
* 可以使用五个两比特量子门构建托佛利门<ref>{{cite journal
| last1        = Barenco
| first1       = Adriano
| last2        = Bennett
| first2       = Charles H.
| last3        = Richard
| first3       = Cleve
| last4        = DiVincenzo
| first4       = David P.
| last5        = Margolus
| first5       = Norman
| last6        = Shor
| first6       = Peter
| authorlink6  = Peter Shor
| last7        = Sleator
| first7       = Tycho
| last8        = Smolin
| first8       = John A.
| last9        = Weinfurter
| first9       = Harald
| title        = Elementary gates for quantum computation
| journal      = Phys. Rev. A
| volume       = 52
| issue        = 5
| pages        = 3457–3467
| publisher    = American Physical Society
| doi          = 10.1103/PhysRevA.52.3457
| arxiv          = quant-ph/9503016
| pmid=9912645|bibcode = 1995PhRvA..52.3457B |date=Nov 1995}}</ref>

* 托佛利门可以通过撞球模型得到解释，如图所示。<ref>{{cite journal
 |last1       = Fredkin
 |first1      = Edward
 |authorlink1 = Edward Fredkin
 |last2       = Toffoli
 |first2      = Tommaso
 |authorlink2 = Tommaso Toffoli
 |title       = Conservative logic
 |journal     = International Journal of Theoretical Physics
 |volume      = 21
 |issue       = 3
 |pages       = 219–253
 |publisher   = Springer Netherlands
 |issn        = 0020-7748
 |doi         = 10.1007/BF01857727
 |url         = http://www.digitalphilosophy.org/LinkClick.aspx?fileticket=5wPlkttI56o%3d&tabid=61&mid=494&forcedownload=true
 |bibcode     = 1982IJTP...21..219F
 |date        = April 1982
 |deadurl     = yes
 |archiveurl  = https://web.archive.org/web/20120311135119/http://www.digitalphilosophy.org/LinkClick.aspx?fileticket=5wPlkttI56o=&tabid=61&mid=494&forcedownload=true
 |archivedate = 2012-03-11
}}</ref>

== 參見 ==
* [[可逆計算]]
* [[量子電腦]]
* [[量子閘]]

== 参考 ==
{{reflist}}

[[Category:逻辑门]]
[[Category:量子閘]]