📂양자정보이론

배타적 논리합, XOR 게이트

양자정보이론

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

정의¹

다음과 같은 부울함수를 $\text{XOR}$ 게이트^{XOR gate} 혹은 배타적 논리합^{exclusive disjuction/or}이라 하고 다음과 같이 표기한다.

$$\oplus : \left\{ 0, 1 \right\}^{2} \to \left\{ 0, 1 \right\}$$

$$0\oplus 0 = 0,\quad 0\oplus 1 = 1,\quad 1\oplus 0 = 1,\quad 1\oplus 1 = 0$$

설명

$\text{XOR}$ 게이트는 두 진리값 중 하나만 참일 때, 즉 참이 홀수일 때 참을 반환한다. 다시말하면 두 값이 같으면 $0$, 다르면 $1$을 반환하므로 두 값이 같은지를 비교하는 기능을 구현할 때 유용하다.

"퍼셉트론은 $\text{XOR}$ 문제를 풀 수 없다"는 지적 때문에 AI의 발전이 침체된 시기인 1974년부터 1980년까지를 AI 겨울^{AI winter}이라고 말한다.

부울 함수	기호	진리표
$\text{XOR}$		$a$ $b$ $a \oplus b$ $0$ $0$ $0$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $0$

성질

• $\text{NOT}$ 게이트, $\text{AND}$ 게이트, $\text{OR}$ 게이트로 표현 가능하다.

  $$\begin{align*} a \oplus b &= (a \land \lnot b) \lor (\lnot a \land b) \\ &= (a \lor b) \land (\lnot a \lor \lnot b) \\ &= (a \lor b) \land \lnot (a \land b) \end{align*}$$

• $a \oplus 1 = \lnot a$가 성립한다.

• $a \oplus 0 = a$가 성립한다.

같이보기

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