1.3.2 다수 큐비트 게이트

단일 큐비트에서 다수 큐비트로 일반화, 

그림에선 AND, OR, XOR, NAND, NOR 의 주목할 만한 고전 다수 비트 게이트들이 나타나있다.

중요한 이론적 결과에 따르면, NAND 게이트만으로 구성해도 비트에 대한 어떠한 함수라도 계산할 수 있는데, 따라서 이를 보편적 게이트 universal gate 라고 부른다. 이와는 반대로 XOR 만으로는 보편적이 되지 않는다. 

이를 알아보는 방법은 XOR 게이트를 적용해서 비트들의 전체 패리티 parity 가 변하는지를 알아보면 된다. 결과적으로 NOT 와 XOR 만 들어간 회로에서 두 입력 x 와 y 의 패리티가 서로 같으면 동일한 패리티를 갖는 출력들이 나오므로 계산할 수 있는 함수 클래스들이 제한되고 이에 따라 보편적이지 않다.

원형 prototype 의 다수 큐비트 양자 논리 게이트는 제어형 NOT controlled-NOT 또는 CNOT 게이트이다. 이 게이트는 각각 제어 큐비트 control qubit 와 대상 큐비드 target qubit 라는 2개의 입력 큐비트를 갖는다. CNOT 의 회로 표현은 그림의 오른쪽 위에 나타나 있다. 

이 게이트의 동작은 다음과 같다. 제어 큐비트가 0 이면 대상 큐비트는 그대로다. 제어 큐비트가 1이면 대상 큐비트를 반전시킨다. 

|00> → |00>; |01> → |01>; |10> → |11>; |11> → |10>

CNOT 를 기술하는 또 다른 방법은 고전 XOR 게이트를 일반화시키는 것인데 그 이유는 이 게이트의 동작을 |A, B> → |A, B OPLUS A> 로 요약할 수 있기 때문이다. OPLUS 는 모듈러 2 덧셈 addition momdulo two 이며 XOR 게이트의 동작과 같다. 즉, 제어 큐비트와 대상 큐비트를 XOR 연산 후 대상 큐비트에 저장한다.

CNOT 의 동작을 기술하는 또 다른 방법은 그림의 오른쪽 아래에 나타낸 것처럼 행렬로 표현하는 것이다. U_CN 의 첫 번째 열은 |00> 에게 발생하는 변호나을 기술한다는 것을 쉽게 확인할 수 있으며 다른 계산 기저 상태들에 대해서도 마찬가지다. 단일 큐비트에 있어서 확률이 보존된다는 요구사항은 U_CN 이 유니타리 행렬, 즉 U_CN^DAGGER U_CN = I 이라는 사실로 표현된다.

우리는 CNOT 이 일종의 일반화된 XOR 게이트로 간주될 수 있다는 점을 알았다. 양자 NOT 게이트가 고전 NOT 게이트를 기술하는 것과 비슷한 의미로 NAND 또는 보통의 XOR 게이트와 같은 다른 고전 게이트를 유니타리 게이트로 이해할 수 있을까? 이것은 불가능하다는 것이 밝혀졌다.

그 이유는 NAND 또는 XOR 게이트는 본질적으로 비가역적 irreversible, 즉 역방향 계산이 불가하기 non-invertible 때문이다. 예를 들어 XOR 게이트에서 A OPLUS B 출력이 나왔다고 해서 A 와 B 입력이 무엇이었는지 알아낼 수 없다. 즉, XOR 게이트에서 역동작을 취하면 그에 따른 정보 손실 loss of information 이 발생한다. 

하지만 유티나리 양자 게이트는 항상 가역적이다. 즉 유니타리 행렬의 역행렬 역시 유니타리 행렬이기 때문에 양자 게이트의 역방향은 다른 양자 게이트를 사용해 표시할 수 있다. 이렇게 가역적이거나 역방향 계산 가능한 의미로 고전 논리 수행 방법을 이해해야만 계산에 있어서 양자역학의 강력함에 대한 활용법을 알게 된다.

제어형 NOT 게이트와 단일 큐비트 게이트들은 다음과 같은 탁월한 보편성 결과 때문에 다른 모든 게이트의 원형이 된다. 즉, 모든 다수 큐비트 논리 게이트는 CNOT 게이트와 단일 큐비트 게이트들로 구성될 수 있다. NAND 게이트의 보편성에 대한 양자 버전이라 할 수 있다.