フレドキン・CSWAPゲート
定義1
以下のようなベクトル値ブール関数をフレドキンゲート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}$ゲート
金永勳·許在成, 量子情報理論 (2020), p90-93 ↩︎