トフォリゲートの機能的完全性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/11/22 09:15 UTC 版)
「トフォリゲート」の記事における「トフォリゲートの機能的完全性」の解説
すべての可逆ゲートは同じ数の入力ビットと出力ビットをもつ。これは鳩の巣原理による。 1ビットに対しては、恒等写像とNOTゲートのふたつの可逆ゲートがある。この二種類はどのビット数に対しても同様のゲートが定義できる。 2ビットに対しては、上の二種類と交換などの自明なものを除くと、制御NOTゲートが唯一の演算である。このゲートは一つ目の入力を二つ目の入力にXORし、二つ目に出力する。一つ目の入力はそのまま出力される。動作を以下に示す。 真理値表置換行列表現入力出力 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 [ 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 ] {\displaystyle {\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\\end{bmatrix}}} また、論理式で表すと次のようになる(複数ビットの出力をタプルで表した)。 C N O T ( x , y ) = ( x , x ⊕ y ) {\displaystyle 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 [ 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 ] {\displaystyle {\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}}} また、論理式で表すと次のようになる。 C C N O T ( x , y , z ) = ( x , y , ( x ⋅ y ) ⊕ z ) {\displaystyle 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) と幾つかの作業に使われた不要なビットを出力する論理回路を構成できる。これは、トフォリゲートを使って論理関数を可逆的に計算することができることを意味する。
※この「トフォリゲートの機能的完全性」の解説は、「トフォリゲート」の解説の一部です。
「トフォリゲートの機能的完全性」を含む「トフォリゲート」の記事については、「トフォリゲート」の概要を参照ください。
- トフォリゲートの機能的完全性のページへのリンク
