トフォリゲート

ウィキペディア

トフォリゲート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/09/07 09:31 UTC 版)

トフォリゲートの記号

トフォリゲート (英: Toffoli gate) は、トマソ・トフォリの提案した可逆論理ゲートである。トフォリゲートはfunctional complete（en:Functional completeness）である。すなわち、任意の論理演算がトフォリゲートの組み合わせにより実現できる。別名の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}}$ ビリヤードボール・コンピュータ フレドキンゲートはトフォリゲートと同様の3ビット可逆ゲートで、1ビット目が1のときに残りのビットを交換する。制御交換ゲートとも呼ばれる。 任意のビット数に対してトフォリゲートを一般化することができる。n ビットの入力 x1, x2, ..., xn をとり、 n ビットを出力するものとする。最初の n−1 ビットはそのまま入力の x1, ..., xn−1 を出力し、最後のビットに (x1 AND ... AND xn−1) XOR xn を出力する。 トフォリゲートは2量子ビットを扱うゲートを5つ組み合わせることによって量子コンピュータ上で実現できる。 トフォリゲートは仕切りとビリヤードボールを使って実装できる（ビリヤードボール・コンピュータを参照）。このモデルはフレドキンとトフォリが提案した。図はボールの衝突がどのように進むかを示したものである。 量子計算との関係 量子トフォリゲートは2009年1月、オーストリアのインスブルック大学で実現された。 関連項目 フレドキンゲート 可逆計算 量子コンピュータ 外部リンク CNOT and Toffoli Gates in Multi-Qubit Setting at the Wolfram Demonstrations Project. Related Gates' figure public online "Information Mechanics in Unconventional Computing", Review of Information Mechanics, InterQuanta