Magic State 증류: 내결함성 비클리퍼드 연산의 자원 기법

개념 소개

양자 오류 정정 코드 대부분은 Clifford 연산을 트랜스버살(transversal) 방식, 즉 논리 큐비트 전체에 독립적으로 동시 적용하는 형태로 구현할 수 있다. 그러나 Eastin-Knill 정리는 단일 코드에서 보편 게이트 집합을 트랜스버살하게 구현하는 것이 원리적으로 불가능함을 증명한다. 즉, $\{H,S,\mathrm{CNOT}\}$으로 이루어진 클리퍼드 군만으로는 보편 양자계산이 성립하지 않는다.

이를 뒷받침하는 근거가 Gottesman-Knill 정리다. 클리퍼드 연산, 파울리 측정, 계산 기저 상태 초기화만으로 이루어진 회로는 고전 컴퓨터로 다항 시간 내에 효율적으로 시뮬레이션할 수 있다. 따라서 지수적 양자 우위를 위해서는 반드시 비클리퍼드 연산이 필요하며, 그 대표가 **T 게이트(π/8 게이트)**이다.

$$T=\left(\begin{array}{cc}1& 0\\ 0& e^{i\pi /4}\end{array}\right)$$

T 게이트를 코드 블록에 직접 적용하면 오류 정정 구조가 파괴된다. 이 문제의 해법이 Magic State 증류다: 잡음 있는 Magic State 다수를 클리퍼드 회로와 측정만으로 처리하여 소수의 고순도 상태를 얻고, 이를 **상태 주입(state injection)**으로 논리 T 게이트에 연결한다.

핵심 원리

Magic State 정의

T 게이트에 대응하는 Magic State는 다음과 같이 정의된다.

$$|T⟩=T|+⟩=\frac{1}{\sqrt{2}}(|0⟩+e^{i\pi /4}|1⟩)$$

이 상태는 파울리 군의 안정자(stabilizer)로 표현되지 않으므로 클리퍼드 형식 밖에 존재한다. 실제 물리 시스템에서는 탈분극화 잡음 등으로 인해 오류율 $p$를 가진 혼합 상태로 생성된다.

$${\rho }_{\text{noisy}}=(1-p)|T⟩⟨T|+p\frac{I}{2}$$

15-to-1 증류 프로토콜

Bravyi와 Kitaev가 제안한 15-to-1 프로토콜은 $[[15,1,3]]$ Reed-Muller 코드를 기반으로 한다. 거리 3의 이 코드는 임의의 단일 큐비트 오류를 검출할 수 있다.

절차:

1. 잡음 있는 $|T{⟩}^{\otimes 15}$를 준비한다.
2. 클리퍼드 인코딩 회로를 적용하여 $[[15,1,3]]$ 코드 상태로 변환한다.
3. 14개의 보조 큐비트를 측정하여 오류 증후군을 확인한다.
4. 증후군이 무오류 패턴과 일치하면 남은 1큐비트가 고순도 $|T⟩$에 해당하고, 불일치 시 전체를 폐기한다.

오류 억제 관계식은 다음과 같다.

$$p_{\text{out}}\approx 35p_{\text{in}}^3$$

수렴 조건은 $p_{\text{out}}<p_{\text{in}}$, 즉 $35p^2<1$에서

$$p_{\text{in}}<\frac{1}{\sqrt{35}}\approx 16.9\%$$

이 임계값 미만에서만 반복 증류가 의미 있게 수렴한다. 레벨 $\ell$ 반복 후:

$$p^{(\ell )}\approx 35^{(3^{\ell }-1)/2}{p}_{\text{in}}^{3^{\ell }}$$

상태 주입 회로

정제된 $|T⟩$은 아래 회로를 통해 논리 T 게이트를 구현한다.

|ψ⟩ ──●────── S^m ──▶ T|ψ⟩
       │
|T⟩ ──⊕── M → m ∈ {0,1}

$|T⟩$을 CNOT 표적으로 사용하고, 측정 결과 $m$에 따라 조건부로 $S$ 게이트를 적용한다. 이 절차 전체가 클리퍼드 연산과 측정으로만 구성되어 내결함성이 유지된다.

예시·응용

자원 오버헤드 수치 계산

import numpy as np

def distilled_error(p_in, rounds=1):
    """15-to-1 프로토콜 반복 적용 후 출력 오류율"""
    p = p_in
    for _ in range(rounds):
        p = 35 * p**3
    return p

p_phys = 1e-3  # 물리적 오류율 0.1%
for r in range(1, 4):
    p_out = distilled_error(p_phys, rounds=r)
    cost = 15**r  # 필요 물리 Magic State 수(하한 추정)
    print(f"레벨 {r}: 오류율 = {p_out:.2e}, 필요 상태 수 ≥ {cost}")

레벨 1: 오류율 = 3.50e-08, 필요 상태 수 ≥ 15
레벨 2: 오류율 = 1.29e-22, 필요 상태 수 ≥ 225
레벨 3: 오류율 = 5.82e-65, 필요 상태 수 ≥ 3375

레벨 1만으로 오류율이 $10^{-8}$ 수준으로 낮아지지만, 각 단계마다 15배씩 물리 큐비트 비용이 증가한다.

실용적 의의

내결함성 양자컴퓨터 설계에서 **Magic State 공장(factory)**은 전체 칩 자원의 상당 부분을 차지한다. Google, IBM, Microsoft 등의 로드맵은 수천 개의 물리 큐비트를 T 게이트 하나를 생성하는 데 투입하는 구조를 포함한다. 이 오버헤드를 줄이기 위해 코드 스위칭(code switching), 플래그 기반 측정, 고차 증류 코드 등의 대안이 활발히 연구 중이나, 15-to-1 프로토콜은 현재 가장 성숙한 표준으로 남아 있다.

정리

Magic State 증류는 세 가지 핵심 아이디어를 결합한다: (1) 클리퍼드 군의 계산 한계 → 비클리퍼드 자원 필수, (2) 오류 정정 코드 구조를 활용한 다수 잡음 상태의 정제, (3) 상태 주입을 통한 내결함성 비클리퍼드 게이트 구현. 오류율 억제 공식 $p_{\text{out}}\approx 35p_{\text{in}}^3$와 수렴 임계값 $\approx 16.9\%$은 프로토콜의 실용성을 판단하는 핵심 지표이며, 대규모 자원 오버헤드 절감은 내결함성 양자컴퓨팅 분야의 중요한 미해결 과제로 남아 있다.