📂양자정보이론

함수적으로 완전한 집합이란?

양자정보이론

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

정의¹

부울함수들의 집합 $\left\{ f_{k} \right\} = \left\{ f_{k} : \left\{ 0, 1 \right\}^{n_{k}} \to \left\{ 0, 1 \right\} \right\}_{k\in \Gamma}$이 주어졌다고 하자. $\Gamma$는 유한집합이다. $\left\{ f_{k} \right\}$들의 합성으로 임의의 부울함수

$$ \left\{ 0, 1 \right\}^{n} \to \left\{ 0, 1 \right\}\quad (n \in \mathbb{N}) $$

을 표현할 수 있으면, 집합 $\left\{ f_{k} \right\}$를 함수적으로 완전하다^{functionally complete}고 한다.

정리

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

설명

다시말해 모든 부울 함수는 $\text{NOT}$와 $\text{AND}$의 반복으로 만들 수 있다. 함수적으로 완전한 집합은 유일하지 않으며, 무수히 많다. 가령 $a \land b = \lnot(\lnot a \lor \lnot b)$이기 때문에, $\left\{ \lnot, \lor \right\}$도 함수적으로 완전한 집합이다. 이 정리로부터 임의의 집합이 $\text{AND}$ 게이트와 $\text{NOT}$ 게이트를 만들 수 있는지만 보여도 함수적으로 완전한 집합임을 증명할 수 있다.

함수적으로 완전한 집합들의 예시:

• $\text{NAND}$ 게이트
• $\text{NOR}$ 게이트
• $T$(토폴리 게이트)
• $F$(프레드킨 게이트)
• $\left\{ \lnot, \lor \right\}$
• $\left\{ \oplus, \land \right\}$

물론 여기에 복제 함수가 필요한 경우도 있다. 위의 결과들을 컴퓨터 회로에 대한 언어로 서술하면 다음과 같다. 모든 논리 연산은:

• $\text{NOT}$ 게이트와 $\text{AND}$ 게이트만을 사용하여 회로로 구현할 수 있다.
• $\text{NAND}$ 게이트와 복제 함수만을 사용하여 회로로 구현할 수 있다.
• $\text{NOR}$ 게이트와 복제 함수만을 사용하여 회로로 구현할 수 있다.
• 토폴리 게이트만을 사용하여 회로로 구현할 수 있다.
• 프레드킨 게이트만을 사용하여 회로로 구현할 수 있다.

범용 게이트

특히나 자기 자신만으로 이루어진 집합 $\left\{ f \right\}$가 함수적으로 완전할 때, 이러한 $f$를 범용 게이트^{universal gate}라 한다. 범용 게이트는 자기 자신만으로 모든 부울 함수를 표현할 수 있다. $\text{NAND}$, $\text{NOR}$, $T$, $F$는 범용 게이트이다.