トッフォリ/CCNOTゲート

定義¹

以下のようなベクトル値ブール関数をトフォリゲート^{Toffoli gate}と呼ぶ。

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

$$T (a, b, c) = (a, b, (a \land b) \oplus c)$$

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

説明

トフォリゲートでは、最初の二つの入力が両方とも$1$であれば、三番目の入力が反転する。その他の場合は、入力と出力が同じである。具体的な計算は以下の通りである。

$$\begin{align*} T (0,0,0) &= (0, 0, (0 \land 0) \oplus 0) = (0, 0, 0 \oplus 0) = (0, 0, 0) \\ T (0,0,1) &= (0, 0, (0 \land 0) \oplus 1) = (0, 0, 0 \oplus 1) = (0, 0, 1) \\ T (0,1,0) &= (0, 1, (0 \land 1) \oplus 0) = (0, 1, 0 \oplus 0) = (0, 1, 0) \\ T (0,1,1) &= (0, 1, (0 \land 1) \oplus 1) = (0, 1, 0 \oplus 1) = (0, 1, 1) \\ T (1,0,0) &= (1, 0, (1 \land 0) \oplus 0) = (1, 0, 0 \oplus 0) = (1, 0, 0) \\ T (1,0,1) &= (1, 0, (1 \land 0) \oplus 1) = (1, 0, 0 \oplus 1) = (1, 0, 1) \\ T (1,1,0) &= (1, 1, (1 \land 1) \oplus 0) = (1, 1, 1 \oplus 0) = (1, 1, 1) \\ T (1,1,1) &= (1, 1, (1 \land 1) \oplus 1) = (1, 1, 1 \oplus 1) = (1, 1, 0) \\ \end{align*}$$

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

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

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

부울 함수	기호	진리표
$T$		입력 출력 $a$ $b$ $c$ $a$ $b$ $(a \land b) \oplus c$ $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$

整理

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

証明

定理

複製関数を許可すると、$\left\{ \uparrow \right\}$は機能的に完全である。つまり$\text{NAND}$ゲート$\uparrow$は汎用ゲートである。

上の定理に従い、射影、注入、$T$を適切に使用して複製関数$\text{cl}$と$\text{NAND}$ゲートを表現できることを示せば証明が完了する。

• 複製関数

  $$\operatorname{cl} = p_{1} \circ T \circ \imath_{2} \circ \jmath_{1}$$

  が成り立つ。まず$T \circ \imath_{2} \circ \jmath_{1} (a)$を計算すると以下のようになる。

  $$T \circ \imath_{2} \circ \jmath_{1} (a) = T \circ \imath_{2} (a, 1) = T (a, 1, 0)$$

  ここで$a = 1$であれば$T(1, 1, 0) = (1, 1, 1)$であり、$a = 0$であれば$T(0, 1, 0) = (0, 1, 0)$であるため、次が成り立つ。

  $$T(a, 1, 0) = (a, 1, a)$$

  したがって$p_{1}$を取れば、

  $$p_{1} \circ T \circ \imath_{2} \circ \jmath_{1} (a) = p_{1} (a, 1, a) = (a, a) = \operatorname{cl}(a)$$

• $\text{NAND}$ゲート

  $$p_{0} \circ p_{1} \circ T \circ \jmath_{2} = \uparrow \\ p_{0} \circ p_{1} \circ T \circ \jmath_{2} (a, b) = a \uparrow b$$

  が成り立つ。順に計算すると以下のようになる。

  $$\begin{align*} p_{0} \circ p_{1} \circ T \circ \jmath_{2} (a, b) &= p_{0} \circ p_{1} \circ T (a, b, 1) \\ &= p_{0} \circ p_{1} (a, b, (a \land b) \oplus 1) \\ &= p_{0} (a, (a \land b) \oplus 1) \\ &= (a \land b) \oplus 1 \\ &= \lnot(a \land b) = a \uparrow b \end{align*}$$

  最後の行は$\text{XOR}$ゲートの性質によって成り立つ。

■