トフォリゲート

トフォリゲートの記号

トフォリゲート (英: 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}}$

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

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

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

このゲートは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(x₁, x₂, ..., x_m) に対しても、トフォリゲートのみを使って x₁, x₂, ..., x_m と幾つかの作業用のビットを入力に取り x₁, x₂, ..., x_m, f(x₁, x₂, ..., x_m) と幾つかの作業に使われた不要なビットを出力する論理回路を構成できる。これは、トフォリゲートを使って論理関数を可逆的に計算することができることを意味する。

関連する論理ゲート

ビリヤードボール・コンピュータ

• フレドキンゲートはトフォリゲートと同様の3ビット可逆ゲートで、1ビット目が1のときに残りのビットを交換する。制御交換ゲートとも呼ばれる。

• 任意のビット数に対してトフォリゲートを一般化することができる。n ビットの入力 x₁, x₂, ..., x_n をとり、 n ビットを出力するものとする。最初の n−1 ビットはそのまま入力の x₁, ..., x_n−1 を出力し、最後のビットに (x₁ AND ... AND x_n−1) XOR x_n を出力する。
• トフォリゲートは2量子ビットを扱うゲートを5つ組み合わせることによって量子コンピュータ上で実現できる。

• トフォリゲートは仕切りとビリヤードボールを使って実装できる（ビリヤードボール・コンピュータを参照）。このモデルはフレドキンとトフォリが提案した。図はボールの衝突がどのように進むかを示したものである。

ハードウェアによる記述

ハードウェア記述言語Verilogで実装された古典的なトフォリゲートは以下のようになる。

module toffoli_gate (
 input u1, input u2, input in,
 output v1, output v2, output out);
always @(*) begin
    v1 = u1;
    v2 = u2;
    out = in ^ (u1 && u2);
end
endmodule

量子計算との関係

量子トフォリゲートは2009年1月、オーストリアのインスブルック大学で実現された。

n量子ビットのトフォリ回路の回路モデルを作成するにあたって、$2n$ CNOT 回路 が必要であり、上限として知られているのは$6n-12$ CNOT 回路 である。

また、イオントラップやリードブルグ原子、超電導回路における直接操作は多体相互作用の応用を用いることで実装できる。

関連項目

• フレドキンゲート
• 可逆計算
• 量子コンピュータ

外部リンク

• 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