토폴리 게이트

논리 회로에서 1980년 토마소 토폴리가 발명한 토폴리 게이트()는 CCNOT 게이트("controlled-controlled-not")라고도 불리며, 두 개의 제어 비트와 하나의 대상 비트를 가진 CNOT 게이트이다. 즉, 첫 번째와 두 번째 비트가 모두 1일 경우 대상 비트(세 번째 비트)가 반전된다. 이는 모든 고전적 가역 회로를 토폴리 게이트로 구성할 수 있다는 의미에서 보편적인 가역 논리 게이트이다. 비트가 큐비트로 대체되는 양자 컴퓨팅 버전도 있다.

 설명 
진리표와 치환행렬은 다음과 같다(순환 표기법으로 (7,8)로 쓸 수 있다):

 진리표  치환행렬 입력 출력 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  0  1 1  1  0  1  1  1 1  1  1  1  1  0

 배경 
입력을 소비하는 논리 게이트 L은 다음 조건을 충족하면 가역적이다. (1) L(x) = y는 어떤 출력 y에 대해 고유한 입력 x가 있는 게이트이다. (2) 게이트 L은 모든 y에 대해 y를 x로 매핑하는 게이트 L´(y) = x가 존재하면 가역적이다.

가역 논리 게이트의 예로는 아래 진리표에서 설명할 수 있는 NOT 게이트가 있다.

 입력  출력조건 (1)조건 (2) 0  1x = 0 y = 1y = 1 x = 0 1  0x = 1 y = 0y = 0 x = 1

일반적인 AND 게이트는 가역적이지 않다. 입력 00, 01, 10이 모두 출력 0에 매핑되기 때문이다.

 입력  출력조건 (1) 00  0x not unique for y = 0 01  0x not unique for y = 0100x not unique for y = 0111x = 11 y = 1

가역 게이트는 1960년대부터 연구되어 왔다. 원래의 동기는 가역 게이트가 열을 덜 소산시키기 (또는 원칙적으로 열을 전혀 소산시키지 않기) 때문이었다.

최근의 동기는 양자 컴퓨팅에서 비롯된다. 양자역학에서 양자 상태는 두 가지 방식으로 진화할 수 있다: 슈뢰딩거 방정식(유니터리 변환)에 의해서, 또는 파동함수 붕괴에 의해서. 토폴리 게이트가 그 예인 양자 컴퓨터를 위한 논리 연산은 유니터리 변환이므로 가역적으로 진화한다.

 하드웨어 설명 
하드웨어 기술 언어 베릴로그로 구현된 고전 토폴리 게이트:
module toffoli_gate (
 input u1, input u2, input in,
 output v1, output v2, output out);
always @(*) begin
    v1 = u1;
    v2 = u2;
    out = in ^ (u1 && u2);
end
endmodule

 보편성과 토폴리 게이트 
입력을 소비하고 모든 입력 계산을 허용하는 모든 가역 게이트는 비둘기집 원리에 따라 출력 비트보다 많은 입력 비트를 가질 수 없다. 하나의 입력 비트에 대해 두 가지 가능한 가역 게이트가 있다. 그중 하나는 NOT이다. 다른 하나는 입력을 변경되지 않은 채 출력으로 매핑하는 항등 게이트이다. 두 개의 입력 비트에 대해 유일하게 비자명한 게이트(대칭까지)는 제어된 NOT 게이트(CNOT)로, 첫 번째 비트를 두 번째 비트에 XOR하고 첫 번째 비트는 변경되지 않은 채로 둔다.

 진리표  치환행렬 형태 입력 출력 0  0  0  0 0  1  0  1 1  0  1  1 1  1  1  0

불행히도, 이러한 게이트만으로는 계산할 수 없는 가역 함수들이 있다. 예를 들어, AND는 이러한 게이트로는 구현할 수 없다. 다시 말해, NOT과 XOR 게이트로 구성된 집합은 완전하지 않다. 가역 게이트를 사용하여 임의의 함수를 계산하기 위해서는 1980년 토폴리가 제안한 토폴리 게이트가 실제로 그 목표를 달성할 수 있다.Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: 이는 비트 {a, b, c}를 {a, b, c XOR (a AND b)}로 매핑하는 것으로도 설명할 수 있다. 이것은 종종 {a, b, c} → {a, b, c ⨁ ab}로 쓰이는 비트 c에 대한 모듈러 연산으로도 이해할 수 있다.

토폴리 게이트는 보편적이다. 이는 임의의 불 함수 f(x1, x2, ..., xm)에 대해, x1, x2, ..., xm과 0 또는 1로 설정된 일부 추가 비트를 입력으로 받아 x1, x2, ..., xm, f(x1, x2, ..., xm) 및 일부 추가 비트(가비지라고 불림)를 출력하는 토폴리 게이트로 구성된 회로가 존재한다는 의미이다. 예를 들어, NOT 게이트는 세 개의 입력 비트를 {a, 1, 1}로 설정하여 세 번째 출력 비트가 (1 XOR (a AND 1)) = NOT a가 되도록 토폴리 게이트로 구성할 수 있다. (a AND b)는 {a, b, 0}에서 세 번째 출력 비트이다. 본질적으로 이것은 토폴리 게이트를 사용하여 원하는 불 함수 계산을 가역적인 방식으로 수행하는 시스템을 구축할 수 있음을 의미한다.

 관련 논리 게이트 

섬네일|126x126px|프레드킨 게이트
섬네일|405x405px|토폴리 게이트는 단일 큐비트 T 및 하디마르 게이트와 최소 6개의 CNOT로 구성할 수 있다.
 프레드킨 게이트는 첫 번째 비트가 1일 경우 마지막 두 비트를 교환하는 보편적인 가역 3비트 게이트이다. 즉, 제어 스왑 연산이다.
 n-비트 토폴리 게이트는 토폴리 게이트의 일반화이다. n개의 비트 x1, x2, ..., xn을 입력으로 받고 n개의 비트를 출력한다. 처음 n − 1개의 출력 비트는 x1, ..., xn−1과 같다. 마지막 출력 비트는 (x1 AND ... AND xn−1) XOR xn이다.
 토폴리 게이트는 5개의 2-큐비트 양자 게이트로 구현될 수 있지만, 5개 미만을 사용해서는 불가능하다는 것이 증명되었다.
 또 다른 보편 게이트인 도이치 게이트는 중성 원자를 사용하여 5개의 광학 펄스로 구현될 수 있다. 도이치 게이트는 양자 컴퓨팅을 위한 보편적인 게이트이다.
 노먼 마골루스의 이름을 딴 마골루스 게이트는 토폴리 게이트와 매우 유사하지만 대각선에 -1을 포함한다: RCCX = diag(1, 1, 1, 1, 1, -1, X). 마골루스 게이트는 가역 회로에도 보편적이며 토폴리 게이트와 매우 유사하게 작동하며, 토폴리 게이트에 비해 CNOT의 절반 정도로 구성될 수 있다는 장점이 있다.
 iToffoli 게이트는 쌍별 결합을 가진 초전도 큐비트에서 비가환 연산을 동시에 적용하여 구현되었다.

 양자 컴퓨팅과의 관계 
모든 가역 게이트는 양자 컴퓨터에 구현될 수 있으므로 토폴리 게이트 또한 양자 연산자이다. 그러나 토폴리 게이트는 보편적인 양자 계산에는 사용될 수 없지만, 양자 컴퓨터가 가능한 모든 고전 계산을 구현할 수 있음을 의미한다. 토폴리 게이트는 양자 계산에 보편적이기 위해서는 본질적으로 양자적인 게이트(들)와 함께 구현되어야 한다. 특히 비자명한 양자 상태를 생성할 수 있는 실수 계수를 가진 모든 단일 큐비트 게이트로 충분하다.

양자역학에 기반한 토폴리 게이트는 2009년 1월 오스트리아 인스부르크 대학에서 성공적으로 구현되었다. 회로 모델에서 n-큐비트 토폴리 구현은  CNOT 게이트를 필요로 하지만, 가장 잘 알려진 상한은  CNOT 게이트이다. 포획 이온 양자 컴퓨터가 n-큐비트 토폴리 게이트를 직접 구현할 수 있다고 제안되었다. 다체 상호작용의 적용은 포획 이온, 리드베리 원자, 초전도 회로 구현에서 게이트의 직접 작동에 사용될 수 있다. 암흑 상태 매니폴드를 따라가는 Khazali-Mølmer Cn-NOT 게이트는 회로 모델 패러다임을 벗어나 단 세 개의 펄스로 작동한다. iToffoli 게이트는 쌍별 결합을 가진 세 개의 초전도 큐비트를 사용하여 단일 단계로 구현되었다.

 같이 보기 
 제어된 NOT 게이트
 프레드킨 게이트
 가역 컴퓨팅
 전단사 함수
 양자 컴퓨팅
 양자 논리 게이트
 양자 프로그래밍
 단열 논리

 각주 

 외부 링크 
 CNOT 및 토폴리 게이트의 다중 큐비트 설정 - 울프럼 데몬스트레이션 프로젝트.

분류:논리 게이트
분류:이탈리아의 발명품