logo

토폴리/CCNOT 게이트 📂양자정보이론

토폴리/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$
입력출력
$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}$ 게이트의 성질에 의해 성립한다.

같이보기


  1. 김영훈·허재성, 양자 정보 이론 (2020), p89-93 ↩︎