A Multilevel Framework for Partitioning Quantum Circuits

기술 요약: 양자 회로 분할을 위한 다층 프레임워크 (A Multilevel Framework for Partitioning Quantum Circuits)

문제 정의
분산 양자 컴퓨팅(Distributed Quantum Computing, DQC)은 여러 양자 처리 장치(QPU)를 얽힘(entanglement)으로 연결함으로써 확장 가능한 양자 시스템으로 가는 경로를 제시한다. 그러나 이러한 분산 노드에 걸쳐 양자 알고리즘을 실행하는 것은 상당한 오버헤드를 발생시킨다. 나이브한 방식의 QPU 매핑은 높은 통신 비용, 구체적으로는 얽힌 쌍(e-bit)의 소비, 실행 시간 증가, 그리고 노이즈 심화를 초래한다. 핵심 과제는 논리 큐비트를 QPU에 최적으로 할당하고, 비로컬 연산(서로 다른 QPU에 거주하는 큐비트 간의 게이트 동작)을 처리하기 위한 가장 효율적인 방법을 결정하는 것이다. 기존 방법들이 이를 다루고 있으나, 텔레포테이션(teleportation)의 모든 가능성을 포착하지 못하거나, 특히 회로 크기와 네트워크 규모가 증가함에 따라 발생하는 NP-난해(NP-hard) 최적화 문제 해결에 어려움을 겪는다.

방법론
저자들은 양자 회로 분할을 하이퍼그래프 분할 문제로 정식화한 종합적인 다층 프레임워크를 제안한다. 워크플로우는 다음과 같은 몇 가지 별도의 단계로 구성된다:

1. 그래프 구축 및 게이트 그룹화:

   • 회로는 특정 게이트 세트($U(\theta, \phi, \lambda)$ 및 $CP(\theta)$)로 트랜스파일된 후, 큐비트가 특정 타임스텝에서의 노드로 표현되는 시간적으로 확장된 그래프(temporally extended graph)로 변환된다.
   • 이 그래프는 다중 게이트 텔레포테이션을 위한 "호환성"을 기준으로 게이트를 그룹화함으로써 하이퍼그래프로 일반화된다. 두 큐비트 게이트가 공통의 제어 큐비트를 공유하고, 연속적이며, 제어 큐비트 상에서 비대각 단일 큐비트 게이트에 의해 방해받지 않는 경우 하나의 그룹이 형성된다.
   • 본 프레임워크는 **중첩 상태 텔레포테이션(nested state teleportation)**이라는 새로운 프로토콜을 도입하며, 이는 게이트 텔레포테이션 절차를 부분적으로 상태 텔레포테이션으로 붕괴시키는 방식이다. 이를 통해 시스템은 다중 게이트 텔레포테이션 절차의 "종료 프로세스(ending process)"를 재지정함으로써 상태 텔레포테이션과 게이트 텔레포테이션 사이를 동적으로 선택할 수 있다.

2. 목적 함수:

   • e-bit 소요량을 최소화하도록 설계된 고유한 비용 함수를 사용한다. 하이퍼 엣지의 비용은 루트 세트(root set)에 의해 설명되지 않는 수신자 세트(receiver set)가 가로지르는 파티션의 수로 정의된다(효과적으로 새로운 얽힘 자원을 필요로 하는 컷(cut)을 계산함).
   • 목적은 모든 엣지에 대한 이러한 비용의 합을 최소화하는 것이다: $\min_{\Phi} \sum_{e \in E} c_e(\Phi)$.

3. 분할 알고리즘 (적응형 FM):

   • 잘 알려진 피두시아-매티시스(Fiduccia-Mattheyses, FM) 휴리스틱을 시간적 하이퍼그래프 구조와 특정 균형 제약 조건(각 타임스텝당 큐비트 용량)을 처리할 수 있도록 적응시켰다.
   • 효율성을 보장하기 위해, 저자들은 가능한 모든 하이퍼 엣지 구성에 대한 비용을 사전 계산하고, 상수 시간 내에 "델타 이득(delta gains)"을 계산하기 위해 보조 데이터 구조(루트/수신자 카운트)를 사용한다.
   • 정적 초기 할당에 내재된 지역 최적점(local minima)을 벗어나기 위해, 저자들은 최적의 누적 이득으로 되돌아가지 않는 **탐색적 패스(exploratory passes)**를 도입하여, 더 나은 전역 최적점에 도달하기 위해 일시적으로 비용이 증가하는 이동 시퀀스를 통과할 수 있도록 한다.

4. 다층 프레임워크:

   • 최첨단 그래프 분할기(예: METIS, KaHyPar)에서 영감을 얻은 본 프레임워크는 **시간적 응축(temporal coarsening)**을 채택한다. 무작위 노드 병합 대신, 타임스텝을 병합한다(윈도우, 블록 또는 재귀적 응축).
   • 과정은 다음과 같다:
     • 응축(Coarsening): 더 작고 거친 하이퍼그래프를 만들기 위해 시간적 해상도를 낮춘다.
     • 분할(Partitioning): 가장 거친 그래프에서 분할 문제를 해결한다.
     • 역응축 및 정교화(Uncoarsening and Refinement): 이전 레벨의 솔루션을 시작점으로 사용하여 시간적 해상도를 점진적으로 복구하고, 각 레벨에서 FM 정교화를 적용한다.
   • 재귀적 응축(recursive coarsening) 전략(인접한 타임스텝 병합)이 가장 효과적인 것으로 확인되었으며, 레벨 수에 대해 로그 스케일링을 제공한다.

5. 회로 추출:

   • 최종 분할된 그래프는 다시 분산 양자 회로로 변환된다. 여기에는 얽힘 생성 스케줄링, 텔레포테이션의 시작 및 종료 프로세스 관리, 통신 큐비트 자원 관리가 포함된다.

주요 기여

• 중첩 상태 텔레포테이션의 정식화: 본 논문은 상태, 게이트 및 중첩 상태 텔레포테이션을 종료 프로세스의 방향에 따라 결정되는 동일한 절차의 변형으로 취급하는 통합된 관점을 도입한다. 이는 얽힘 비용 최적화를 위한 설계 공간을 확장한다.
• 다층 시간적 분할: 양자 회로의 시간적 구조에 맞게 다층 기법을 적용하여, 다양한 입도(granularity)에서 문제를 해결함으로써 솔루션 품질과 실행 시간을 모두 개선한다.
• 적응형 FM 휴리스틱: DQC의 특정 비용 함수와 균형 제약을 효율적으로 처리하며, 탐색적 패스를 통해 지역 최적점을 피하는 메커니즘을 갖춘 수정된 피두시아-매티시스 알고리즘을 제공한다.
• 오픈 소스 구현: 본 프레임워크는 disqco 저장소에 구현되어 재현 가능한 분산 양자 회로 컴파일 도구를 제공한다.

결과
본 프레임워크는 Pytket-DQC(Partition, PartitionEmbed, EmbedSteinerDetached 워크플로우 사용) 및 미세 조정 분할(Fine-Grained Partitioning, FGP-rOEE) 방식을 포함한 최첨단 방법들과 벤치마크를 수행하였다.

• 얽힘 감소: 다양한 유형의 회로(CP-fraction, QFT, QAOA, Quantum Volume, QASM 벤치마크)에 걸쳐, 제안된 다층 프레임워크(특히 재귀적 변형인 MLFM-R)는 대부분의 경우에서 가장 낮은 얽힘 비용을 달성했다.
• 정량적 개선: 본 프레임워크는 차순위 성능을 보인 방법과 비교했을 때 평균적으로 얽힘 요구량을 35% 감소시켰다.
• 확장성: 다층 접근 방식은 표준 FM에 비해 실행 시간을 크게 단축시켰으며, 파티션 수가 과도하게 많지 않은 경우 경쟁 방법들보다 훨씬 큰 규모의 회로(수백 개의 큐비트)를 분할할 수 있게 해주었다.
• 트레이드오프: 게이트 그룹화(다중 게이트 텔레포테이션)는 회로 깊이를 크게 줄였으나 통신 큐비트에 대한 수요를 높였다. 본 프레임워크는 사용자가 가용 하드웨어 자원에 따라 이 트레이드오프를 조정할 수 있도록 한다.

의의 및 주장
본 논문은 제안된 다층 프레임워크가 분산 양자 회로 컴파일의 중요한 진전임을 주장한다. 다양한 텔레포테이션 프로토콜(상태, 게이트, 중첩 상태)을 단일 최적화 목적 함수 내로 통합하고 다층 그래프 분할 기술을 활용함으로써, 얽힘 오버헤드(DQC의 주요 병목 현상)를 실질적으로 최소화할 수 있음을 입증하였다.

저자들은 현재의 작업이 모든-대-모든(all-to-all) 연결성을 가정하고 20개 미만의 QPU 네트워크에 집중하고 있지만, 핵심 기술은 확장 가능하도록 설계되었다고 강조한다. 그들은 이 프레임워크가 대규모의 노이즈가 있고 제약이 있는 양자 네트워크를 처리할 수 있는, 미래의 분산 양자 컴퓨팅 컴파일러 스택을 위한 견고한 토대를 제공한다고 주장한다. 본 연구는 얽힘 최소화를 위한 최적화가 단순한 이론적 연습이 아니라, 근미래 및 미래의 하드웨어에서 분산 양자 알고리즘을 실현 가능하게 만들기 위한 실질적인 필수 사항임을 강조한다.