본문으로 이동

토폴리 게이트

위키백과, 우리 모두의 백과사전.

논리 회로에서 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

배경

[편집]

입력을 소비하는 논리 게이트 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

불행히도, 이러한 게이트만으로는 계산할 수 없는 가역 함수들이 있다. 예를 들어, 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(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-큐비트 양자 게이트로 구현될 수 있지만,[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-큐비트 토폴리 구현은 CNOT 게이트를 필요로 하지만,[13] 가장 잘 알려진 상한은 CNOT 게이트이다.[14] 포획 이온 양자 컴퓨터가 n-큐비트 토폴리 게이트를 직접 구현할 수 있다고 제안되었다.[15] 다체 상호작용의 적용은 포획 이온, 리드베리 원자, 초전도 회로 구현에서 게이트의 직접 작동에 사용될 수 있다.[16][17][18][19][20][21] 암흑 상태 매니폴드를 따라가는 Khazali-Mølmer Cn-NOT 게이트[17]는 회로 모델 패러다임을 벗어나 단 세 개의 펄스로 작동한다. iToffoli 게이트는 쌍별 결합을 가진 세 개의 초전도 큐비트를 사용하여 단일 단계로 구현되었다.[22]

같이 보기

[편집]

각주

[편집]
  1. ↑ 가 나 Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: Toffoli, Tommaso (1980). J. W. de Bakker and J. van Leeuwen (편집). 《Reversible computing》 (PDF). Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. 632–644쪽. doi:10.1007/3-540-10003-2_104. ISBN 3-540-10003-2. 2010년 4월 15일에 원본 문서 (PDF)에서 보존된 문서. 
  2. ↑ Landauer, R. (July 1961). 《Irreversibility and Heat Generation in the Computing Process》. 《IBM Journal of Research and Development》 5. 183–191쪽. doi:10.1147/rd.53.0183. ISSN 0018-8646. 
  3. ↑ Colin P. Williams (2011). 《Explorations in Quantum Computing》. 슈프링어. 25–29,61쪽. ISBN 978-1-84628-887-6. 
  4. ↑ Nielsen, Michael L.; Chuang, Isaac L. (2010). 《Quantum Computation and Quantum Information》 10판. Cambridge University Press. 29쪽. ISBN 9781107002173. 
  5. ↑ Barenco, Adriano; Bennett, Charles H.; Cleve, Richard; DiVincenzo, David P.; Margolus, Norman; Shor, Peter; Sleator, Tycho; Smolin, John A.; Weinfurter, Harald (Nov 1995). 《Elementary gates for quantum computation》. 《Physical Review A》 52. 3457–3467쪽. arXiv:quant-ph/9503016. Bibcode:1995PhRvA..52.3457B. doi:10.1103/PhysRevA.52.3457. PMID 9912645. S2CID 8764584. 
  6. ↑ Yu, Nengkun; Duan, Runyao; Ying, Mingsheng (2013년 7월 30일). 《Five two-qubit gates are necessary for implementing the Toffoli gate》. 《Physical Review A》 88. 010304쪽. arXiv:1301.3372. Bibcode:2013PhRvA..88a0304Y. doi:10.1103/physreva.88.010304. ISSN 1050-2947. S2CID 55486826. 
  7. ↑ Shi, Xiao-Feng (May 2018). 《Deutsch, Toffoli, and CNOT Gates via Rydberg Blockade of Neutral Atoms》. 《Physical Review Applied》 9. 051001쪽. arXiv:1710.01859. Bibcode:2018PhRvP...9e1001S. doi:10.1103/PhysRevApplied.9.051001. S2CID 118909059. 
  8. ↑ Deutsch, D. (1989). 《Quantum Computational Networks》. 《Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences》 425. 73–90쪽. Bibcode:1989RSPSA.425...73D. doi:10.1098/rspa.1989.0099. ISSN 0080-4630. JSTOR 2398494. S2CID 123073680. 
  9. ↑ Maslov, Dmitri (2016년 2월 10일). 《Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization》 (영어). 《Physical Review A》 93. 022311쪽. arXiv:1508.03273. Bibcode:2016PhRvA..93b2311M. doi:10.1103/PhysRevA.93.022311. ISSN 2469-9926. 
  10. ↑ Kim, Y.; Morvan, A.; Nguyen, L.B.; Naik, R.K.; Jünger, C.; Chen, L.; Kreikebaum, J.M.; Santiago, D.I.; Siddiqi, I. (2022년 5월 2일). 《High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits》. 《Nature Physics》 18. 783–788쪽. arXiv:2108.10288. Bibcode:2022NatPh..18..783K. doi:10.1038/s41567-022-01590-3. 
  11. ↑ Shi, Yaoyun (Jan 2003). 《Both Toffoli and Controlled-NOT need little help to do universal quantum computation》. 《Quantum Information & Computation》 3. 84–92쪽. arXiv:quant-ph/0205115. Bibcode:2002quant.ph..5115S. doi:10.26421/QIC3.1-7. 
  12. ↑ Monz, T.; Kim, K.; Hänsel, W.; Riebe, M.; Villar, A. S.; Schindler, P.; Chwalla, M.; Hennrich, M.; Blatt, R. (Jan 2009). 《Realization of the Quantum Toffoli Gate with Trapped Ions》. 《Physical Review Letters》 102. 040501쪽. arXiv:0804.0082. Bibcode:2009PhRvL.102d0501M. doi:10.1103/PhysRevLett.102.040501. PMID 19257408. S2CID 2051775. 
  13. ↑ Shende, Vivek V.; Markov, Igor L. (2008년 3월 15일). “On the CNOT-cost of TOFFOLI gates”. arXiv:0803.2316 [quant-ph]. 
  14. ↑ Maslov, Dmitri (2016). 《Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization》. 《Physical Review A》 93. 022311쪽. arXiv:1508.03273. Bibcode:2016PhRvA..93b2311M. doi:10.1103/PhysRevA.93.022311. S2CID 5226873. 
  15. ↑ Katz, Or; Marko; Monroe, Christopher (2022년 2월 8일). 《 -Body Interactions between Trapped Ion Qubits via Spin-Dependent Squeezing》. 《Physical Review Letters》 129. 063603쪽. arXiv:2202.04230. Bibcode:2022PhRvL.129f3603K. doi:10.1103/PhysRevLett.129.063603. PMID 36018637. S2CID 246679905. 
  16. ↑ Arias Espinoza, Juan Diego; Groenland, Koen; Mazzanti, Matteo; Schoutens, Kareljan; Gerritsma, Rene (2021년 5월 28일). 《High-fidelity method for a single-step N-bit Toffoli gate in trapped ions》. 《Physical Review A》 103. 052437쪽. arXiv:2010.08490. Bibcode:2021PhRvA.103e2437E. doi:10.1103/PhysRevA.103.052437. S2CID 223953418. 
  17. ↑ 가 나 Khazali, Mohammadsadegh; Mølmer, Klaus (2020년 6월 11일). 《Fast Multiqubit Gates by Adiabatic Evolution in Interacting Excited-State Manifolds of Rydberg Atoms and Superconducting Circuits》 (영어). 《Physical Review X》 10. 021054쪽. arXiv:2006.07035. Bibcode:2020PhRvX..10b1054K. doi:10.1103/PhysRevX.10.021054. ISSN 2160-3308. 
  18. ↑ Isenhower, L.; M.; Mølmer, K. (2011년 9월 4일). 《Multibit CkNOT quantum gates via Rydberg blockade》 (영어). 《Quantum Information Processing》 10. 755쪽. arXiv:1104.3916. doi:10.1007/s11128-011-0292-4. ISSN 1573-1332. S2CID 28732092. 
  19. ↑ Rasmussen, S. E.; Groenland, K.; Gerritsma, R.; Schoutens, K.; Zinner, N. T. (2020년 2월 7일). 《Single-step implementation of high-fidelity n -bit Toffoli gates》. 《Physical Review A》 101. 022308쪽. arXiv:1910.07548. Bibcode:2020PhRvA.101b2308R. doi:10.1103/physreva.101.022308. ISSN 2469-9926. S2CID 204744044. 
  20. ↑ Nguyen, L.B.; Kim, Y.; Hashim, A.; Goss, N.; Marinelli, B.; Bhandari, B.; Das, D.; Naik, R.K.; Kreikebaum, J.M.; Jordan, A.; Santiago, D.I.; Siddiqi, I. (2024년 1월 16일). 《Programmable Heisenberg interactions between Floquet qubits》. 《Nature Physics》 20. 240–246쪽. arXiv:2211.10383. Bibcode:2024NatPh..20..240N. doi:10.1038/s41567-023-02326-7. 
  21. ↑ Nguyen, Long B.; Goss, Noah; Siva, Karthik; Kim, Yosep; Younis, Ed; Qing, Bingcheng; Hashim, Akel; Santiago, David I.; Siddiqi, Irfan (2024). 《Empowering a qudit-based quantum processor by traversing the dual bosonic ladder》. 《Nature Communications》 15. 7117쪽. arXiv:2312.17741. Bibcode:2024NatCo..15.7117N. doi:10.1038/s41467-024-51434-2. PMC 11333499 |pmc= 값 확인 필요 (도움말). PMID 39160166. 
  22. ↑ Kim, Y.; Morvan, A.; Nguyen, L.B.; Naik, R.K.; Jünger, C.; Chen, L.; Kreikebaum, J.M.; Santiago, D.I.; Siddiqi, I. (2022년 5월 2일). 《High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits》. 《Nature Physics》 18. 783–788쪽. arXiv:2108.10288. Bibcode:2022NatPh..18..783K. doi:10.1038/s41567-022-01590-3. 

외부 링크

[편집]
원본 주소 "https://ko.wikipedia.org/w/index.php?title=토폴리_게이트&oldid=40376011"