📂양자정보이론

토폴리/CCNOT 게이트

양자정보이론

[ 펼치기 · 접기 ] 양자계산 논리게이트 비트 · 부울함수(AND · OR · NOT · XOR · NAND · NOR · CNOT · CCNOT · CSWAP) · 범용 게이트 · 복제 함수 · 사영 · 주입 양자게이트 큐비트 · 양자 얽힘 · 양자 회로 · 양자 게이트(파울리 게이트 · 위상 게이트 · 아다마르 게이트 · 양자 CNOT · 교환 게이트 · 양자 CSWAP · 양자 CSWAP) · 솔베이-키타예프 정리 · 복제 불가 정리 정보이론 고전정보이론 정보량 · 엔트로피(결합 엔트로피 · 조건부 엔트로피 · 상대적 엔트로피 · 상호 정보 ) · 부호화 · 복호화 양자정보이론 TBD · TBD · TBD 관련 분야 선형대수 · 양자역학

정의¹

다음과 같은 벡터값 부울함수를 토폴리 게이트^{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}$ 게이트의 성질에 의해 성립한다.

■

같이보기

• $\text{AND}$ 게이트^논리곱
• $\text{OR}$ 게이트^논리합
• $\text{NOT}$ 게이트^{논리 부정}
• $\text{XOR}$ 게이트^{배타적 논리합}
• $\text{NAND}$ 게이트^{부정논리곱}
• $\text{NOR}$ 게이트^{부정논리합}
• $\operatorname{CNOT}$ 게이트
• 프레드킨 게이트^{$\text{CSWAP}$ 게이트}