フレドキン・CSWAPゲート

定義¹

以下のようなベクトル値ブール関数をフレドキンゲート^{Fredkin gate}と呼ぶ。

$$ F : \left\{ 0, 1 \right\}^{3} \to \left\{ 0, 1 \right\}^{3} $$

$$ F (a, b, c) = \Big(a, (\lnot a \land b) \lor (a \land c), (\lnot a \land c) \lor (a \land b) \Big) $$

• $\text{CSWAP}$ ゲート^{Controlled SWAP(CSWAP) gate}とも呼ばれる。

説明

エドワード・フレドキン^{Edward Fredkin}によって紹介された。フレドキンゲートは、最初の入力を変えずに、最初の入力が$1$の場合には、残りの二つの値を交換^swapして出力する。その具体的な計算は次のようである。

$$ \begin{align*} F (0,0,0) &= (0, (\lnot 0 \land 0) \lor (0 \land 0), (\lnot 0 \land 0) \lor (0 \land 0)) = (0, 0 \lor 0, 0 \lor 0) = (0, 0, 0) \\ F (0,0,1) &= (0, (\lnot 0 \land 0) \lor (0 \land 1), (\lnot 0 \land 1) \lor (0 \land 0)) = (0, 0 \lor 0, 1 \lor 0) = (0, 0, 1) \\ F (0,1,0) &= (0, (\lnot 0 \land 1) \lor (0 \land 0), (\lnot 0 \land 0) \lor (0 \land 1)) = (0, 1 \lor 0, 0 \lor 0) = (0, 1, 0) \\ F (0,1,1) &= (0, (\lnot 0 \land 1) \lor (0 \land 1), (\lnot 0 \land 1) \lor (0 \land 1)) = (0, 1 \lor 0, 1 \lor 0) = (0, 1, 1) \\ F (1,0,0) &= (1, (\lnot 1 \land 0) \lor (1 \land 0), (\lnot 1 \land 0) \lor (1 \land 0)) = (1, 0 \lor 0, 0 \lor 0) = (1, 0, 0) \\ F (1,0,1) &= (1, (\lnot 1 \land 0) \lor (1 \land 1), (\lnot 1 \land 1) \lor (1 \land 0)) = (1, 0 \lor 1, 0 \lor 0) = (1, 1, 0) \\ F (1,1,0) &= (1, (\lnot 1 \land 1) \lor (1 \land 0), (\lnot 1 \land 0) \lor (1 \land 1)) = (1, 0 \lor 0, 0 \lor 1) = (1, 0, 1) \\ F (1,1,1) &= (1, (\lnot 1 \land 1) \lor (1 \land 1), (\lnot 1 \land 1) \lor (1 \land 1)) = (1, 0 \lor 1, 0 \lor 1) = (1, 1, 1) \\ \end{align*} $$

上の表を見れば、$F$が可逆関数であることと、$F$を二回合成すると恒等関数になることが容易にわかる。

$$ \operatorname{Id} = F \circ F $$

また、$\left\{ F \right\}$が機能的に完全であるため、$F$は汎用ゲートである。

ブール関数	シンボル
$F$

整理

(射影と注入を制約なく使えると仮定すると)フレドキンゲート$F$は汎用ゲートである。つまり、$\left\{ F \right\}$は機能的に完全である。

証明

定理

$\text{NOT}$ゲートと$\text{AND}$ゲートの集合$\left\{ \lnot, \land \right\}$は機能的に完全である。

上の定理に従って、射影、注入、$F$を適切に使用して$\text{NOT}$、$\text{AND}$を表現できることを示せば、証明は終了する。

• $\text{NOT}$ゲート

  $$ \lnot = p_{0} \circ p_{1} \circ F \circ \jmath_{2} \circ \imath_{1} $$

  が成り立つ。まず$\jmath_{2} \circ \imath_{1} (a) = (a, 0, 1)$であるため、次を得る。

  $$ \begin{equation} F \circ \jmath_{2} \circ \imath_{1}(a) = F(a, 0, 1) = (a, a, \lnot a) \end{equation} $$

  ここで、最初の二つの値を消去するために$p_{0} \circ p_{1}$を取ると、

  $$ p_{0} \circ p_{1} \circ F \circ \jmath_{2} \circ \imath_{1} (a) = p_{0} \circ p_{1} (a, a, \lnot a) = \lnot a $$

  ※ さらに$(1)$に$p_{2}$を適用すると、複製関数を得る。

• $\text{AND}$ゲート

  $$ \land = p_{0} \circ p_{1} \circ F \circ \imath_{2} $$

  が成り立つ。まず$F \circ \jmath_{2} (a, b)$は次のようである。

  $$ \begin{align*} F \circ \jmath_{2} (a, b) = F(a, b, 0) &= (a, (\lnot a \land b) \lor (a \land 0), (\lnot a \land 0) \lor (a \land b)) \\ &= (a, (\lnot a \land b) \lor 0, 0 \lor (a \land b)) \\ &= (a, \lnot a \land b, a \land b) \end{align*} $$

  したがって、$p_{0} \circ p_{1}$を取ると、

  $$ p_{0} \circ p_{1} \circ F \circ \imath_{2} (a, b) = p_{0} \circ p_{1} (a, \lnot a \land b, a \land b) = a \land b $$

■

関連項目

• $\text{AND}$ゲート^論理積
• $\text{OR}$ゲート^論理和
• $\text{NOT}$ゲート^論理否定
• $\text{XOR}$ゲート^{排他的論理和}
• $\text{NAND}$ゲート^{否定論理積}
• $\text{NOR}$ゲート^{否定論理和}
• $\operatorname{CNOT}$ゲート
• トフォリゲート^{$\text{CCNOT}$ゲート}