トフォリゲートのソースを表示

[[File:Toffoli gate.svg|150px|thumb|トフォリゲートの記号]]
'''トフォリゲート''' ({{lang-en-short|Toffoli gate}}) は、[[トマソ・トフォリ]]の提案した[[可逆計算|可逆]]論理ゲートである。トフォリゲートはfunctional complete（[[:en:Functional completeness]]）である。すなわち、任意の論理演算がトフォリゲートの組み合わせにより実現できる。別名の'''CCNOTゲート'''は、その動作を表す "controlled-controlled-not" (制御・[[制御NOTゲート|制御・NOTゲート]]) の略称である。

== 概要 ==
[[論理ゲート]] ''L'' が可逆であるとは、ゲートの表す関数が[[単射]]であること、すなわち任意の出力 ''y'' に対して ''L''(''x'') = ''y'' を満たす入力 ''x'' がただ一つ定まることをいう。出力に対応する入力を求める ''L''&prime;(''y'') = ''x'' を逆ゲートという。例えば、以下のように[[NOTゲート]]は可逆である。

{| class="wikitable"
! 入力 !! 出力
|- align=center
| 0
| 1
|- align=center
| 1
| 0
|}

一方、[[ANDゲート]]は可逆ではない。00、01、10に対する出力がすべて0となるため、出力0に対する入力が一つに定まらないためである。

可逆ゲートの研究は[[1960年代]]頃に始まった。その動機は、通常のゲートに比べて可逆ゲートは計算に使うエネルギーの消費が少ない(理想的にはゼロとなる)ことだった。通常論理ゲートでは入力する情報量に比べて出力する情報量が減り、入力された状態は失われる。これによって熱的[[エントロピー]]が下がり、生じた差分のエネルギーが周囲に熱として放出される。別の言い方をすると、回路の状態が変化する時電子がアースに流れ、エネルギーが僅かに回路外に持ち出されるということである。可逆ゲートは状態を交換して回るだけなので、情報は失われず、回路内のエネルギーは保存される。

可逆ゲートは、近年[[量子計算]]の分野で注目されている。[[量子計算]]では全ての遷移は可逆であり、[[重ね合わせの原理|重ね合わせ]]によってより多くの計算機の状態を持つことができる。したがって、可逆ゲートは[[量子ゲート]]の機能の一部を再現するものであり、可逆的に計算できるものは[[量子コンピュータ]]上でも計算できる。

== トフォリゲートの機能的完全性 ==

すべての[[可逆ゲート]]は同じ数の入力[[ビット]]と出力ビットをもつ。これは[[鳩の巣原理]]による。

1ビットに対しては、[[恒等写像]]と[[NOTゲート]]のふたつの可逆ゲートがある。この二種類はどのビット数に対しても同様のゲートが定義できる。

2ビットに対しては、上の二種類と交換などの自明なものを除くと、[[制御NOTゲート]]が唯一の演算である。このゲートは一つ目の入力を二つ目の入力にXORし、二つ目に出力する。一つ目の入力はそのまま出力される。動作を以下に示す。

{|
! [[真理値表]] !! [[置換行列]]表現
|-
| 
{| 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>
|}

また、論理式で表すと次のようになる(複数ビットの出力を[[タプル]]で表した)。

:<math>CNOT(x, y) = (x, x \oplus y)</math>

しかし、この演算のみでは表現できない可逆計算が存在する。つまり、CNOTは機能的完全性を持たない。{{仮リンク|機能的完全性|en|Functional completeness}}を持つ演算の一つが[[トマソ・トフォリ]]によって提案されたトフォリゲートである<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  = トマソ・トフォリ
 |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
 |isbn        = 3-540-10003-2
 |archiveurl  = https://web.archive.org/web/20100415041123/http://pm1.bu.edu/~tt/publ/revcomp-rep.pdf
 |archivedate = 2010-04-15
 |url-status  = dead
}}</ref>。

このゲートは3ビットの入出力をもつ。もし入力の最初の2ビットが1ならその時に限り、第3のビットを反転して出力する。最初の2ビットはそのまま出力する。以下の表に動作を示す。

{|
! [[真理値表]] !! [[置換行列]]表現
|-
|
{| class="wikitable"
! colspan="3" | 入力
! colspan="3" | 出力
|- 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>CCNOT(x, y, z) = (x, y, (x \cdot y) \oplus z)</math>

トフォリゲートは{{仮リンク|機能的完全性|en|Functional completeness}}をもつ。つまり、どのような[[論理関数]] ''f''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''m''</sub>) に対しても、トフォリゲートのみを使って ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''m''</sub> と幾つかの作業用のビットを入力に取り ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''m''</sub>, ''f''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''m''</sub>) と幾つかの作業に使われた不要なビットを出力する論理回路を構成できる。これは、トフォリゲートを使って論理関数を可逆的に計算することができることを意味する。

== 関連する論理ゲート ==
[[File:Toffoli BilliardBall-en.svg|thumb|250px|[[ビリヤードボール・コンピュータ]]]]
* [[フレドキンゲート]]はトフォリゲートと同様の3ビット可逆ゲートで、1ビット目が1のときに残りのビットを交換する。制御交換ゲートとも呼ばれる。

* 任意のビット数に対してトフォリゲートを一般化することができる。''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> を出力する。
* トフォリゲートは2[[量子ビット]]を扱う[[量子ゲート|ゲート]]を5つ組み合わせることによって[[量子コンピュータ]]上で実現できる<ref>{{cite journal
| last1        = Barenco
| first1       = Adriano
| last2        = Bennett
| first2       = Charles H.
| last3        = Cleve
| first3       = Richard
| 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
| year         = 1995
| month        = Nov
| title        = Elementary gates for quantum computation
| journal      = Physical Review 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 }}</ref>。

* トフォリゲートは仕切りと[[ビリヤードボール]]を使って実装できる（[[ビリヤードボール・コンピュータ]]を参照）。このモデルは[[エドワード・フレドキン|フレドキン]]と[[トマソ・トフォリ|トフォリ]]が提案した<ref>{{cite journal
| last1        = Fredkin
| first1       = Edward
| authorlink1  = Edward Fredkin
| last2        = Toffoli
| first2       = Tommaso
| authorlink2  = Tommaso Toffoli
| year         = 1982
| month        = April
| 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 }}</ref>。図はボールの衝突がどのように進むかを示したものである。

== 量子計算との関係 ==
量子トフォリゲートは2009年1月、[[オーストリア]]の[[インスブルック大学]]で実現された<ref>{{cite journal
|author1-link = Yaoyun Shi
|last1 = Shi
|first1 = Yaoyun
|journal = Quantum Information & Computation
|volume = 3
|issue = 1
|pages = 84–92
|date = Jan 2003
|arxiv = quant-ph/0205115
|title = Both Toffoli and Controlled-NOT need little help to do universal quantum computation}}</ref><ref>{{cite journal
| last1        = Monz
| first1       = T.
| last2        = Kim
| first2       = K.
| last3        = Hänsel
| first3       = W.
| last4        = Riebe
| first4       = M.
| last5        = Villar
| first5       = A. S.
| last6        = Schindler
| first6       = P.
| last7        = Chwalla
| first7       = M.
| last8        = Hennrich
| first8       = M.
| last9        = Blatt
| first9       = R.
| year         = 2009
| month        = Jan
| title        = Realization of the Quantum Toffoli Gate with Trapped Ions
| journal      = Physical Review Letters
| volume       = 102
| issue        = 4
| pages        = 040501
| publisher    = American Physical Society
| doi          = 10.1103/PhysRevLett.102.040501
| arxiv        = 0804.0082
| bibcode=2009PhRvL.102d0501M}}</ref>。

== 関連項目 ==
* [[フレドキンゲート]]
* [[可逆計算]]
* [[量子コンピュータ]]

== 脚注 ==
{{reflist|30em}}


==外部リンク==

* [http://demonstrations.wolfram.com/CNOTAndToffoliGatesInMultiQubitSetting/ CNOT and Toffoli Gates in Multi-Qubit Setting] at the Wolfram Demonstrations Project.

* Related Gates' figure public online [http://www.InterQuanta.biz/im "Information Mechanics in Unconventional Computing"], Review of Information Mechanics, ''InterQuanta''

{{論理ゲート}}

{{DEFAULTSORT:とふおりけと}}
[[Category:論理ゲート]]
[[Category:可逆計算]]