フレドキンゲート

フレドキンゲート（英: Fredkin gate）は、エドワード・フレドキンが提案した可逆論理ゲートである。単独でfunctional completeness () を有しているので、任意の論理演算をフレドキンゲートだけを使って構成できる。
基本フレドキンゲートは、3つの入力 ("C", "I"1, "I"2) と3つの出力 ("C", "O"1, "O"2) を写像する「制御付き交換ゲート」である。入力 "C" はそのまま出力 "C" に対応する。"C" = 0 の場合交換はなされず、"I"1 は "O"1 に、"I"2 は "O"2 に対応する。そうでない場合2つの出力は交換され、"I"1 は "O"2 に、"I"2 は "O"1 にマッピングされる。入力と出力を入れ替えても同じに動作することから、この回路が可逆性であることは容易に示すことができる。これをさらに一般化した "n"×"n" フレドキンゲートは、最初の "n"-2 個の入力をそのまま対応する出力に出力し、残る2つは最初の "n"-2 個の入力が全て1の場合だけ交換して出力する。
フレドキンゲートは可逆3ビットゲートであり、最初のビットが1の場合に残る2ビットを交換して出力する。真理値表を右に示す。
0と1の個数が保存されるという便利な特性があり、ビリヤードボールモデルで入力されたボールの数と出力ボール数が同じになるのと同じである。これは物理学における質量保存の法則にもうまく対応し、このモデルが無駄ではないことを示す助けにもなっている。
XORゲートとANDゲートによる論理関数.
フレドキンゲートをXORゲートとANDゲートで構成する場合、次のようになる。