토폴리 게이트

논리 회로에서 1980년 토마소 토폴리가 발명한 **토폴리 게이트**(Toffoli gate)는 **CCNOT 게이트**("controlled-controlled-not")라고도 불리며, 두 개의 제어 비트와 하나의 대상 비트를 가진 CNOT 게이트이다. 즉, 첫 번째와 두 번째 비트가 모두 1일 경우 대상 비트(세 번째 비트)가 반전된다. 이는 모든 고전적 가역 회로를 토폴리 게이트로 구성할 수 있다는 의미에서 보편적인 가역 논리 게이트이다. 비트가 큐비트로 대체되는 양자 컴퓨팅 버전도 있다.
# 설명
진리표와 치환행렬은 다음과 같다(순환 표기법으로 (7,8)로 쓸 수 있다): {| |- | {| class="wikitable" | 입력 ! colspan="3" | 출력 |- | 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 |} | \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 게이트가 있다. {| class="wikitable" |- | 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에 매핑되기 때문이다. {| class="wikitable" |- | 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년대부터 연구되어 왔다. 원래의 동기는 가역 게이트가 열을 덜 소산시키기 (또는 원칙적으로 열을 전혀 소산시키지 않기) 때문이었다.issn=0018-8646 최근의 동기는 양자 컴퓨팅에서 비롯된다. 양자역학에서 양자 상태는 두 가지 방식으로 진화할 수 있다: 슈뢰딩거 방정식(유니터리 변환)에 의해서, 또는 파동함수 붕괴에 의해서. 토폴리 게이트가 그 예인 양자 컴퓨터를 위한 논리 연산은 유니터리 변환이므로 가역적으로 진화한다.pages=25–29,61
# 하드웨어 설명
하드웨어 기술 언어 베릴로그로 구현된 고전 토폴리 게이트: 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하고 첫 번째 비트는 변경되지 않은 채로 둔다. {| |- | {| class="wikitable" | 입력 ! colspan="2" | 출력 |- | 0 || 0 || 0 || 0 |- | 0 || 1 || 0 || 1 |- | 1 || 0 || 1 || 1 |- | 1 || 1 || 1 || 0 |} | \begin{bmatrix} 1 & 0 & 0 & 0 \\\ 0 & 1 & 0 & 0 \\\ 0 & 0 & 0 & 1 \\\ 0 & 0 & 1 & 0 \\\ \end{bmatrix} |} 불행히도, 이러한 게이트만으로는 계산할 수 없는 가역 함수들이 있다. 예를 들어, AND는 이러한 게이트로는 구현할 수 없다. 다시 말해, NOT과 XOR 게이트로 구성된 집합은 완전하지 않다. 가역 게이트를 사용하여 임의의 함수를 계산하기 위해서는 1980년 토폴리가 제안한 토폴리 게이트가 실제로 그 목표를 달성할 수 있다.Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: archivedate = 2010-04-15 이는 비트 {a, b, c}를 {a, b, c XOR (a AND b)}로 매핑하는 것으로도 설명할 수 있다. 이것은 종종 {a, b, c} → {a, b, c ⨁ ab}로 쓰이는 비트 c에 대한 모듈러 연산으로도 이해할 수 있다.pages=29 토폴리 게이트는 보편적이다. 이는 임의의 불 함수 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}에서 세 번째 출력 비트이다. 본질적으로 이것은 토폴리 게이트를 사용하여 원하는 불 함수 계산을 가역적인 방식으로 수행하는 시스템을 구축할 수 있음을 의미한다.
# 관련 논리 게이트
양자 논리 게이트 목록 프레드킨 게이트 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-큐비트 양자 게이트로 구현될 수 있지만, s2cid = 8764584 5개 미만을 사용해서는 불가능하다는 것이 증명되었다.issn=1050-2947 * 또 다른 보편 게이트인 도이치 게이트는 중성 원자를 사용하여 5개의 광학 펄스로 구현될 수 있다. s2cid = 118909059 도이치 게이트는 양자 컴퓨팅을 위한 보편적인 게이트이다.issn=0080-4630 * 노먼 마골루스의 이름을 딴 마골루스 게이트는 토폴리 게이트와 매우 유사하지만 대각선에 -1을 포함한다: RCCX = diag(1, 1, 1, 1, 1, -1, X). 마골루스 게이트는 가역 회로에도 보편적이며 토폴리 게이트와 매우 유사하게 작동하며, 토폴리 게이트에 비해 CNOT의 절반 정도로 구성될 수 있다는 장점이 있다.arxiv=1508.03273 * iToffoli 게이트는 쌍별 결합을 가진 초전도 큐비트에서 비가환 연산을 동시에 적용하여 구현되었다.arxiv=2108.10288
# 양자 컴퓨팅과의 관계
모든 가역 게이트는 양자 컴퓨터에 구현될 수 있으므로 토폴리 게이트 또한 양자 연산자이다. 그러나 토폴리 게이트는 보편적인 양자 계산에는 사용될 수 없지만, 양자 컴퓨터가 가능한 모든 고전 계산을 구현할 수 있음을 의미한다. 토폴리 게이트는 양자 계산에 보편적이기 위해서는 본질적으로 양자적인 게이트(들)와 함께 구현되어야 한다. 특히 비자명한 양자 상태를 생성할 수 있는 실수 계수를 가진 모든 단일 큐비트 게이트로 충분하다.bibcode = 2002quant.ph..5115S 양자역학에 기반한 토폴리 게이트는 2009년 1월 오스트리아 인스부르크 대학에서 성공적으로 구현되었다.s2cid = 2051775 회로 모델에서 n-큐비트 토폴리 구현은 2n CNOT 게이트를 필요로 하지만,date=2008-03-15 가장 잘 알려진 상한은 6n-12 CNOT 게이트이다.s2cid=5226873 포획 이온 양자 컴퓨터가 n-큐비트 토폴리 게이트를 직접 구현할 수 있다고 제안되었다.s2cid=246679905 다체 상호작용의 적용은 포획 이온, 리드베리 원자, 초전도 회로 구현에서 게이트의 직접 작동에 사용될 수 있다.s2cid = 223953418doi-access=frees2cid=28732092s2cid=204744044arxiv=2211.10383 bibcode=2024NatCo..15.7117N 암흑 상태 매니폴드를 따라가는 Khazali-Mølmer Cn-NOT 게이트는 회로 모델 패러다임을 벗어나 단 세 개의 펄스로 작동한다. iToffoli 게이트는 쌍별 결합을 가진 세 개의 초전도 큐비트를 사용하여 단일 단계로 구현되었다.arxiv=2108.10288