Efficient algorithms for quantum chemistry on modular quantum processors

이 논문은 의사 가환성(pseudo-commutativity)과 최적화된 모듈 간 게이트 스케줄링을 활용하여, 모듈 간 지연 시간에 대한 민감도를 최소화하면서도 모듈형 양자 프로세서에서 효율적인 화학적 정확도의 양자 화학 시뮬레이션을 가능하게 하는 분산 유니터리 선택적 결합 클러스터(dUSCC) 알고리즘을 소개한다.

핵심

거대한, 믿을 수 없을 정도로 복잡한 직소 퍼즐을 풀려고 노력 중이라고 상상해 보십시오. 양자 컴퓨팅의 세계에서 이 퍼즐은 거대 분자(약물이나 신소재 같은)의 정확한 거동을 파악하는 것입니다. 이 문제를 해결하려면 '큐비트'라고 불리는 수백만 개의 아주 작은 스위치가 있는 컴퓨터가 필요합니다.

문제는, 백만 개의 큐비트를 가진 하나의 거대한 기계를 만드는 것이 마치 커다란 유리 판 하나로 완벽한 백만 조각짜리 퍼즐 판을 만들려는 것과 같다는 점입니다. 그것은 너무 깨지기 쉽고, 비용이 많이 들며, 균열이 생길 가능성이 높습니다.

모듈형 솔루션: 퍼즐 해결사 팀
하나의 거대한 기계 대신, 저자들은 서로 대화하는 작은 컴퓨터들(모듈)의 팀을 구축할 것을 제안합니다. 이것은 세 명의 사람이 각자의 책상에 앉아 거대한 퍼즐의 서로 다른 구역을 풀고 있는 것과 같습니다.

• 좋은 소식: 같은 책상에 있는 사람들은 메모를 전달하고 퍼즐 조각을 즉시 주고받을 수 있습니다.
• 나쁜 소식: 다른 책상에 있는 사람에게 메모를 전달하는 데는 시간이 걸립니다. 연결이 더 느리고 완벽하지 않습니다.

도전 과제: "교통 체증"
만약 서로 다른 책상 사이의 퍼즐 조각을 끊임없이 교환해야 한다면, 팀은 느린 메모가 도착하기를 기다리느라 멈춰 서게 됩니다. 이 "대기 시간"(지연 시간)은 전체 프로젝트를 망칠 수 있으며, 모듈형 팀을 기존의 작은 단일 팀보다 더 느리게 만들 수 있습니다.

혁신: "dUSCC" 알고리즘
저자들은 dUSCC(distributed Unitary Selective Coupled Cluster)라고 불리는 새로운 작업 조직 방식을 만들었습니다. 그들은 단순히 퍼즐을 나누기만 한 것이 아니라, 느린 연결 관계를 고려하여 팀이 어떻게 움직여야 하는지를 알아냈습니다.

여기서 그들이 어떻게 수행했는지, 몇 가지 창의적인 비유를 들어 설명하겠습니다.

1. "의사 가환성(Pseudo-Commutativity)" 기술 (셔플하기)

양자 화학에서는 특정 단계를 수행하는 순서가 보통 중요합니다. 하지만 저자들은 이 특정 유형의 문제에 있어서는 순서가 최종 결과에 아주 결정적인 영향을 미치지는 않는다는 것을 발견했습니다. 이것은 카드 덱을 섞는 것과 같습니다. 결국 손에 넣게 될 카드가 무엇인지가 중요하다면, 카드를 집어 드는 정확한 순서는 결과적으로 손에 쥐게 될 카드 구성에 영향을 주지 않습니다.

순서가 엄격하게 중요하지 않기 때문에, 그들은 계산의 단계들을 재배치할 수 있습니다. 즉, "느린" 단계(책상 간의 메모가 필요한 단계)를 계산 일정의 다른 시점으로 옮겨도 수학적 오류를 일으키지 않고 실행할 수 있습니다.

2. "버퍼링" 전략 (대기실)

팀원들이 자신의 업무를 수행하는 동안 배달 트럭(즉, "벨 쌍(Bell pair)" 또는 연결)이 책상 사이를 느릿하게 달리고 있다고 상상해 보십시오.

• 기존 방식: 팀은 트럭이 도착할 때까지 일을 멈추고 기다립니다.
• 새로운 방식 (dUSCC): 팀은 트럭이 달리는 동안에도 자신들의 책상 업무를 계속 수행합니다. 그들은 다음 단계를 준비하기 위해 이 "대기실" 시간을 활용합니다.

저자들은 느린 장거리 작업이 발생하는 틈새 사이에 빠른 로컬 작업을 끼워 넣는 "패킹 스킴(packing scheme, 테트리스와 같은 방식)"을 설계했습니다. 그들은 본질적으로 느린 통신 시간을 빠른 로컬 계산 뒤로 숨깁니다.

3. "약한 연결 고리"의 발견

저자들은 수소 분자 사슬을 대상으로 테스트를 진행했습니다. 그들은 분자들이 (긴 사슬처럼) 배치되어 있어 "책상" 사이의 "연결"이 자연스럽게 약한 경우, 팀이 거의 기다릴 필요가 없다는 것을 발견했습니다.

• 결과: 그들은 책상 사이의 연결이 책상 내부에서 이루어지는 작업보다 35배나 더 느리더라도, 전체 문제를 해결하는 데 걸리는 총 시간은 늘어나지 않는다는 것을 보여주었습니다. 팀이 멀티태스킹을 매우 효율적으로 수행하기 때문에 느린 연결이 "공짜"처럼 느껴지게 된 것입니다.

4. "공짜 구역" 찾기

가장 멋진 부분 중 하나는, 어떤 분자가 이러한 "공짜" 팀워크에 적합한지 알아내기 위해 양자 컴퓨터를 사용할 필요가 없다는 점입니다. 일반적인 클래식 컴퓨터를 사용하여 먼저 분자의 구조를 살펴볼 수 있습니다. 만약 클래식 컴퓨터가 "책상" 사이의 연결이 약하다는 것을 감지하면, 다음과 같이 알려줍니다: "자, 모듈형 팀을 사용하십시오! 매우 빠를 것입니다."

요약

이 논문은 네트워크로 연결된 작은 컴퓨터들에서 양자 화학을 실행하기 위한 새로운 "사용 설명서"(알고리즘)를 제시합니다. 계산 단계를 재배치하고, 느린 연결을 기다리는 시간을 빠른 로컬 작업을 수행하는 데 활용함으로써, 그들은 다음을 증명했습니다:

1. 거대한 양자 문제를 여러 대의 기기에 나누어 할당하더라도 결과 속도가 저하되지 않습니다.
2. 많은 분자에서, 기계 사이의 느린 연결은 매우 잘 관리되어 계산에 추가적인 시간을 전혀 소요하지 않습니다.
3. 이 방식은 이러한 모듈형 지연을 고려하지 않는 표준 소프트웨어(예: Qiskit)를 사용하는 것보다 훨씬 빠릅습니다.

요컨대, 그들은 느리게 연결된 컴퓨터 팀이 화학적 퍼즐을 풀기 위해 단일한 초고속 컴퓨터처럼 효율적으로 작동하게 만드는 방법을 찾아냈습니다.

기술 요약

기술 요약: 모듈형 양자 프로세서를 위한 효율적인 양자 화학 알고리즘

문제 정의
양자 화학는 미래 양자 컴퓨터의 주요 타겟 응용 분야이지만, 유틸리티 규모의 문제를 해결하기 위한 리소스 추정치에 따르면 전체 잠재력을 실현하기 위해 수백만 개의 물리적 큐비트가 필요할 것으로 보입니다. 현재의 하드웨어 스케일링 로드맵은 이 규모에 도달하기 위해 단일 구조(monolithic) 프로세서에서, 대규모 양자 프로세서가 서로 연결된 다수의 모듈로 구성되는 모듈형 아키텍처로의 패러다임 전환이 필요함을 시사합니다. 이 전환 과정에서의 핵심 과제는 모듈 간 양자 인터커넥트가 모듈 내부 연산에 비해 일반적으로 충실도(fidelity)가 낮고 속도가 느리다는 점입니다. 본 연구가 다루는 중심 문제는 이러한 인터커넥트의 성능 요구 사항을 결정하고, 화학적 정확도를 희생하거나 실행 시간을 늘리지 않으면서 상당한 모듈 간 지연 시간(latency)을 견딜 수 있는 컴파일 전략을 개발하는 것입니다.

방법론
저자들은 모듈형 양자 프로세서에 특화되어 설계된 USCC 방법의 변형인 분산형 단위 선택 결합 클러스터(distributed Unitary Selective Coupled Cluster, dUSCC) 알고리즘을 소개합니다. 이 방법론은 세 가지 주요 구성 요소로 이루어집니다:

1. 알고리즘 선택: 저자들은 국소적 고전 솔루션(Direct Initialization 또는 Quantum Phase Estimation을 통해)과 변분 양자 고유값 솔버(VQE)를 결합한 USCC를 활용합니다. USCC는 에너지 구배($\partial E / \partial t_\beta \geq \epsilon$)를 기준으로 해밀토니안 항을 필터링하여, 회로 복잡도를 줄이기 위해 유의미한 호핑(hopping) 항만을 선택합니다. 이러한 선택 과정은 자연스럽게 장거리 상호작용을 걸러내며, 이는 모듈 분산에 매우 중요합니다.
2. 회로 컴파일 및 패킹: dUSCC 안사츠(ansatz)는 조던-위그너(Jordan-Wigner) 변환과 트로터화(Trotterization)를 사용하여 큐비트 회로로 컴파일됩니다. 저자들은 트로터화의 의사 가환성(pseudo-commutativity)—지수 항의 순서를 변경하더라도 트로터 오차의 차수가 변하지 않는 성질—을 활용하여 병렬성을 극대화합니다.
   • 회로는 "타일"(단일, 이중, 제어 호핑 항)로 분해됩니다.
   • **이중 패킹 휴리스틱(double-packing heuristic)**이 1+1D 타일 패킹 문제를 해결하기 위해 사용됩니다. 이 체계는 타일을 높이 순으로 정렬하고, 모듈 내부 병렬성을 극대화하도록 패킹합니다.
   • 결정적으로, 알고리즘은 모듈 간 벨 쌍(Bell pair)의 버퍼링을 고려하여 모듈 간 게이트를 스케줄링합니다. 모듈 간 타일은 지연 시간을 시뮬레이션하기 위해 추가적인 너비로 "마스킹"되며, 이를 통해 모듈 간 벨 쌍의 생성 및 버퍼링과 동시에 모듈 내부 연산이 실행될 수 있도록 합니다.
3. 하드웨어 모델: 본 연구는 로테이티드 표면 코드(rotated surface code)를 통해 논리 큐비트가 인코딩된 중성 원자 배열 플랫폼을 가정합니다. 모듈 간 연산은 격자 수술(lattice surgery)을 통해 수행되며, 이는 직렬로 생성되는 벨 쌍을 소비합니다. 저자들은 모듈 내 CNOT 게이트 대비 벨 쌍 생성의 지연 시간을 모델링합니다.

주요 기여

• dUSCC 알고리즘: 모듈 간 지연 시간과 트로터화된 알고리즘의 의사 가환성을 명시적으로 고려한 분산 컴파일 체계를 도입했습니다.
• 패킹 체계: 모듈 내부 계산과 벨 쌍 버퍼링 뒤로 통신 지연을 숨김으로써 모듈 간 게이트의 스케줄링을 최적화하는 새로운 탐욕적(greedy) 이중 패킹 알고리즘을 제시했습니다.
• 임계값 분석: 시스템이 약하게 얽혀 있는 경우, 모듈 간 지연 시간이 전체 회로 실행 시간을 증가시키지 않는 "무료 모듈화(free modularization)" 영역을 식별했습니다.
• 고전적 예측 가능성: 분자의 호핑 다이어그램을 분석함으로써 "무료" 모듈화 임계값의 존재 여부를 고전적 알고리즘을 통해 효율적으로 결정할 수 있음을 입증했습니다.

결과
저자들은 $(H_4)_3$ 체인(두 개의 $H_2$ 분자로 구성된 세 개의 클러스터)과 확장된 수소 체인에 대해 dUSCC를 시연했습니다:

• 지연 시간 허용 범위: $(H_4)_3$ 체인의 경우, 화학적 정확도($\sim 1.6$ mHa)를 유지하도록 선택 기준 $\epsilon$을 설정한다면, 모듈 간 게이트가 모듈 내 게이트보다 약 35배 느려지더라도 ($\tau \approx 35$) dUSCC 실행 시간은 변하지 않습니다.
• 얽힘 의존성: "무료" 모듈화 영역은 모듈 간 얽힘이 희소할 때만 존재합니다. 선택 기준 $\epsilon$이 엄격해질수록(더 낮은 값), 더 많은 장거리 모듈 간 호핑이 포함되어 강한 클러스터 간 얽힘으로 이어집니다. 이 "강하게 얽힌" 단계에서는 회로 시간이 모듈 간 지연 시간에 따라 선형적으로 증가합니다.
• 성능 이득: 분산 최적화 없이 (예: Qiskit을 사용하는) 단순 컴파일과 비교했을 때, dUSCC 컴파일은 $(H_4)_3$ 시스템에서 회로 시간을 최대 35배 단축합니다. 이 이점은 모듈의 수에 따라 선형적으로 확장됩니다.
• 일반화: 스틸벤(stilbene) 및 폴리엔(polyene) 분자에 대해서도 테스트를 진행하였으며, 특히 모듈 간 CNOT를 최소화하기 위해 큐비트 텔레포테이션 전략을 사용할 때 지연 비용이 감소하는 유사한 결과를 보여주었습니다.

의의 및 주장
본 논문은 많은 거대 분자들이 자연스럽게 약하지만 비자명한 연결성을 가진 클러스터들로 그룹화된다는 점에서, 모듈형 양자 아키텍처가 양자 화학에 독보적으로 적합하다고 주장합니다. 본 연구의 의의는 다음과 같습니다:

1. 모듈형 화학의 실현 가능성: 분자의 구조와 트로터화의 의사 가환성을 활용하도록 컴파일한다면, 인터커넥트가 모듈 내부 연산보다 훨씬 느린 모듈형 프로세서에서도 양자 화학을 효율적으로 수행할 수 있음을 입증했습니다.
2. 리소스 효율성: "무료" 모듈화 영역은 약하게 얽힌 시스템의 경우 계산을 분산시키는 오버헤드가 무시할 수 있는 수준임을 의미하며, 이는 모듈형 확장이 유틸리티 규모의 양자 화학을 향한 실행 가능한 경로임을 보여줍니다.
3. 컴파일 전략: 본 연구는 의사 가환성과 모듈 간 스케줄링을 활용하는 일반적인 컴파일 프레임워크를 제공하며, 이는 USCC를 넘어 다른 트로터화된 알고리즘에도 적용될 수 있습니다.

저자들은 dUSCC가 약하게 연결된 시스템에서 상당한 이점을 제공하지만, 모듈 간 통신이 모듈 내부 병렬성을 과도하게 포화시키는 매우 복잡하고 강하게 얽힌 분자에 대해서는 완전한 해법을 제공하지 못한다는 점을 언급하며 연구 범위를 신중하게 제한했습니다. 그러나 이 단계에서도 dUSCC가 비분산 방식에 비해 실행 시간 측면에서 우위를 점한다고 주장합니다.