トッフォリ/CCNOTゲート
定義1
以下のようなベクトル値ブール関数をトフォリゲート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$ |
|
整理
(射影と注入を制約なく使えると仮定すると)トフォリゲート$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}$ゲートの性質によって成り立つ。
■
木村泰宏・許在成, 量子情報理論 (2020), p89-93 ↩︎