PureMagic: A Dynamic Scheduler for Lattice Surgery

PureMagic 은 라티스 서저리를 위한 동적 스케줄러로, 모든 안실라 패치를 라우팅과 확률적 매직 상태 양성에 재할용하여 전용 버스 패치를 제거함으로써 전통적인 정적 접근 방식에 비해 효율성, 자원 활용도 및 준비 시간을 크게 개선합니다.

핵심

거대하고 매우 복잡한 공장을 운영하는 상상을 해보세요. 이 공장은 자동차나 스마트폰을 만드는 것이 아니라, 오늘날의 기계로는 해결 불가능한 문제를 풀 수 있는 양자 컴퓨터를 만듭니다. 하지만 함정이 하나 있습니다: 이 공장은 매우 취약합니다. 단 한 명의 작업자가 재채기만 해도 전체 생산 라인이 멈출 수 있습니다. 이를 해결하기 위해 공장은 정확성을 보장하기 위해 많은 작업자가 같은 일을 수행하는 오류 수정이라는 "안전망" 시스템을 사용합니다.

그러나 가장 첨단 작업을 수행하려면 **"매직 상태 (magic state)"**라는 특수하고 희귀한 재료가 필요합니다. 이 재료를 만드는 것은 까다롭습니다.

구식 방식: 전용 "매직 공장"

전통적인 접근 방식 (이전 시스템에서 사용됨) 에서는 공장은 이러한 매직 상태 전용으로 거대하고 영구적인 건물을 지었습니다.

• 문제점: 이러한 건물은 논리적 큐비트라는 막대한 공간을 차지했습니다. 마치 공장 바닥 가장자리에 자리 잡은 거대한 창고들 같았습니다.
• 병목 현상: 고정된 위치에 있었기 때문에 이동할 수 없었습니다. 만약 주요 생산 라인이 공장 한쪽에서 다른 쪽으로 상자를 옮기도록 작업자를 필요로 한다면, 매직 공장의 작업자들은 도움을 줄 수 없었습니다. 그들은 매직 상태 제작에 갇혀 있었기 때문입니다.
• 도박: 매직 상태를 만드는 것은 주사위를 굴리는 것과 같습니다. 때로는 몇 초가 걸리지만, 때로는 운이 나빠 몇 시간이 걸리기도 합니다. 구식 시스템은 "느린 주사위 굴림"이 완료될 때까지 기다려야 했기 때문에 전체 공장이 대기하게 되었습니다.

새로운 방식: PureMagic ("스위스 아미 나이프" 작업자)

이 논문은 공장을 운영하는 방식을 완전히 바꾸는 PureMagic이라는 새로운 방식을 소개합니다.

1. 전용 공장 폐지
매직 상태 전용 건물을 짓는 대신, PureMagic 은 **"모든 사람이 매직 제작자다"**라고 말합니다.
공장 내 모든 단일 작업자 (안실라 패치라고 함) 는 매직 상태를 만들도록 훈련받습니다. 그들은 끊임없이 매직 재료를 양조하려 노력합니다.

2. 동적 전환
여기에 영리한 부분이 있습니다: 이러한 작업자들은 동시에 배송 기사이기도 합니다.

• 시나리오 A: 한 작업자가 매직 양조에 바쁩니다.
• 시나리오 B: 갑자기 주요 생산 라인이 그 작업자에게 공장을 가로질러 상자를 나르도록 (라우팅) 요구합니다.
• 매직 이동: 작업자는 즉시 양조를 멈추고, 반쯤 완성된 매직을 내려놓고 상자를 나릅니다. 상자를 배송하자마자 그들은 즉시 처음부터 다시 매직 양조를 시작합니다.

왜 이것이 더 나은가요?

• "긴 꼬리" 절단: 구식 시스템에서는 매직 제작 시도가 "불운한" 루프에 갇혀 (끝없이 걸려서) 멈추면 전체 공장이 기다려야 했습니다. PureMagic 에서는 작업자가 양조에 갇히면 배송 업무로 중단됩니다. 이는 자연스럽게 느린 시도들의 "긴 꼬리"를 잘라냅니다. 공장은 "빠른" 매직 제작자만 유지하므로 매직을 얻는 평균 시간이 훨씬 빨라집니다 (논문에 따르면 4.5 배 빠름).
• 대기 시간 제거: 구식 시스템에서는 배송 작업자들이 매직 공장이 작동하는 동안 대기했고, 그 반대의 경우도 마찬가지였습니다. PureMagic 에서는 모든 작업자가 항상 무언가를 합니다. 매직을 만들거나 물건을 옮기는 것입니다. 낭비되는 공간은 없습니다.

3. "무게 제한" 트릭
이 논문은 "무게 제한" (기호: $\omega$) 이라는 소프트웨어 트릭도 언급합니다. 한 번에 작업자가 나를 수 있는 상자 수에 대한 규칙이라고 생각하세요.

• 구식 방식은 단계를 절약하기 위해 거대한 하중 (복잡한 명령어) 을 나르려 했지만, 쉽게 걸렸습니다.
• PureMagic 은 명령어를 작은 단일 상자 하중으로 나누는 규칙을 사용합니다. 이는 공장이 동시에 많은 작업자를 병렬로 실행할 수 있음을 의미합니다. PureMagic 은 매직 공장에 갇히지 않은 많은 작업자를 활용할 수 있기 때문에, 구식 시스템보다 이러한 병렬성을 훨씬 더 잘 활용할 수 있습니다.

결과

연구진은 이 새로운 시스템을 29 가지 다른 "공장 설계" (벤치마크 회로) 에서 테스트했습니다. 그들이 발견한 바는 다음과 같습니다:

• 효율성: PureMagic 은 구식 버스 라우팅 시스템보다 40% 에서 150% 더 효율적이었습니다.
• 공간: 동일한 작업을 수행하는 데 작업자 (논리적 큐비트) 를 19% 에서 80% 적게 사용했습니다.
• 속도: 매직 재료를 준비하는 데 필요한 시간을 4.5 배 줄였습니다.
• 비교: 기존 최고의 정적 스케줄러 (DASCOT) 와 비교했을 때, 매직 상태 제작 비용을 계산하면 PureMagic 은 최대 15 배 더 효율적이었습니다.

결론

PureMagic 은 공장을 고정된 역할이 있는 경직된 격자가 아닌, 유동적이고 역동적인 환경으로 취급합니다. 모든 작업자가 "매직 제작"과 "패키지 배송" 사이를 즉시 전환하도록 함으로써, 낭비되는 공간을 제거하고 가장 느린 시도들을 잘라내며 양자 컴퓨터가 최고 속도로 작동하도록 유지합니다. 이 논문은 이 접근 방식이 이론적 완벽성의 한계에 거의 도달하여 기계의 기본 물리학을 바꾸지 않는 한 그보다 더 잘할 수 있는 것이 거의 불가능하다고 주장합니다.

기술 요약

기술 요약: PureMagic

문제 제기

표면 코드를 이용한 내결함성 양자 연산은 범용성을 달성하기 위해 매직 상태에 의존합니다. 전통적인 접근법은 결정론적으로 매직 상태를 생성하는 대규모 정적 논리 큐비트 배열인 **증류 공장 (distillation factories)**을 활용합니다. 이는 121~176 개의 패치당 출력 포트가 필요한 정적이며 주변부 배치된 자원을 필요로 하여, '버스' 패치는 라우팅 전용으로, '매직' 패치는 생산 전용으로 고정된 경직된 아키텍처를 초래합니다.

대안인 **매직 상태 재배 (magic state cultivation)**는 단일 논리 큐비트까지 공간 점유를 줄이지만 본질적인 확률성을 도입합니다. 고충실도 매직 상태를 생성하는 데 필요한 시간은 '긴 꼬리 (long tail)'를 가진 지수 분포를 따르므로, 일부 시도는 평균보다 훨씬 더 오래 걸립니다. 결정론적 자원 가용성을 가정하는 정적 스케줄러는 이러한 변동성에 적응하지 못해 정지 및 비효율을 초래합니다. 또한, 재배 시간의 긴 꼬리는 정적 스케줄러가 자원을 과잉 공급하거나 상당한 지연을 감수하도록 강요합니다.

방법론

저자들은 격자 수술 (lattice surgery) 에서 안실라 패치 (ancilla patches) 의 역할을 근본적으로 재고하는 PureMagic이라는 동적 스케줄링 프레임워크를 제안합니다.

1. 이중 목적 안실라 아키텍처

PureMagic 은 전용 버스 패치와 매직 상태 재배기 간의 구분을 없앱니다. 대신 모든 안실라 패치를 이중 목적 자원으로 취급합니다.

• 재배: 모든 데이터가 아닌 패치는 지속적으로 매직 상태 재배를 시도합니다.
• 라우팅: 파울리 곱 (Pauli product) 을 위한 라우팅 경로가 필요할 때, 현재 재배 중인 패치를 포함한 모든 패치는 즉시 재사용될 수 있습니다.
• 중단 및 재시작: 패치가 라우팅에 필요하면 진행 중인 재배가 취소됩니다. 라우팅 작업이 완료되면 해당 패치에서 재배가 처음부터 다시 시작됩니다. 이 메커니즘은 재배 시간 분포의 긴 꼬리를 자연스럽게 잘라내어, 느리게 성장하는 상태는 라우팅 요구에 의해 중단되므로 오직 가장 빠른 성공적인 시도만이 일정에 기여하도록 보장합니다.

2. 동적 스케줄링 알고리즘

스케줄러는 클리포드+T 회로를 다중 큐비트 파울리 곱 측정 시퀀스로 변환하는 파울리 기반 연산 (PBC) 프레임워크 내에서 작동합니다.

• 실시간 적응: 스케줄러는 단일 논리 사이클 (코드 거리 $d=17$의 경우 약 17µs) 내에서 결정을 내립니다. 이는 확률적 재배 완료 시간과 T-상태 주입 실패 (S-게이트 보정 필요) 의 50% 확률이라는 두 가지 비결정론적 소스를 처리합니다.
• 휴리스틱 패킹: NP-하드인 격자 수술 스케줄링 문제 (LSSP) 를 해결하기 위해 PureMagic 은 탐욕적 스테이너 숲 (Steiner forest) 패킹 알고리즘을 사용합니다. 이는 맨해튼 거리를 사용하여 추정된 트리 크기를 기반으로 파울리 곱에 우선순위를 부여하여 가장 컴팩트한 연산을 먼저 스케줄링합니다.
• 경로 탐색: 단일 연산자 파울리 곱의 경우, 효율적인 A* 알고리즘을 사용하여 사용 가능한 매직 상태로의 경로를 찾습니다. 다중 큐비트 곱의 경우, 최단 경로 휴리스틱이 스테이너 트리를 근사합니다.

3. 가중치 제한 ($\omega$) 을 통한 변환

저자들은 가중치 제한 $\omega$를 사용한 테이블로 (Tableau) 알고리즘을 적용한 변환 확장을 도입합니다.

• $\omega = 1$ (경량-PBC): 파울리 곱을 단일 연산자로 제한합니다. 이는 총 게이트 수를 약간 (2~6%) 증가시키지만, 병렬성을 극대화하여 회로 깊이를 획기적으로 (최대 26 배) 줄입니다.
• $\omega = \infty$ (중량-PBC): 모든 클리포드 게이트가 교환되는 표준 방식으로, 게이트 수는 적지만 가중치가 높은 파울리 곱과 낮은 병렬성을 초래합니다.
  PureMagic 은 특히 $\omega = 1$ 설정의 높은 병렬성을 활용하도록 설계되었으며, 이는 증가된 수의 재배 가능 패치가 더 많은 동시 라우팅 요청을 처리할 수 있기 때문입니다.

주요 기여

1. PureMagic 아키텍처: 전용 버스 패치를 제거하고 모든 안실라 패치가 재배기와 라우팅 자원으로 상호 교환적으로 기능할 수 있도록 하는 레이아웃 설계.
2. 동적 스케줄러: 확률적 재배 시간과 T-상태 주입 실패에 적응하며 탐욕적 스테이너 숲 패킹 방식을 활용하는 실시간 스케줄러.
3. 시뮬레이션 프레임워크: 스케줄링 성능을 평가하기 위해 확률적 재배 및 주입 실패를 모델링하는 논리 큐비트 수준의 시뮬레이터.
4. 가중치 제한 변환: 게이트 수와 회로 병렬성 간의 트레이드오프를 통해 PureMagic 아키텍처에 최적화된 워크로드를 제공하는 테이블로 알고리즘 확장.

실험 결과

이 프레임워크는 Benchpress 스위트의 29 개 벤치마크 회로에서 평가되었으며, 추상적 표면 코드 모델 ($d=17$) 에서의 실행을 시뮬레이션했습니다.

• 효율성 향상: 전통적인 버스 라우팅 레이아웃과 비교하여 PureMagic 은 효율성 (시공간 부피의 역수) 에서 40% 에서 150% 개선을 달성합니다. 이러한 이득은 경량 변환 설정 ($\omega = 1$) 을 사용할 때 가장 두드러집니다.
• 자원 감소: PureMagic 은 고정된 주변부의 전용 매직 상태 공장이 필요하지 않으므로, 버스 라우팅 레이아웃보다 논리 큐비트를 19% 에서 80% 적게 사용합니다.
• 재배 시간: 재배 분포의 긴 꼬리가 잘려나감에 따라 평균 매직 상태 준비 시간은 4.5 배 감소했습니다 (평균 26 사이클에서 5.8 사이클로).
• 정적 스케줄러와의 비교: 즉각적인 매직 상태 가용성을 가정하는 최첨단 정적 스케줄러인 DASCOT과 비교할 때, 매직 상태 준비 비용 (재배 시간 또는 증류 공장 면적) 을 포함하면 PureMagic 은 최대 15 배 더 효율적입니다.
• 이론적 한계: PureMagic 의 스케줄링된 부피는 보수적이고 낙관적인 FLASQ 이론적 하한선 사이에 위치하여, 동적 이중 목적 전략이 '유동적 (fluid)' 안실라 자원의 이상에 근접함을 보여줍니다.

중요성 및 주장

이 논문은 라우팅과 매직 상태 생산의 분리가 증류 공장의 높은 오버헤드로 인한 산물이라고 주장합니다. 재배와 동적 스케줄링을 채택함으로써, 사용 가능한 모든 자원이 어떤 기능이라도 수행할 수 있는 '유동적 안실라 (fluid-ancilla)' 이상을 달성 가능하게 만듭니다.

저자들은 PureMagic 이 동적 스케줄링이 효율적인 내결함성 양자 연산에 필수적임을 보여주며, 특히 재배와 같은 자원 효율적 방법을 사용할 때 그렇다고 주장합니다. 그들은 향후 양자 오류 정정 코드 (QECC) 비교가 정적 게이트 수준 지표를 넘어 동적 스케줄링 및 자원 관리의 오버헤드를 포함해야 한다고 제안합니다. 이 연구는 알고리즘이 더 높은 충실도의 매직 상태 (더 긴 재배 시간 필요) 를 요구함에 따라, 대규모 패치 풀 전체에 재배 비용을 분산시키는 PureMagic 의 이점이 더욱 중요해질 것임을 시사합니다.