기술 요약: MOSAIQC

문제 정의

현재의 양자 컴퓨터, 특히 NISQ(Noisy Intermediate-Scale Quantum) 시대의 장치들은 대부분의 실질적인 양자 알고리즘을 실행하는 데 필요한 큐비트 자원과 충실도(fidelity)가 부족하다. 이러한 하드웨어적 한계를 극복하기 위해, "양자 회로 커팅(quantum circuit cutting)" 또는 "회로 니팅(circuit knitting)" 기법이 대규모 알고리즘을 사용 가능한 하드웨어에서 실행 가능한 작은 파티션으로 나누는 방법으로 부상했다. 그러나 이 접근 방식은 정확한 상태 재구성을 위해 필요한 컷(cut)의 수에 따라 기하급수적으로 증가하는 **샘플링 오버헤드(sampling overhead)**를 발생시킨다.

컷 위치를 결정하기 위한 기존의 최적화 프레임워크들은 다음과 같은 몇 가지 중대한 한계점에 직면해 있다:

1. 확장성(Scalability): 정확한 방법들(예: 혼합 정수 계획법(MIP), SMT 솔버)은 종종 팩토리얼 또는 지수적 계산 복잡도를 보이며, 이는 수천 큐비트에 달하는 회로에 적용하기에는 불가능한 수준이다.
2. 컷 유형의 제한(Cut Type Limitations): 많은 휴리스틱은 와이어 컷(wire cuts) 또는 게이트 컷(gate cuts) 중 하나만을 단독으로 최적화하며, 이를 하나의 최적화 절차 내에서 결합하여 다루는 경우는 드물다.
3. 하드웨어 인식(Hardware Awareness): 대부분의 접근 방식은 균질한(homogeneous) 하드웨어 파티션을 가정하며, 이질적인(heterogeneous) 양자 백엔드의 구체적인 노이즈 특성과 연결성 제약을 간과하여 최적이 아닌 실행 충실도를 초래한다.
4. 트레이드오프(Trade-offs): 샘플링 오버헤드의 최소화와 하드웨어 충실도(노이즈 감소)의 최대화 사이의 균형을 맞추는 것은 복잡한 다목적 최적화 문제이며, 기존의 확장 가능한 휴리스틱들은 이를 공동으로 해결하지 못하는 경우가 많다.

방법론

본 논문은 샘플링 오버헤드, 하드웨어 인식 배치, 그리고 혼합 게이트/와이어 컷을 다항 시간 복잡도를 유지하면서 공동으로 최적화하도록 설계된 휴리스틱 최적화 프레임워크인 MosaiQC를 제시한다. 이 프레임워크는 계층적인 4단계 최적화 파이프라인을 통해 작동한다:

1. 그래프 표현 (Graph Representation)

계산 오버헤드를 줄이기 위해, 양자 회로와 하드웨어 토폴로지는 반복적인 유향 비순환 그래프(DAG) 평가에 의존하는 대신 압축된 그래프 표현으로 변환된다.

• 연결성 그래프 (Connectivity Graph): 큐비트를 노드로, 2-큐비트 게이트를 에지로 나타내며, 게이트 수에 따라 가중치를 부여한다.
• 시간적 의존성 (Temporal Dependencies): 파티션이 큐비트를 공유할 때 와이어 컷을 효율적으로 평가하기 위해 별도로 저장된다.
• 하드웨어 토폴로지 (Hardware Topology): 노이즈 메트릭(예: $1-q$ 및 $2-q$ 게이트 에러)과 라우팅 비용(Floyd-Warshall 최단 경로를 통해 추정)을 포함하는 가중치 그래프로 모델링된다.

2. 초기 파티셔닝 (Initial Partitioning - Warm-Start)

프레임워크는 METIS 라이브러리를 사용하여 전역 그래프 파티셔닝을 수행한다. 이 단계는 하드웨어 용량 제약을 만족하는 초기 솔루션을 생성하여, 후속 정교화(refinement)를 위한 고품질의 시작점을 제공한다. 이 단계는 주로 게이트 컷 또는 와이어 컷을 개별적으로 처리하여 베이스라인을 구축한다.

3. 로컬 정교화 (Local Refinement)

타부 서치(Tabu Search) 알고리즘이 로컬 이동(local moves)을 통해 초기 파티션을 반복적으로 정교화한다:

• 파티션에 노드 추가 (용량 제한 준수).
• 파티션 간 노드 이동.
• 파티션 경계에서의 노드 스와핑(swapping).
• 혼합 컷 평가 (Mixed Cut Evaluation): 비용 함수는 게이트 컷과 와이어 컷을 모두 명시적으로 고려한다. 오버헤드는 $Overhead = (GateCost)^g \cdot 16^w$ (여기서 $g$와 $w$는 각각 게이트 컷과 와이어 컷의 수)로 계산된다. 계산 최적화를 위해 탐색 과정 중에는 이 비용의 로그값이 사용된다.
• 로컬 평가 전략 (Local Evaluation Strategy): 전체 그래프를 다시 평가하는 대신, 프레임워크는 큐비트 수준의 그래프 표현을 기반으로 한 로컬 와이어 컷 룩업 전략을 사용하여 복잡도를 $O((a+1)p \log p)$로 크게 낮춘다.

4. 하드웨어 인식 파티션 할당 (Hardware-Aware Partition Assignment)

실행 충실도를 최적화하기 위해, MosaiQC는 Frank-Wolfe 알고리즘을 사용하는 이차 할당 문제(Quadratic Assignment Problem, QAP) 솔버를 채택한다.

• 목적: 기대 충실도를 최대화(노이즈 최소화)하기 위해 회로 파티션을 하드웨어 백엔드에 매핑하는 치환 행렬(permutation matrix)을 찾는 것이다.
• 스코어링 (Scoring): 알고‌리즘은 회로 파티션 행렬과 하드웨어 노이즈 토폴로지 행렬의 곱의 트레이스(trace)를 최소화한다. 다양한 스케일을 효과적으로 다루기 위해 노이즈 가중치는 로그 변환($w = \ln(1 - \epsilon_{noise})$)된다.
• 적응형 비용 함수 (Adaptive Cost Function): QAP 평가의 계산 비용과 최적화 품질 사이의 균형을 맞추기 위해, 프레임워크는 컷 오버헤드를 QAP 배치 점수에 대해 정규화하는 적응형 비용 함수($S_{adapt}$)를 사용한다. QAP 평가는 매 반복마다 수행되는 것이 아니라 일정 간격으로 수행된다.

주요 기여 (Key Contributions)

본 논문은 다음과 같은 구체적인 기여를 주장한다:

1. 통합 최적화 프레임워크: 단일 절차 내에서 혼합 와이어 및 게이트 컷을 최적화하는 휴리스틱 프레임워크로, 이는 기존의 확장 가능한 도구들에서 거의 입증되지 않은 기능이다.
2. 로컬 와이어 컷 평가: 반복적인 DAG 기반 최적화의 계산 복잡도를 줄이는 큐비트 수준의 그래프 표현 기반 전략.
3. 이질적 하드웨어 지원: 다양한 큐비트 용량과 노이즈 특성을 가진 양자 백엔드를 지원하는 추상화 계층을 통해 혼합 크기의 하드웨어 파티션을 허용한다.
4. 하드웨어 인식 배치: 노이즈 감소를 명시적으로 최적화하기 위해 (Frank-Wolfe를 통해 해결되는) 이중 가중치 그래프 매칭을 사용하여 파티션을 하드웨어에 배치한다.
5. 확장 가능한 하이브리드 전략: 전역 METIS 파티셔닝을 통한 웜 스타트 초기화와 로컬 타부 서치 정교화를 결합하여, $O(k \cdot n_q + m \cdot n_q^3)$의 다항 시간 복잡도를 달s한다.

결과 (Results)

프레임워크는 다양한 벤치마크(예: Adder, BV, AQFT, QAOA, VQE)와 다양한 회로 크기(6 ~ 1000 큐비트)에 대해 Qiskit의 회로 커팅 애드온(Dijkstra 알고리즘 사용) 및 전수 조사(exhaustive search) 방법과 비교 평가되었다.

• 런타임 성능: MosaiQC는 베이스라인 대비 런타임에서 2.88배의 기하 평균 속도 향상을 달성했다. 결정적으로, 베이스라인이 빈번하게 타임아웃되거나 메모리 오버플로를 겪었던 것과 달리, 1000 큐비트에 달하는 회로까지 성공적으로 최적화했다.
• 샘플링 오버헤드: 본 프레임워크는 베이스라인 대비 컷의 수를 평균 16.84% 감소시켰다. 이는 오버헤드의 기하급례적 특성으로 인해 약 $5.38 \cdot 10^{11}\times$의 기하 평균 샘플링 오버헤드 개선 효과를 가져왔다.
• 충실도 개선: 하드웨어 인식 배치 전략은 QAP 점수와 측정된 충실도 사이에 강한 피어슨 상관관계($r \approx 0.83 - 0.87$)를 보여주었다. 충실도 벤치마크에서 MosaiQC는 노이즈 가중치가 우선시될 때 베이스라인 대비 +19.56% ± 6.17%의 평균 로컬 충실도 향상을 달성했다.
• 수렴성: 하이브리드 웜 스타트 접근 방식은 정교화 전용 접근 방식에 비해 수렴에 필요한 반복 횟수를 크게 줄여, 검색 초기 단계에서 최적화 도구가 지역 최적점(local minima)에 빠지는 것을 방지했다.

의의 및 주장 (Significance and Claims)

저자들은 MosaiQC를 양자 컴파일 도구의 필수적인 진화 단계로 규정한다. 그들은 양자 회로가 천 큐비트 영역으로 확장됨에 따라, 컷 배치 자체의 최적화가 계산적 병목 현상이 되어서는 안 된다고 주장한다.

본 논문은 MososiQC가 실행 속도와 솔루션 품질 사이의 우수한 트레이드오프를 보여주며, 경쟁 도구들이 배제하고 있는 핵심 기능들(혼합 컷, 이질적 하드웨어 지원, 노이즈 인식 배치)을 추가했다고 단언한다. 실제 회로 커팅이 재구성을 위해 요구되는 기하급수적인 샘플링 오버헤드에 의해 근본적으로 제약받는다는 점을 인정하면서도, 저자들은 MosaiQC가 미래의 이질적인 양자 컴퓨팅 시스템을 위한 확장 가능한 회로 커팅의 실질적인 토대를 마련한다고 주장한다. 이 연구는 확장 가능한 휴리스틱 최적화가 회로 컷 배치에 따른 계산 오버헤드를 실질적으로 줄임으로써, 현재의 하드웨어로는 실행이 불가능했을 알고리즘의 실행을 가능하게 한다고 시사한다.