General circuit mapping algorithm for neutral atom quantum computers

기술 요약: 중성 원자 양자 컴퓨터를 위한 일반 회로 매핑 알고리즘

문제 정의
중성 원자 양자 컴퓨터(NAQC)는 긴 결맞음 시간(coherence times), 유연한 큐비트 배치, 그리고 고유한 다중 큐비트 게이트 기능(예: CCZ, Ck-phase)을 특징으로 하는 확장 가능한 플랫폼을 제공한다. 그러나 NAQC 하드웨어에서 양자 회로를 실행하려면 광 트위저(optical tweezers)를 통해 원자를 물리적으로 이동시켜 큐비트를 인접하게 가져와야 한다(Rydberg blockade). 이러한 "재매핑(remapping)" 과정은 다음과 같은 상당한 오버헤드를 발생시킨다:

1. 충실도 손실(Fidelity Loss): 각 이동은 원자 소실이나 상태 변화의 위험을 수반한다. 단일 이동 성공률은 높지만(>0.99), 많은 큐비트나 이동이 필요한 회로에서는 누적된 오류가 치명적이 될 수 있다.
2. 시간 오버헤드: 이동은 시간을 소비하여 전체 계산 창(computation window)을 줄인다.
3. 최적화 과제: 기존 컴파일러(예: ZAC, MQT)는 시뮬레이티드 어닐링(simulated annealing)이나 탐욕 알고리즘(greedy algorithms)과 같은 휴리스틱에 의존하는 경우가 많다. 이러한 방법들은 초기 방식보다 개선되었으나, 필요한 이동 횟수에 대한 명시적인 이론적 하한선(lower bounds)을 결여하고 있으며, 모놀리식(M-arch) 및 존형(Z-arch) 아키텍처 모두에서 총 이동 거리와 병렬 이동 연산(PTO)을 동시에 최적화하는 일반적인 정식화(formulation)를 제공하지 못한다.

방법론
저자들은 그래프 이론 기반의 조합 최적화를 활용한 통합적이고 회로 독립적인 수학적 프레임워크를 제안한다. 이 방법론은 네 가지 단계로 진행된다:

1. 그래프 표현 (이론적 토대):

   • 양자 회로는 정점(vertex)이 "명령어"(특정 단계 내 특정 큐비트에 작용하는 게이트 그룹)를 나타내고, 간선(edge)이 단계 간의 전이를 나타내는 방향성 비순환 그래프(DAG)로 분해된다.
   • 단계 간 이동을 최소화하는 문제는 연속적인 단계들을 연결하는 이분 부분 그래프(bipartite subgraphs)에서의 **최대 가중 매칭(maximum weighted matching)**을 찾는 문제로 모델링된다.
   • 정리(Theorem) 3.1 & 3.2: 저자들은 M-arch와 Z-arch 모두에서 최소 이동 횟수가 이러한 매칭의 국소적 최소값들의 합에 의해 도출될 수 있음을 증명한다. Z-arch의 경우, 그래프는 존(zone)별 부분 그래프로 분해되며, 존 사이에는 필수적인 이동이 발생한다.

2. 스틱 인코딩 (문제 축소):

   • 원자의 물리적 배치를 최적화하기 위해, 저자들은 단계 사이에 정적으로 유지되는 큐비트들을 "스틱(stick)"으로 그룹화하여 문제를 추상화하는 "스틱 인코딩"을 도입한다.
   • 하나의 스틱 내에서 큐비트들은 "서브스틱(substick)"을 형성한다. 이 인코딩은 원자 그리드 상의 스틱의 2D 공간 좌표와 다중 큐비트 스틱 내의 서브스틱이 스왑(swap)되었는지 여부를 나타내는 불리언(Boolean) 변수라는 고유한 자유도(DoFs)를 포착한다.
   • 이 인코딩은 어떤 큐비트를 이동시킬지에 대한 결정(그래프 매칭에 의해 결정됨)과 큐비트의 배치(placement)를 분리함으로써, 이동 거리 최적화를 효율적으로 수행할 수 있게 한다.

3. 유전 알고리즘 (최적화):

   • 비선형 정수 프로그램을 해결하기 위해 유전 알고리즘(GA)이 사용된다.
   • GA는 교차(crossover) 없이, 대신 국소적 무작위 수정(스틱 이동 또는 서브스틱 셔플링)에 의존하여 구성 공간(configuration space)을 탐색한다.
   • 목적 함수는 유연하여, 사용자가 총 이동 거지를 최소화하거나 병렬 이동 연산을 최대화하거나, 혹은 두 가지의 가중치 조합을 우선시하도록 설정할 수 있다.

4. 병렬 이동 연산(PTO) 구축:

   • 사후 처리 단계에서 병렬 이동 시퀀스를 구축한다.
   • 알고리즘은 이동 유향 그래프(transfer digraph)를 분석하여 사이클을 감지한다. 만약 사이클이 존재하면(원자들이 서로의 경로를 막는 경우), "주차 공간(parking space)"(빈 원자 슬롯)을 사용하여 사이클을 깨뜨리며, 이는 한 번의 추가 이동을 요구한다.
   • 그 후 탐욕 알고리즘이 이동을 스케줄링하여, 충돌을 피하면서 병렬성을 극대화하도록 하며 하드웨어 제약 조건(예: 광학적 변조기(AOD) 제한)과의 호환성을 보장한다.

주요 기여

• 일반적 수학적 프레임워크: 본 논문은 모든 NAQC 플랫폼(M-arch 및 Z-arch 모두 적용 가능)에 대해 임의의 양자 회로에서 요구되는 원자 이동 횟수의 이론적 하한선을 결정하는 최초의 그래프 이론적 정식화를 제공한다.
• 새로운 인코딩: "스틱 인코딩"의 도입은 공간적 배치 및 내부 큐비트 순서와 관련된 자유도를 격리함으로써 매핑 문제의 복잡성을 효과적으로 감소시킨다.
• 트레이드오프 제어: 이 프레임워크는 원자의 총 이동 거리(시간 감소)를 최소화하는 것과 병렬 이동 연산(지연 시간 감소)을 최대화하는 것 사이의 트레이드오프를 명시적으로 가능하게 한다.
• 이론적 보장: 기존의 휴리스틱 접근 방식과 달리, 본 연구는 이동 횟수에 대한 증명 가능한 하한선(정리 3.1/3.2)을 제공하며, 제안된 방법이 이러한 하한에 일관되게 도달함을 입증한다.

결과
저자들은 자신들의 알고리즘을 ZAC(재사용 인지형 존형 아키텍처 매퍼) 및 MQT(Munich Quantum Toolkit)와 같은 최신 매퍼들과 벤치마킹하였다.

• 이동 횟수: 제안된 방법은 테스트된 모든 회로에 대해 이론적 최소 이동 횟수(사이클 파괴 요구 사항으로 인한 0~2회의 차이 내에서)를 일관되게 달여낸다. 반면, ZAC는 종종 이 이론적 최소치를 초과한다.
• 거리 및 병렬성:
  • 거리를 최적화할 때, 제안된 방법은 ZAC에 비해 총 이동 거리를 현저히 줄인다 (예: QFT 회로의 경우 약 333% 개선).
  • 병렬 이동을 최적화할 때, 이 방법은 특히 복잡한 회로에서 MQT와 ZAC보다 더 많은 PTO를 달성하며 성능이 우수하다.
• 유연성: 결과는 트레이드오프를 강조한다: 거리를 최적화하는 것이 항상 PTO를 최소화하는 것은 아니며, 그 반대도 마찬가지이다. GA를 통해 실무자는 특정 하드웨어 파라미터(예: 트위저 이동 속도 대비 트랩 스위칭 속도)에 따라 목적 함수를 조정할 수 있다.

의의 및 주장
본 논문은 효율적인, 아키텍처 인식형 양자 회로 컴파일을 위한 이론적 기준선과 실용적 도구를 모두 제공한다고 주장한다.

• 이론적 측면: 최소 이동 횟수가 그래프 매칭을 통해 결정될 수 있음을 확립하여, 향후 컴파일러 개발을 위한 벤치마크를 제공한다.
• 실용적 측면: 실무자가 하드웨어 인식형 매핑을 생성할 수 있도록 하는 유연한 최적화 도구를 제공한다. 이동으로 인한 오류를 줄이고 원자 이동의 병렬성을 더 잘 활용함으로써, 이 방법은 NAQC 장치의 실행 효율성을 직접적으로 향상시킨다.
• 확장성: 이 접근 방식은 일반적이고 확장 가능하다고 기술되어 있으며, 다양한 게이트 세트(다중 큐비트 게이트 포함)를 처리할 수 있고, 추가적인 존(예: CCZ 게이트용)이 있는 미래의 NAQC 아키텍처에도 적응 가능하다.

저자들은 실행 시간에 대해 겸허한 태도를 유지하며, 거리 최소화와 PTO 최소화 중 최적의 선택은 특정 하드웨어 파라미터(예: SLM/AOD 스위칭 속도 대 트위저 이동 속도)에 따라 달라질 수 있다고 언급한다. 이들은 주어진 장치에 최적의 솔루션을 선택하기 위해 매퍼를 다양한 파라미터로 실행할 것을 권장한다.