Gap-Priced $|T\rangle$-States: Dynamic $|T\rangle$ Post-Selection and Budget-Aware Factory Provisioning

기술 요약: Gap-Priced |𝑇⟩-States (GP|𝑇⟩-S)

문제 정의
표면 코드(surface codes)를 이용한 결함 허용 양자 컴퓨팅(FTQC)에서, 매직 |𝑇⟩-상태의 준비는 큐비트와 지연 시간 측면에서 가장 지배적인 비용을 차지한다. 기존의 방식들은 일반적으로 |𝑇⟩-상태 생산을 정적으로 할당한다: 즉, 변동하는 충실도(fidelity)를 가진 확률적이고 공간 효율적인 방법인 배양(cultivation) 또는 결정론적이고 공간 집약적인 방법인 증류(distillation) 중 하나를 선택한다. 기존의 격자 서전리(lattice surgery) 스케줄러들은 이러한 방법들을 고정된 입력값으로 취급하며, 이로 인해 프로그램의 전체 |𝑇⟩-오차 예산(error budget) 중 상당 부분이 사용되지 않은 채 남게 된다. 이러한 정적 프로비저닝은 실행 시간, 공간 오버헤드, 그리고 에러율 사이의 최적의 트레이드오프를 달성하지 못하게 한다. 구체적으로, 정적 갭 컷오프(gap cutoff)는 사용 가능한 상태들을 버리는 결과를 초래하며, 정적 팩토리 할당은 프로그램의 실제 오차 예산 여유(slack)를 무시한 채 최악의 충실도 요구사항을 맞추기 위해 자원을 과잉 할당하는 경향이 있다.

방법론
저자들은 전역 |𝑇⟩-오차 예산($\epsilon$) 하에서 배양 포스트 셀렉션(post-selection), 증류 팩토리 할당, 그리고 격자 서전리 스케줄링을 공동 최적화하는 시스템인 **Gap-Priced |𝑇⟩-States (GP|𝑇⟩-S)**를 제안한다. 이 시스템은 세 가지 통합된 메커니즘을 통해 작동한다:

1. 동적 배양 포스트 셀렉션 (Dynamic Cultivation Post-Selection):
   고정된 갭 컷오프 대신, GP|𝑇⟩-S는 남은 오차 예산에 따라 배양된 상태의 수락 기준을 동적으로 조정한다.

   • 충실도 추정: 시스템은 디코더가 보고하는 보완적 갭(complementary gap)(가장 가능성 높은 교정값과 그다음으로 높은 값 사이의 로그 가능도 차이)을 상태 충실도의 대리 지표(proxy)로 사용한다. 몬테카를로 시뮬레이션에서 유도된 룩업 테이블(lookup table)은 갭 값을 논리 에러율(LER)로 매핑한다.
   • 예산 인지형 스케줄링: 스케줄러가 |𝑇⟩-상태를 소비함에 따라, 시스템은 남은 예산($\epsilon_{rem}$)을 추적한다. 만약 예산이 여유롭다면, 갭 컷오프를 낮추어 충실도는 낮지만 더 빠른 상태를 수락함으로써 예산의 여유를 속도로 전환한다. 만약 예산이 타이트하다면, 컷오프를 높여 충실도를 보장한다. 이를 통해 시스템은 정적 컷오프라면 거부했을 법한, 하지만 남은 프로그램 단계들에 충분한 상태들을 수락할 수 있게 한다.

2. 팩토리 특성화 및 카탈로그 (Factory Characterization and Catalog):
   저자들은 15-to-1 증류 팩토리가 출력하는 상태의 불충실도(infidelity)가 $p_{out} \approx 35p^3$라는 표준 근사치에 의문을 제기한다. 밀도 행렬 시뮬레이션을 통해, 저자들은 할당에 관련된 코드 거리에서 출력 불충실도가 타일 차원($d_x, d_z$)에 따라 수 차례의 오더(order)만큼 변동함을 보여준다.

   • 배양 팩토리 (Cultivating Factories): PureMagic에서 영감을 얻어, 시스템은 15-to-1 증류 팩토리의 라우팅 채널 내에 배양 프로세스를 삽로 넣는 "배양 팩토리"를 도입한다. 이는 결함이 있는 물리적 $T$ 인젝션을 배양된 상태로 대체하며, 단일 레벨의 공간 점유율(footprint)로 두 단계 증류 방식에 필적하는 충실도를 달را한다.
   • 팩토리 카탈로그: 팩토리를 크기($d_x, d_z$), 생산율($\tau$), 출력 불충실도($p_{out}$)로 특성화하는 카탈로그를 생성한다.

3. 동적 계획법 할당기 (Dynamic Programming Allocator):
   GP|𝑇⟩-S는 팩토리 할당과 갭 컷오프 선택을 결합된 최적화 문제로 정식화한다.

   • 파레토 프런트 구축: 동적 계획법 알고리즘을 사용하여, 시스템은 총 물리 큐비트 수($q$), 생산율($r$), 불충실도 가중 출력률($\phi$)이라는 세 가지 지표를 기반으로 유효한 팩토리 구성의 파레토 프런트를 계산한다.
   • 휴리스틱 솔버: 정확한 DP의 계산 시간(수 분이 소요될 수 있음)을 줄이기 위해, 유계 배낭 문제(bounded knapsack) 기반의 휴리스틱 할당기를 제공한다. 이 할당기는 탐색 과정에서 명시적인 배치(placement) 차원을 제거하고 이후 그리디(greedy) 방식으로 구체적인 포트 할당을 해결하여, 매우 빠른 속도로 최적에 가까운 결과를 얻는다.

주요 기여

• Gap-to-Fidelity 매핑: 배양된 상태의 보완적 갭을 충실도 추정치로 변환하여 동적 포스트 셀렉션을 가능하게 하는 추정 방법.
• 동적 스케줄러: 남은 오차 예산에 따라 배양 갭 컷오프를 동적으로 조정하여 충실도와 속도를 트레이드오프하는 격자 서전리 스케줄러.
• 공동 최적화된 할당: 오차 예산을 초과하지 않으면서 실행 시간 또는 시공간 볼륨을 최소화하기 위해 갭 컷오프와 팩토리 구성(크기 및 개수)을 공동으로 최적화하는 동적 계획법 할당기.
• 정교한 팩토리 특성화: 15-to-1 팩토리가 $35p^3$ 근사가 실제 크기에서 종종 부정확함을 입증하고, 낮은 공간 비용으로 높은 충실도를 달성하는 "배양 팩토리"를 도입한 거리별 특성화.

실험 결과
시스템은 $T$-count가 $1.4 \times 10^4$에서 $8.2 \times 10^5$ 사이인 16개의 벤치마크(Ising, QAOA, KNN, QFT 회로 포함)를 대상으로 두 가지 오차 예산 $\epsilon = 10^{-3}$ 및 $\epsilon = 10^{-5}$ 하에서 평가되었다.

• 베이스라인 대비 성능: GP|𝑇⟩-S는 (1) 정적 갭 컷오프를 가진 배양 전용 방식, (2) 배양이 없는 단일 팩토리 방식이라는 두 가지 베이스라인보다 일관되게 우수한 성능을 보였다.
• 지표:
  • 논리 사이클 수 (Logical Cycle Count): 베이스라인 대비 5.5배의 기하 평균 속도 향상(평균 69% 감소)을 달성했다.
  • 시공간 볼륨 (Space-Time Volume): 3.4배의 기하 평균 감소(평간 58% 감소)를 달성했다.
  • 예산 활용도: 베이스라인들이 종종 오차 예산의 50~95%를 사용하지 않고 남겨둔 것과 달리, GP|𝑇⟩-S는 모든 실행에서 거의 전체 예산을 사용하면서도 제한치를 한 번도 초과하지 않았다.
• 실현 가능성: 배양만으로는 실행이 불가능했던 벤치마크(엄격한 충실도 요구사항 때문)에서도, 배양 팩토리와 동적 할당의 추가를 통해 예산 내에서의 실행이 가능해졌다.

의의
본 논문은 배양 튜닝과 팩토리 할당을 분리하여 설계하는 것이 최적이 아닌 선택임을 주장한다. 갭 컷오프와 팩토리 구성을 하나의 결합된 설계 공간으로 취급함으로써, GP|𝑇⟩-S는 오차 예산을 늘리지 않고도 상당한 성능 이득을 얻을 수 있음을 입증한다. 이 연구는 "예산 여유(budget slack)"가 현재의 FTQC 스케줄링에서 매우 중요하지만 흔히 낭비되는 자원임을 강조한다. 제안된 시스템은 양자 프로그램의 특정 오차 허용 범위와 실행 진행 상황에 따라 자원 프로비저닝을 동적으로 적응시킴으로써 표면 코드 아키텍처의 효율성을 극대화할 수 있는 실질적인 프레임워크를 제공한다.