📂양자정보이론

프레드킨/CSWAP 게이트

양자정보이론

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

정의¹

다음과 같은 벡터값 부울함수를 프레드킨 게이트^{Fredkin gate}라고 한다.

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

$$F (a, b, c) = \Big(a, (\lnot a \land b) \lor (a \land c), (\lnot a \land c) \lor (a \land b) \Big)$$

• $\text{CSWAP}$ 게이트^{Controlled SWAP(CSWAP) gate}라고도 한다.

설명

에드워드 프레드킨^{Edward Fredkin}에 의해 소개되었다. 프레드킨 게이트는 첫번째 입력은 바꾸지않고, 첫번째 입력이 $1$인 경우에는 나머지 두 값을 교환^swap하여 출력한다. 그 구체적인 계산은 다음과 같다.

$$\begin{align*} F (0,0,0) &= (0, (\lnot 0 \land 0) \lor (0 \land 0), (\lnot 0 \land 0) \lor (0 \land 0)) = (0, 0 \lor 0, 0 \lor 0) = (0, 0, 0) \\ F (0,0,1) &= (0, (\lnot 0 \land 0) \lor (0 \land 1), (\lnot 0 \land 1) \lor (0 \land 0)) = (0, 0 \lor 0, 1 \lor 0) = (0, 0, 1) \\ F (0,1,0) &= (0, (\lnot 0 \land 1) \lor (0 \land 0), (\lnot 0 \land 0) \lor (0 \land 1)) = (0, 1 \lor 0, 0 \lor 0) = (0, 1, 0) \\ F (0,1,1) &= (0, (\lnot 0 \land 1) \lor (0 \land 1), (\lnot 0 \land 1) \lor (0 \land 1)) = (0, 1 \lor 0, 1 \lor 0) = (0, 1, 1) \\ F (1,0,0) &= (1, (\lnot 1 \land 0) \lor (1 \land 0), (\lnot 1 \land 0) \lor (1 \land 0)) = (1, 0 \lor 0, 0 \lor 0) = (1, 0, 0) \\ F (1,0,1) &= (1, (\lnot 1 \land 0) \lor (1 \land 1), (\lnot 1 \land 1) \lor (1 \land 0)) = (1, 0 \lor 1, 0 \lor 0) = (1, 1, 0) \\ F (1,1,0) &= (1, (\lnot 1 \land 1) \lor (1 \land 0), (\lnot 1 \land 0) \lor (1 \land 1)) = (1, 0 \lor 0, 0 \lor 1) = (1, 0, 1) \\ F (1,1,1) &= (1, (\lnot 1 \land 1) \lor (1 \land 1), (\lnot 1 \land 1) \lor (1 \land 1)) = (1, 0 \lor 1, 0 \lor 1) = (1, 1, 1) \\ \end{align*}$$

위 표를 보면 $F$가 가역 함수라는 사실과 $F$를 두 번 합성하면 항등함수가 됨을 쉽게 알 수 있다.

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

또한 $\left\{ F \right\}$가 함수적으로 완전하므로, $F$는 범용 게이트이다.

부울 함수	기호
$F$

진리표

입력 출력 $a$ $b$ $c$ $a$ $(\lnot a \land b) \lor (a \land c)$ $(\lnot a \land c) \lor (a \land b)$ $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$ $1$ $0$ $1$ $1$ $0$ $1$ $0$ $1$ $1$ $1$ $1$ $1$ $1$ $1$

정리

(사영과 주입을 제약없이 쓸 수 있다고 가정하면) 프레드킨 게이트 $F$는 범용 게이트이다. 다시말해 $\left\{ F \right\}$는 함수적으로 완전하다.

증명

정리

$\text{NOT}$ 게이트와 $\text{AND}$ 게이트의 집합 $\left\{ \lnot, \land \right\}$은 함수적으로 완전하다.

위의 정리에 따라 사영, 주입, $F$를 적절히 사용하여 $\text{NOT}$, $\text{AND}$를 표현할 수 있음을 보이면 증명이 끝난다.

• $\text{NOT}$ 게이트

  $$\lnot = p_{0} \circ p_{1} \circ F \circ \jmath_{2} \circ \imath_{1}$$

  가 성립한다. 우선 $\jmath_{2} \circ \imath_{1} (a) = (a, 0, 1)$이므로 다음을 얻는다.

  $$\begin{equation} F \circ \jmath_{2} \circ \imath_{1}(a) = F(a, 0, 1) = (a, a, \lnot a) \end{equation}$$

  여기서 앞의 두 값을 지우기 위해 $p_{0} \circ p_{1}$를 취하면,

  $$p_{0} \circ p_{1} \circ F \circ \jmath_{2} \circ \imath_{1} (a) = p_{0} \circ p_{1} (a, a, \lnot a) = \lnot a$$

  ※ 추가적으로 $(1)$에 $p_{2}$을 적용하면 복제 함수를 얻는다.

• $\text{AND}$ 게이트

  $$\land = p_{0} \circ p_{1} \circ F \circ \imath_{2}$$

  가 성립한다. 우선 $F \circ \jmath_{2} (a, b)$는 다음과 같다.

  $$\begin{align*} F \circ \jmath_{2} (a, b) = F(a, b, 0) &= (a, (\lnot a \land b) \lor (a \land 0), (\lnot a \land 0) \lor (a \land b)) \\ &= (a, (\lnot a \land b) \lor 0, 0 \lor (a \land b)) \\ &= (a, \lnot a \land b, a \land b) \end{align*}$$

  따라서 $p_{0} \circ p_{1}$를 취하면,

  $$p_{0} \circ p_{1} \circ F \circ \imath_{2} (a, b) = p_{0} \circ p_{1} (a, \lnot a \land b, a \land b) = a \land b$$

■

같이보기

• $\text{AND}$ 게이트^논리곱
• $\text{OR}$ 게이트^논리합
• $\text{NOT}$ 게이트^{논리 부정}
• $\text{XOR}$ 게이트^{배타적 논리합}
• $\text{NAND}$ 게이트^{부정논리곱}
• $\text{NOR}$ 게이트^{부정논리합}
• $\operatorname{CNOT}$ 게이트
• 토폴리 게이트^{$\text{CCNOT}$ 게이트}