トフォリゲート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
トフォリゲートの記号

トフォリゲート (: Toffoli gate) は、トマソ・トフォリの提案した量子計算可逆計算上で重要な論理ゲートである。トフォリゲートは万能である。すなわち、可逆計算を行うどのような論理回路もトフォリゲートの組み合わせに還元できる。別名のCCNOTゲートは、動作を表す "controlled-controlled-not" (制御・制御・NOTゲート) の略称である。

概要[編集]

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

入力 出力
0 1
1 0

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

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

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

トフォリゲートの機能的完全性[編集]

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

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

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

真理値表 行列表現
入力 出力
 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}

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

CNOT(x, y) = (x, x \oplus y)

しかし、この演算のみでは表現できない可逆計算が存在する。つまり、CNOTは機能的完全性を持たない。機能的完全性英語版を持つ演算の一つがトマソ・トフォリによって提案されたトフォリゲートである[1]

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

真理値表 行列表現
入力 出力
 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}

また、論理式で表すと次のようになる。

CCNOT(x, y, z) = (x, y, (x \cdot y) \oplus z)

トフォリゲートは機能的完全性英語版をもつ。つまり、どのような論理関数 f(x1, x2, ..., xm) に対しても、トフォリゲートのみを使って x1, x2, ..., xm と幾つかの作業用のビットを入力に取り x1, x2, ..., xm, f(x1, x2, ..., xm) と幾つかの作業に使われた不要なビットを出力する論理回路を構成できる。これは、トフォリゲートを使って論理関数を可逆的に計算することができることを意味する。

関連する論理ゲート[編集]

  • フレドキンゲートはトフォリゲートと同様の3ビット可逆ゲートで、1ビット目が1のときに残りのビットを交換する。制御交換ゲートとも呼ばれる。
  • 任意のビット数に対してトフォリゲートを一般化することができる。n ビットの入力 x1, x2, ..., xn をとり、 n ビットを出力するものとする。最初の n−1 ビットはそのまま入力の x1, ..., xn−1 を出力し、最後のビットに (x1 AND ... AND xn−1) XOR xn を出力する。
  • トフォリゲートは2量子ビットを扱うゲートを5つ組み合わせることによって量子コンピュータ上で実現できる[2]

量子計算との関係[編集]

量子コンピュータの回路上では可逆ゲートが実現できるので、トフォリゲートも量子演算の一種である。トフォリゲートは量子計算の演算としては万能ではないが、量子コンピュータ上で古典的な可逆計算が実行できるということは言える。量子トフォリゲートは2009年1月、オーストリアインスブルック大学で実現された[4]

関連項目[編集]

脚注[編集]

  1. ^ Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: Toffoli, Tommaso (1980). “Reversible computing”. In J. W. de Bakker and J. van Leeuwen. Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. pp. 632-644. ISBN 3-540-10003-2. http://pm1.bu.edu/~tt/publ/revcomp-rep.pdf 
  2. ^ Barenco, Adriano; Bennett, Charles H.; Richard, Cleve; DiVincenzo, David P.; Margolus, Norman; Shor, Peter; Sleator, Tycho; Smolin, John A. et al. (Nov 1995). “Elementary gates for quantum computation”. Phys. Rev. A (American Physical Society) 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 (April 1982). “Conservative logic”. International Journal of Theoretical Physics (Springer Netherlands) 21 (3): 219–253. Bibcode 1982IJTP...21..219F. doi:10.1007/BF01857727. ISSN 0020-7748. http://www.digitalphilosophy.org/LinkClick.aspx?fileticket=5wPlkttI56o%3d&tabid=61&mid=494&forcedownload=true. 
  4. ^ Monz, T.; Kim, K.; Hänsel, W.; Riebe, M.; Villar, A. S.; Schindler, P.; Chwalla, M.; Hennrich, M. et al. (Jan 2009). “Realization of the Quantum Toffoli Gate with Trapped Ions”. R. (American Physical Society) 102 (4): 040501. arXiv:0804.0082. Bibcode 2009PhRvL.102d0501M. doi:10.1103/PhysRevLett.102.040501.