Witnessing the architecture of quantum circuits

양자 설계도 퍼즐

당신은 복잡한 기계, 예를 들어 로봇을 만들려고 노력하고 있다고 상상해 보십시오. 하지만 당신은 오직 특정한, 제한된 세트의 레고 브릭만을 사용할 수 있습니다. 아마도 당신에게는 빨간색 2x4 브릭과 파란색 1x2 브릭만 있고, 바퀴나 특수 커넥터는 사용하는 것이 금지되어 있을 수도 있습니다. 양자 컴퓨팅의 세계에서 이 "브릭"들은 **양자 게이트(quantum gates)**라고 불리며, "기계"는 계산을 수행하는 **양자 회로(quantum circuit)**입니다. 당신이 가진 브릭의 종류와 그것들을 어떻게 연결할 수 있는지에 대한 게임의 규칙을 **회로 아키텍처(circuit architecture)**라고 부릅니다.

때때로, 당신은 매우 구체적인 부품들을 필요로 하는 아주 복잡하고 정교한 로봇(하나의 유니터리 변환(unitary transformation))을 만들고 싶어 합니다. 여기서 핵심적인 질문은 이것입니다: 내가 가진 브릭들만 사용하여 이 정확한 로봇을 만들 수 있는가? 만약 당신이 시도했다가 실패한다면, 그것은 단순히 당신이 조립을 못 하는 것일 수도 있습니다. 하지만 만약 그것이 실제로 불가능한 일이라면 어떨까요? 만약 물리 법칙이 당신이 가진 브릭 상자로는 결코 그 로봇을 만들 수 없다고 단언한다면 어떨까요? 이것이 바로 **부적합성(incompatibility)**의 문제입니다. 과학자들은 어떤 작업이 주어진 규칙 아래에서 불가능하다는 것을 100% 확신을 가지고 증명할 수 있는 방법이 필요합니다. 이는 단순히 시간을 아끼는 문제가 아닙니다. 우리가 설계하기도 전에 우리의 양자 컴퓨터가 실제로 무엇을 할 수 있는지에 대한 근본적인 한계를 아는 것에 관한 문제입니다.

---

"불가능" 탐지기

라파엘 모트(Raphaël Mothe)와 오트프리드 귀네(Otfried Gühne)는 새로운 연구를 통해 **양자 회로 아키텍처 위트니스(quantum circuit architecture witness)**라는 영리한 수학적 도구를 발명했습니다. 이 위트니스를 생각할 때, 이것은 매우 똑똑한 "불가능 탐지기"와 같습니다. 로봇을 직접 만들어 보고 실패하는 대신, 이 도구는 로봇의 설계도와 당신이 사용할 수 있는 브릭 목록을 살펴보고 즉시 이렇게 말해줍니다. "아뇨, 당신은 그 부품들로 이것을 만들 수 없습니다."

보통 과학자들이 양자 회로를 어떻게 구축할지 고민할 때, 그들은 미로를 통과하며 길을 찾는 것과 같은 방법을 사용합니다. 그들은 기계를 작동시키는 방법을 찾을 때까지 다양한 경로를 계속 시도합니다. 만약 길을 찾지 못한다면, 그들은 단순히 막다른 길에 갇힌 것일 수도 있고, 혹은 더 열심히 노력해야 하는 상황일 수도 있습니다. 그들은 출구가 벽 뒤에 숨겨져 있는지조차 알지 못합니다. 모트와 귀네의 접근 방식은 이 흐름을 뒤집습니다. 그들은 회로를 구축하려고 시도하는 대신, 그 회로가 존재할 수 없음을 증명하려고 노력합니다.

탐정이 작동하는 방식: "초이(Choi)" 거울

이를 위해 저자들은 **초이 상태(Choi state)**라고 불리는 수학적 트릭을 사용합니다. 당신이 양자 게이트(계산의 단일 단계)를 거울에 비추었을 때, 그것이 기계로서가 아니라 특별한 종류의 "지문"이나 독특한 빛의 패턴으로 반사되는 마법 거울을 상상해 보십시오. 당신이 전체 회로를 가지게 되면, 이 거울은 모든 게이트가 함께 작동하는 결합된 지문을 보여줍니다.

저자들의 방법은 "대상 로봇"(당신이 만들고자 하는 유니터리)의 지문과 당신의 특정 브릭들로 만들 수 있는 모든 가능한 로봇의 지문을 비교합니다. 그들은 **충실도(fidelity)**라고 불리는 점수를 계산하는데, 이는 유사성 백분율과 같습니다. 만약 점수가 100%라면, 대상 로봇은 당신의 브릭들과 호환됩니다. 만약 점수가 100% 미만이라면, 당신의 브릭들이 그 작업에 근본적으로 잘못되었다는 것을 의미합니다.

그들의 "위트니스"의 천재성은 수학적인 선을 긋는다는 점에 있습니다. 만약 유사성 점수가 특정 지점 아래로 떨어지면, 위트니스는 "부적합!"이라고 외칩니다. 이것은 과학자들에게 "그만 시도하십시오. 이 특정 양자 작업은 이 특정 회로 레이아웃으로는 수행될 수 없습니다"라는 엄격한 인증서를 제공합니다.

수학적 마법: 어려운 것을 쉽게 만들기

저자들은 모든 게이트의 조합을 확인하는 것이, 계속해서 커지는 건초더미 속에서 바늘을 찾는 것처럼 믿을 수 없을 정도로 어렵다는 것을 깨달았습니다. 이 문제를 해결하기 위해, 그들은 이 문제를 **반정부호 계획법(Semidefinite Program, SDP)**으로 전환했습니다. 이것을 지치지 않는 로봇을 사용하여 건초더미를 분류하는 매우 조직적인 방법이라고 생각할 수 있습니다.

하지만, 게이트가 매우 많은 매우 복잡한 회로의 경우, 이 로봇조차도 압도당합니다. 그래서 저자들은 **클리포드 게이트(Clifford gates)**라고 불리는 특정 유형의 양자 게이트를 위한 특별한 지름길을 찾아냈습니다. 클리포드 게이트는 양자 컴퓨터가 특히 오류를 수정할 때 많이 사용하는 "쉬운" 게이트들입니다. 이 게이트들의 경우, 저자들은 이 문제가 **선형 계획법(Linear Programming, LP)**으로 단순화될 수 있음을 보여주었습니다. 이것은 3D 미로를 2D 지도로 만드는 것과 같습니다. 이는 계산을 훨씬 빠르게 만들어 주어, 그들이 최대 7개의 2-큐비트 게이트(두 개의 양자 비트를 연결하는 게이트)를 가진 회로를 효율적으로 확인할 수 있게 해줍니다.

그들이 발견한 것: 토폴리 게이트의 한계

팀은 새로운 탐지기를 몇 가지 유명한 양자 퍼즐에 테스트했습니다. 가장 유명한 것 중 하나는 토폴리 게이트(Toffoli gate)(CCNOT 게이트로도 알려짐)로, 이는 많은 양자 알고리즘에 필수적인 "삼중 스위치"와 같습니다.

• 두 개의 게이트 테스트: 그들은 "두 개의 2-큐비트 게이트만을 사용하여 토폴리 게이트를 만들 수 있는가?"라고 물었습니다. 그들의 위트니스는 아니오라고 답했습니다. 사실, 그들은 당신이 할 수 있는 최선의 결과가 약 **72.85%**의 유사도라는 것을 계산했습니다. 완벽한 일치를 위해서는 100%가 필요하므로, 이는 두 개의 게이트가 충분하지 않다는 것을 증명했습니다.
• 세 개의 게이트 테스트: 그들은 세 개의 게이트로 다시 시도했습니다. 위트니스는 여전히 아니오라고 답했으며, 유사성 한계는 약 **85.7%**였습니다.
• 결론: 다양한 배치를 체계적으로 테스트함으로써, 그들은 토폴리 게이트를 세 개의 큐비트 상에서 구축하려면 최소 4개의 게이트 층(또는 특정 깊이)이 필요함을 확인했습니다. 이는 다른 과학자들이 다른 방법을 통해 찾아낸 것과 일치하지만, 저자들의 방법은 왜 적은 자원으로는 불가능한지에 대한 직접적인 수학적 증명을 제공합니다.

그들은 또한 4개의 큐비트에 5개의 게이트가 있는 회로와 같은 다른 복잡한 설정들도 테스트했습니다. 한 사례에서, 그들은 특정 게이트 배열이 다른 배열과 완전히 호환되지 않는다는 것을 발견했는데, 유사성 점수는 불과 **50%**였습니다. 이는 두 회로 설계가 밤과 낮처럼 서로 다르며, 주어진 규칙으로는 하나를 다른 것으로 바꿀 수 없음을 의미합니다.

이것이 중요한 이유

이 프레임워크는 두 가지 주요 이유로 게임 체인저가 됩니다. 첫째, 이론가들에게는 자원에 대한 엄격한 하한선을 설정하는 방법을 제공합니다. 만약 어떤 작업에 최소 4개의 게이트 층이 필요하다는 것을 안다면, 당신은 3개 층의 솔루션을 설계하려고 시간을 낭비하지 않을 것입니다. 둘째, 실험가들에게는 벤치마크 역할을 합니다. 만약 어떤 과학자가 복잡한 작업을 수행할 수 있는 양자 장치를 만들었다고 주장한다면, 그들은 이 위트니스를 사용하여 자신의 장치가 진정으로 특별한 것, 즉 더 단순하고 표준적인 회로 아키텍처로는 결코 달성할 수 없는 일을 수행하고 있다는 것을 증명할 수 있습니다.

저자들은 자신들의 방법이 많은 경우, 특히 클리포드 게이트에서 아름답게 작동하지만, 여전히 열려 있는 질문들이 있다고 언급합니다. 그들은 이 분석적 접근 방식이 "쉬운" 게이트뿐만 아니라 모든 유형의 양자 회로로 확장될 수 있는지 궁금해합니다. 하지만 현재로서는, 그들은 양자 커뮤니티에 강력한 새로운 도구를 전달했습니다. 양자 설계도를 보고 절대적인 확신을 가지고 "이 설계는 이 부품들로는 불가능합니다"라고 말할 수 있는 도구 말입니다.