Magic State 증류의 기초 — 결함 허용 보편 양자계산의 핵심

개념 소개

클리포드 게이트(H, S, CNOT 등)는 결함 허용 양자오류정정 코드 위에서 트랜스버살 방식으로 구현할 수 있어 비교적 손쉽게 오류 내성을 확보한다. 그러나 클리포드 게이트만으로는 보편적 양자계산을 달성하지 못한다. 괴텐스만–닐(Gottesman–Knill) 정리에 따르면 클리포드 회로는 고전 컴퓨터로 다항 시간 안에 시뮬레이션할 수 있기 때문이다.

보편성을 확보하려면 클리포드 집합 밖의 게이트가 필요하며, 가장 표준적인 선택이 T 게이트다:

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

문제는 대표적인 결함 허용 코드(표면 부호, 색 부호 등)에서 T 게이트를 트랜스버살로 구현할 수 없다는 점이다. 이 딜레마를 해결하는 핵심 아이디어가 **매직 상태 증류(magic state distillation)**다.

---

핵심 원리

매직 상태의 정의

T 게이트에 대응하는 매직 상태 $|A⟩$는 다음과 같이 정의된다:

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

이 상태는 안정자(stabilizer) 형식주의 밖에 놓여 있어 '매직'이라 불린다. 블로흐 구 위에서 $|A⟩$는 팔면체 꼭짓점에 대응하며, 이는 클리포드 게이트의 궤도(orbit) 바깥에 있음을 기하학적으로 표현한다.

게이트 주입(Gate Injection)

핵심 관찰은 $|A⟩$와 클리포드 연산만으로 T 게이트를 적용할 수 있다는 것이다.

1. 입력 큐비트 $|\psi ⟩$와 보조 큐비트 $|A⟩$를 준비한다.
2. CNOT(제어: $|\psi ⟩$, 대상: $|A⟩$)을 적용한다.
3. 보조 큐비트를 Z 기저로 측정한다.
4. 측정 결과가 $|1⟩$이면 $S^{†}$ 보정 게이트를 적용한다.

이 절차 후 입력 큐비트는 $T|\psi ⟩$ 상태가 된다. T 게이트 적용 한 번에 $|A⟩$ 하나가 소비된다.

노이즈 모델과 증류 필요성

물리 큐비트에서 준비된 매직 상태는 오류율 $\epsilon$만큼 노이즈가 섞인 혼합 상태다:

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

이를 그대로 사용하면 T 게이트마다 $O(\epsilon )$ 오류가 누적된다. 증류는 저품질 복사본 여러 개를 클리포드 연산과 측정(후처리)으로 처리하여, 오류율이 대폭 낮은 소수의 고품질 복사본을 얻는 절차다.

Bravyi–Kitaev 15-to-1 프로토콜

브라비이–키타에프(Bravyi–Kitaev)가 제안한 표준 프로토콜은 [[15, 1, 3]] 양자 리드–뮬러(Reed–Muller) 부호를 활용한다.

항목	값
입력	오류율 $\epsilon$인 매직 상태 15개
출력	오류율 ${\epsilon }^{\prime }\approx 35{\epsilon }^3$인 매직 상태 1개
사용 연산	클리포드 게이트 + Z 기저 측정만

출력 오류율이 ${\epsilon }^3$에 비례하므로, $k$단계 반복 증류 후 오류율은 다음과 같이 억압된다:

$${\epsilon }^{(k)}\approx \frac{1}{35}{\left(35\epsilon \right)}^{3^k}$$

이 수렴은 $\epsilon <1/35\approx 0.029$일 때 보장된다. 초기 오류율 $1\%$에서 출발하면 두 단계만에 $10^{-12}$ 수준까지 도달한다.

---

예시·응용

아래는 반복 증류에 따른 오류율 감소를 계산하는 예시 코드다.

import numpy as np

def distill_15to1(epsilon: float) -> float:
    """15-to-1 프로토콜의 출력 오류율 근사 계산"""
    return 35.0 * epsilon**3

def simulate_distillation(epsilon_init: float, steps: int) -> None:
    eps = epsilon_init
    print(f"초기 오류율: {eps:.3e}")
    for step in range(1, steps + 1):
        eps = distill_15to1(eps)
        overhead = 15**step          # 소비된 물리 매직 상태 수
        print(f"단계 {step}: 오류율 ≈ {eps:.3e}  (소비 복사본 ≥ {overhead}개)")

simulate_distillation(epsilon_init=0.01, steps=4)

실행 결과 (근사)

초기 오류율: 1.000e-02
단계 1: 오류율 ≈ 3.500e-05  (소비 복사본 ≥ 15개)
단계 2: 오류율 ≈ 1.286e-12  (소비 복사본 ≥ 225개)
단계 3: 오류율 ≈ 6.424e-36  (소비 복사본 ≥ 3375개)
단계 4: 오류율 ≈ 8.024e-106 (소비 복사본 ≥ 50625개)

오류율은 놀랍도록 빠르게 감소하지만, 소비되는 물리 큐비트 수는 기하급수적으로 증가한다. 표면 부호 기반 대형 양자컴퓨터에서는 전체 물리 큐비트의 상당 부분이 매직 상태 팩토리(magic state factory)에 전용으로 할당된다. 이 때문에 T 게이트 수를 최소화하는 T-count 최적화가 결함 허용 컴파일러 연구의 핵심 주제로 자리잡고 있다.

---

정리

매직 상태 증류는 클리포드 게이트의 트랜스버살 구현 가능성과 T 게이트의 보편성을 분리하여 각각의 장점을 취하는 전략이다. 클리포드 연산—결함 허용적으로 쉽게 구현 가능—만으로 비클리포드 자원인 T 게이트를 간접 공급함으로써, 임의의 양자 알고리즘을 결함 허용적으로 실행하는 길을 연다. 오류율은 반복 증류로 지수적으로 억압되지만, 그에 따른 자원 오버헤드 역시 지수적으로 증가하므로, 증류 효율 향상과 T-count 감소는 오늘날 결함 허용 양자컴퓨팅의 가장 핵심적인 연구 과제로 남아 있다.