토폴리 게이트

논리 회로에서 1980년 토마소 토폴리가 발명한^[1] 토폴리 게이트(영어: Toffoli gate)는 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	${\displaystyle {\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\\\end{bmatrix}}}$

배경

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

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

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

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

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

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

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

하드웨어 설명

하드웨어 기술 언어 베릴로그로 구현된 고전 토폴리 게이트:

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	${\displaystyle {\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\\end{bmatrix}}}$

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

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

관련 논리 게이트

 양자 논리 게이트 목록 문서에 이 부분의 추가 정보가 있습니다.

프레드킨 게이트

토폴리 게이트는 단일 큐비트 T 및 하디마르 게이트와 최소 6개의 CNOT로 구성할 수 있다.

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

양자 컴퓨팅과의 관계

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

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

같이 보기

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