기술 요약: Clifford+$\sqrt{T}$ 게이트 세트를 이용한 일반 단일 큐비트 유니터리의 근사 합성

문제 정의

결함 허용 양자 회로의 비용은 비-클리포드(non-Clifford) 게이트, 특히 $T$ 게이트($Z$축에 대한 $\pi/4$ 회전)에 의해 지배됩니다. 표준 Clifford+$T$ 게이트 세트에 대해 결정론적이고 보조 큐비트(ancilla)가 필요 없는 결정론적 합성 방식은 이미 증명 가능한 $T$-count 최적성을 달성했습니다. 그러나 $\sqrt{T}$ 게이트($\pi/8$ 회전)의 도입은 구현 가능한 연산의 격자 구조를 더욱 미세하게 만듭니다.

$\sqrt{T}$ 매직 상태(magic state)를 사용할 수 있다면 합성 비용이 낮아질 것이라고 가정되어 왔으나, 일반 유니터리에 대해 Clifford+$\sqrt{T}$ 게이트 세트를 사용하는 직접적인 결정론적, 보조 큐비트 프리(ancilla-free) 알고리즘은 존재하지 않았습니다. 기존 방법들은 일반 유니터리를 세 개의 단일 축 회전으로 분해(오일러 분해)한 뒤 각각을 독립적으로 합성하거나, 확률적 혼합(probabilistic mixing) 및 보조 큐비트를 사용하는 폴백(fallback) 방식과 같은 간접적인 접근 방식에 의존했습니다. 본 논문은 이러한 간접적인 분해나 보조 큐비트 오버헤드를 피하는 Clifford+$\sqrt{T}$를 위한 직접적인 합성 알고리즘을 제공함으로써 이 간극을 메웁니다.

방법론

수학적 프레임워크

저자들은 Morisaki 등이 Clifford+$T$를 위해 개발했던 정수 격자점 열거(integer lattice-point enumeration) 방법을 확장합니다.

• 환 확장 (Ring Extension): 합성 문제는 $Z[\omega]$ (여기서 $\omega = e^{2\pi i/8}$)의 원분 정수 환(cyclotomic integers)에서 더 큰 환인 $Z[\zeta]$ (여기서 $\zeta = e^{2\pi i/16}$)로 매핑됩니다.
• 격자 기하학: 대상 유니터리 $V$는 16차원 정수 격자에 임베딩됩니다 (Clifford+$T$의 경우 8차원). 탐색은 다음 세 가지 기하학적 조건을 만족하는 정수 벡터 $x$를 찾습니다:
  1. 노름 쉘 (Norm Shell): $\|x\|^2 = 2^k$. 이는 벡터가 특정 깊이 스케일 $k$에서 유효한 유니터리에 대응함을 보장합니다.
  2. 쌍선형 방정식 (Bilinear Equations): 세 개의 이차 제약 조건($\Phi_j(x) = 0$)은 벡터가 유니터리 행렬임을 보장합니다 (Clifford+$T$의 경우 제약 조건이 하나인 것과 대조적임).
  3. 캡 조건 (Cap Condition): $(\hat{y} \cdot x)^2 \geq \tau(k, \epsilon)$. 이는 결과 유니터리가 대상과의 다이아몬드 거리(diamond distance) $\epsilon$ 이내에 있음을 보장합니다.
• 탐색 알고리즘: 알고리즘은 LLL 격자 축소(lattice reduction)를 수행한 후, Schnorr–Euchner 열거법을 사용하여 대상 정밀도에 의해 정의된 "캡" 영역 내에서 가장 가까운 격자점을 찾습니다.

알고리즘 특징

제안된 알고리즘(Algorithm 2)은 직접적(회전 분해가 아닌 유니터리 전체를 합성)이며, 결정론적이고, 보조 큐비트가 필요 없습니다(보조 큐비트는 매직 상태 준비에만 사용되며 합성 회로 자체에는 사용되지 않음).

• 비용 최소화: 최단 깊이의 해가 최적인 Clifford+$T$의 경우와 달리, Clifford+$\sqrt{T}$의 비용 함수는 $T$ 게이트와 $\sqrt{T}$ 게이트의 혼합 비용으로 인해 깊이에 따라 비단조적(non-monotonic)입니다. 알고-리즘은 첫 번째 실행 가능한 깊이 너머의 제한된 "비용 윈도우($w$)"를 탐색하여 해당 윈도우 내에서 전역적으로 가장 저렴한 회로를 찾습니다.
• 플로어링 (Flooring): 출력값이 결코 최적의 Clifford+$T$ 솔루션보다 비싸지지 않도록 보장하기 위해, 알고리즘은 Clifford+$T$ 합성기를 병행 실행하며 $\sqrt{T}$ 결과를 이에 맞춰 하한(floor)을 설정합니다.

자원 비용 모델

비용 지표는 필요한 $T$-상태 주입(injection)의 기대값입니다.

• $T$ 게이트는 1개의 $T$-상태를 소모합니다.
• 매직 상태 촉매(catalysis)를 통해 구현되는 $\sqrt{T}$ 게이트(Gidney와 Fowler의 방식 준수)는 (일회성 촉매 준비 비용을 분할 상환한 후) 기대적으로 3개의 $T$-상태를 소모합니다.
• 총 비용: $n_T + 3n_{\sqrt{T}}$.

주요 기여

1. 직접 합성 알고리즘: Clifford+$\sqrt{T}$ 게이트 세트에 대해 일반 단일 큐비트 유니터리를 위한 최초의 결정론적, 보조 큐비트 프리 근사 합성 알고리즘을 제공합니다.
2. 격자 방법의 확장: Morisaki 등의 $Z[\omega]$ 기반 격자 열거 기술을 16차원 및 추가적인 쌍선형 제약 조건을 처리하는 $Z[\zeta]$로 성공적으로 일반화했습니다.
3. 오픈 소스 구현: $\epsilon = 10^{-8}$의 정밀도까지 몇 초 만에 회로를 합성할 수 있는 라이브러리인 cyclosynth를 공개합니다.
4. 경험적 비용 감소: 직접적인 Clifford+$\sqrt{T}$ 합성이 간접적인 방법(오일러 분해) 및 직접적인 Clifford+$T$ 합성보다 훨씬 낮은 비-클리포드 비용을 생성함을 입증했습니다.

결과

비용 스케일링

Haar-무작위(Haar-random) 타겟에 대해, 합성된 회로의 비-클리포드 비용은 다음과 같이 스케일링됩니다:

• Clifford+$\sqrt{T}$: $2.4 \log_2(1/\epsilon)$
• Clifford+$T$ (최적): $3.0 \log_2(1/\epsilon)$
• 간접 Clifford+$T$ (오일러): $\sim 9 \log_2(1/\epsilon)$

이는 최적의 Clifford+$T$ 회로와 비교했을 때 20%의 비용 스케일링 감소를 나타내며, 간접 분해 방법과 비교하면 매우 큰 감소를 보여줍니다.

경험적 성능

• 비용 감소: 테스트된 타겟의 99.4%에서 100%에 대해 Clifford+$\sqrt{T}$ 회로가 최적의 Clifford+$T$ 회로보다 엄격히 저렴합니다. 중간 상대 비용 감소율은 약 25% (중앙값 $\rho \approx 0.73$)입니다.
• 실행 시간: 16차원 탐색으로 인해 Clifford+$T$보다 계산 집약적입니다. $\epsilon=10^{-3}$일 때 0.9초, $\epsilon=10^{-8}$일 때 7.0초의 중앙 실행 시간을 보이며, 이는 Clifford+$T$의 밀리초 단위 실행 시간과 대조됩니다. 그러나 저자들은 합성이 오프라인 프로세스이므로 게이트 비용이 주요 지표라고 언급합니다.
• 강건성 (Robustness): $\sqrt{T}$ 게이트 비용이 약 4.0에서 5.3 $T$-상태 사이의 교차점 아래에 있는 한, 이 이점은 지속됩니다. 촉매를 통한 비용이 3 $T$-상태이므로, 이 접근 방식은 여전히 유리합니다.

의의 및 주장

본 논문은 유니터리를 단일 축 회전으로 분해하는 오버헤드를 피하는, Clifford+$\sqrt{T}$를 위한 최초의 직접적인 근사 합성 솔루션을 제공한다고 주장합니다. 저자들은 자신들의 방법이 결정론적이고 보조 큐비트가 필요 없다는 점을 강조하며, 이는 보조 큐비트나 측정이 불가능하거나 정적인 회로가 필요한 시나리오에서 가장 요구 사항이 적은 옵션임을 의미합니다.

저자들은 최적성에 대해 겸허한 태도를 취합니다:

• 그들은 자신들의 회로가 Clifford+$\sqrt{T}$ 게이트 세트에 대한 정보 이론적 하한을 달려준다고 증명하지는 않습니다. 왜냐면 $Z[\omega]$에 기반한 Clifford+$T$의 알려진 $T$-count 하한이 $Z[\zeta]$로 전이된다는 것이 아직 증명되지 않았기 때문입니다.
• 그러나 그들의 비용 스케일링($2.4 \log_2(1/\epsilon)$)이 Kliuchnikov 등이 $z$-회전에 대해 발견한 파워-비용-최적(power-cost-optimal) 스케일링과 일치한다는 점을 들어, 탐색이 최적에 가깝다고 언급합니다.
• 또한 확률적 방법(채널 혼합)이나 보조 큐비트를 사용하는 폴백 방식이 더 낮은 기대 비용을 달성할 수는 있지만, 이는 실행 보장 및 자원 요구 사항 측면에서의 트레이드오프를 수반한다는 점을 인정합니다.

요약하자면, 본 연구는 Clifford+$\sqrt{T}$의 더 미세한 격자를 활용하고 직접 합성 알고리즘을 결함함으로써, 현실적인 매직 상태 비용 모델 하에서 Clifford+$T$의 대응물보다 일관되게 저렴한 게이트 시퀀스를 생성할 수 있음을 확립했습니다.