토폴리/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}$ 게이트의 성질에 의해 성립한다.
■
같이보기
- $\text{AND}$ 게이트논리곱
- $\text{OR}$ 게이트논리합
- $\text{NOT}$ 게이트논리 부정
- $\text{XOR}$ 게이트배타적 논리합
- $\text{NAND}$ 게이트부정논리곱
- $\text{NOR}$ 게이트부정논리합
- $\operatorname{CNOT}$ 게이트
- 프레드킨 게이트$\text{CSWAP}$ 게이트
김영훈·허재성, 양자 정보 이론 (2020), p89-93 ↩︎