The limits of magic-state distillation

기술 요약: 매직 상태 증류의 한계

문제 정의
매직 상태 팩토리(Magic-state factories)는 결함 허용 양자 컴퓨팅에서 상당한 오버헤드를 차지하며, 고충실도 타겟 상태를 생성하기 위해 노이즈가 있는 비-클리포드(non-Clifford) 자원(예: $T$ 상태)을 소비한다. 자원 이론(Resource theories)은 일반적인 경계치를 제공하지만, 종종 약한 스케일링(예: $n \gtrsim d$)을 나타내거나 결정론적 성공을 가정한다. 반대로, 전수 조사(Exhaustive searches)는 특정 코드 패밀리에 대한 입력 개수를 해결했으나, 적응형(adaptive), 사후 선택형(postselected), 또는 다단계(multistage) 프로토콜이 정적 안정기 코드(static stabilizer codes)보다 더 우수한 성능을 낼 수 있는지 여부는 확립하지 못했다. 본 논문이 다루는 핵심 질문은 다음과 같다: 임의의 안정기 프로토콜이 입력 에러율 $p$에 대해 타겟 상태 $\tau$를 오차 억제 차수 $d$(출력 에러 $O(p^d)$)로 증류하는 데 필요한 최소한의 노이즈 입력 수 $n$은 얼마인가?

방법론
저자들은 두 가지 핵심 이론적 축소를 통해 잠재적인 증류 프로토코의 무한한 공간(적응형, 사후 선택형 및 다단계 전략 포함)을 안정기 코드를 통한 조합론적 탐색으로 축소한다:

1. 단일 코드 투영으로의 축소 (정리 1): 본 논문은 특정 결함 패턴을 허용하는 모든 안정기 프로토콜이 단일 안정기 코드 투영보다 강력하지 않음을 증명한다. 구체적으로, 프로토콜이 결함이 없는 입력을 수용하고 결함 패턴 집합을 무해하게 만드는 것은, $n$개의 입력에 대한 안정기 코드 $C$가 존재하여 모든 허용 가능한 입력 상태가 인코딩된 타겟 벡터로 투영되거나 0으로 투영되는 것과 필요충분조건이다. 이는 복잡한 회로 토폴로지, 피드포워드(feedforward) 또는 무작위성을 탐색할 필요 없이, 부호가 있는 안정기 코드(signed stabilizer codes)를 찾는 문제로 대체함으로써 복잡한 구조를 제거한다.
2. 보완적 결함의 대칭성 (정리 2): 유리수 파울리 기대값(예: CCZ, CS)을 갖는 타겟의 경우, 결함 패턴 $e$가 무해하다면 그 보완 패턴 $e + \mathbf{1}$ 또한 무해함을 본 논문은 입증한다. 이러한 대칭성은 자기동형사상(automorphism) $\sigma$($\sqrt{2}$의 부호를 반전시킴)가 안정기 연산과 교환 가능하며, 노이즈 상태 $\rho_T(p)$를 $\rho_T(1-p)$로 매핑하기 때문에 발생한다. 이는 반드시 허용해야 하는 결함 패턴의 집합을 실질적으로 두 배로 늘려, 후보 코드에 대한 탐색 공간을 크게 줄여준다.

이러한 축소 기법을 사용하여, 저자들은 $n=9$까지의 부호 있는 안정기 코드에 대한 전수 조사를 수행하기 위해 환 $\mathbb{Z}[\sqrt{2}, i]$ 상의 엄밀한 산술을 활용한다. 이들은 정수 계획법(integer programming)과 SAT 솔버를 사용하여 명시적인 팩토리(상한치)를 구축하고, 이를 정리 1에서 도출된 "붕괴(collapse)" 조건에 대해 검증한다. "위너(witness)" 상태와 선형 계획법 완화(linear programming relaxations)를 사용한 해석적 논증은 더 높은 차수에 대한 하한치를 제공한다.

주요 기여 및 결과
본 논문은 임의의 안정기 프로토콜에 의한 에러 억제를 위한 첫 번째 정확한 최소 입력 수 $n_{\min}(\tau, d)$를 확립하여, 기존 팩토리들의 최적성에 관한 여러 미해결 문제를 해결한다:

• 기존 팩토리의 최적성: 탐색 결과, 8-입력 이차(quadratic) CCZ 팩토리가 최적임이 확인되었다. 즉, 8개의 입력보다 적은 수를 사용하여 $d=2$ 차수의 CCZ 상태를 증류할 수 있는 적응형 또는 다단계 프로토콜은 존재하지 않는다. 마찬가지로, 8-입력 이차 CS 팩토리도 최적이다.
• T 상태에 대한 새로운 하한치: 이차 억제($d=2$)를 통해 단일 $T$ 상태를 증류하는 경우, 본 논문은 8개의 입력으로는 불충분함을 증명한다. 최소 요구량은 9개 입력이다. 저자들은 이상적 입력 수용 확률이 $1/128$이고 에러 계수가 $27/2$인 9-입력 팩토리를 명시적으로 구축하여, 기존의 최선이었던 10-입력의 기록을 개선하였다.
• 일반 하한치:
  • 유리수 타겟(비-안정기 상태)에 대해 차수 $d$에서, $n \ge 2d + 1$이다.
  • 하나의 $T$ 상태에 대해 차수 $d$에서, $n \ge 2d$이다.
  • 이 경계치들은 임의의 사후 선택을 허용하며, 기존의 일반 경계치인 $\max(d, \nu)$ (여기서 $\nu$는 안정기 영성(nullity)임)를 초과한다.
• 구성적 개선:
  • 2단계 설계(two-level design)는 48개의 입력을 사용하는 4차($d=4$) CCZ 팩토리를 생성하며, 이는 이전의 48-입력 최선치보다 3분의 1 미만인 $864p^4$의 선행 에러 계수를 달성한다.
  • 36-입력 3차(cubic) CCZ 팩토리가 재발견되었으며, 이는 해당 클래스에서 기존의 최선이었던 47-입력을 개선한 것이다.
  • 6-입력 CCCZ 상태 프로토콜이 $d=1$에 대해 최적임을 확인하였다.

의의
본 논문은 적응성, 사후 선택 또는 다단계 처리가 작은 규모의 매직 상태 팩토리의 자원 비용을 줄일 수 있는지에 대한 의문을 해결한다고 주장한다. 모든 그러한 프로토콜이 단일 안정기 코드 투영과 동등함을 증명함으로써, 저자들은 (특히 $T$, CS, CCZ 상태의 이차 억제와 같은) 작은 규모의 팩토리의 경우, 이러한 전략들이 기존의 전수 조사된 안정기 코드 탐색을 통해 발견된 한계치 아래로 입력 수를 줄일 수 없음을 보여준다.

이 결과는 사후 선택을 고려한 최초의 정확한 하한치를 제공하며, 유리수 타겟에 대해 안정기 영성 경계를 엄격히 초과한다. 본 논문은 고차 억제(예: 3차 또는 4차 $T$ 상태)를 위한 간극이 남아 있음을 인정하면서도, "단일 코드 축소"가 이미 낮은 에러율을 가진 입력을 배양하는 근시일 내의 결함 허용 아키텍처에 가장 관련성이 높은 영역에서 프로토콜 복잡도와 자원 효율성 사이의 트레이드오프를 제거한다는 점을 확립한다. 이 연구는 정밀한 자원 비용을 정의함으로써 기존의 점근적 구성 및 정확한 집중 결과들을 보완한다.