Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

기술 요약: 무작위 매칭을 이용한 얕은 클리포드 회로로부터의 우수한 안정화 부호(Stabilizer Codes)

문제 정의
얕은 인코딩 회로를 사용하여 강력한 파라미터(높은 비율과 선형 거리)를 가진 양자 오류 정정 부호(QECC)를 구축하는 것은 결함 허용 양자 컴퓨팅(fault-tolerant quantum computation)의 근본적인 과제이다. CSS 구성 및 $\mathbb{F}_4$ 상의 안정화 부호와 같은 확률적 존재성 결과는 점근적으로 우수한 부호의 존재를 보장하지만, 이들이 낮은 회로 깊이나 제한된 게이트 집합을 가진 인코더를 본질적으로 제공하지는 않는다. Brown과 Fawzi [BF13b]는 전방향 연결성(all-to-all connectivity)과 전체 2-큐비트 클리포드 군($C_2$)을 사용하는 무작위 클리포드 회로가 양자 길버트-바르샤모프(Gilbert-Varshamov, GV) 비율-거리 트레이드오프를 달성함을 입증했으나, 이는 $O(\log^3 n)$의 회로 깊이를 요구했다. 핵심적인 미해결 과제는 추가적인 워크 어닐라(work ancillas) 없이 더 제한된 하드웨어 친화적 게이트 집합(구체적으로 CNOT, Hadamard, Phase 게이트와 같은 기초적인 클리포드 생성기)을 사용하여 훨씬 더 얕은 깊이($O(\log n)$)로 이 최적의 트레이드오프를 달ึง할 수 있는지 여부였다.

방법론
저자들은 "무작위 매칭 회로(random matching circuit)" 아키텍처를 제안하고 분석한다. 인코딩 회로는 $T$개의 독립적인 층(layer)으로 구성된다. 각 층에서:

1. 무작위 매칭: $n$개의 물리적 큐비트는 균등 무작위 완전 매칭(uniformly random perfect matching)을 통해 쌍을 이룬다.
2. 게이트 적용: 각 쌍에 무작위 2-큐비트 클리포드 게이트가 적용된다.
3. 게이트 분포: 게이트는 2-큐비트 클리포드 군 $C_2$ 상의 분포 $p_2$에서 추출된다. 저자들은 $p_2$에 대해 세 가지 정규성 조건을 부과한다:
   • 쌍방 불변성(Bi-invariance): 비항등 단일 큐비트 파울리(부호 제외)에 대해 추이적(transitive)으로 작용하는 로컬 클리포드 부분군에 의한 좌측 및 우측 곱셈에 대한 불변성.
   • 양의 얽힘(Positive Entanglement): 분포가 적어도 하나의 얽힘 게이트(entangling gate)에 대해 양의 확률을 할당함.
   • 가역성(Reversibility): 분포가 역원을 취하는 것에 대해 불변임 ($U \sim p_2 \implies U^\dagger \sim p_2$).

주요 예시는 "로컬로 트월링된 CNOT(locally twirled CNOT)" 분포이며, 여기서 CNOT 게이트는 독립적이고 균등하게 무작위적인 단일 큐비트 클리포드(또는 특정 순환 부분군 $\{I, HS, (HS)^2\}$)에 의해 공액(conjugate)된다.

분석 프레임워크
부호의 특성을 증명하기 위해, 저자들은 무작위 회로의 2차 모멘트 역학(second-moment dynamics)을 분석한다.

1. 2차 모멘트 연산자: 동일한 파울리 문자열 쌍에 작용하는 2차 모한트 연산자 $M_{circ}$를 정의한다. $p_2$의 쌍방 불변성 덕분에, 이 연산자의 역학은 특정 파울리 유형이 아니라 이진 서포트 문자열(binary support string, 즉 비항등 파울리의 위치)에만 의존한다.
2. 마르코프 체인 축소: 서포트 문자열의 진화는 길이 $n$인 이진 문자열 상의 가역 마르코프 체인 $Q_0$로 모델링된다. 이 체인은 다시 해밍 무게(Hamming weight) $w \in [n]$ 상의 "무게 체인(weight chain)" $P$로 축소된다.
3. 정상 분포: 무게 체인의 정상 분포는 $\pi(w) = \binom{n}{w} 3^w / (4^n - 1)$로 나타나며, 이는 $w \approx 3n/4$에서 정점을 찍는다.
4. 충돌 시간(Hitting Time) 분석: 증명의 핵심은 무게 체인이 "선형 무게" 영역에 도달하고, 이후 $3n/4$ 주변의 좁은 구간으로 수렴하는 충돌 시간을 바운딩하는 것이다.
   • 저중량 영역(Low-Weight Regime): 마팅게일 집중 부등식(Azuma-Hoeffding)과 드리프트 분석을 사용하여, 저중량에서 시작할 때 무게가 지수적으로 빠르게 성장하여 높은 확률로 $O(\log n)$ 단계 내에 선형 무게($O(n)$)에 도달함을 보여준다.
   • 정상성으로의 수렴: 선형 무게 영역에 도달하면, 체인은 상수 단계 내에 $3n/4$ 근처로 빠르게 수렴한다.
   • 가역성: 체인의 가역성은 체인이 저중량 영역으로 돌아갈 확률(이는 저중량 오류 연산자에 해당함)을 바운딩할 수 있게 하여, 코드 거리가 높음을 보장한다.

주요 기여 및 결과

1. 최적의 깊이: 저자들은 무작위 매칭 회로가 $O(\log n)$ 깊이로 양자 길버트-바브라쇼프 비율-거리 트레이드오프를 달성함을 증명한다. 이는 Brown과 Fawzi [BF13b]의 $O(\log^3 n)$ 깊이를 개선하며, 선형 거리를 갖는 인코더의 이론적 라이트 콘(light-cone) 하한과 일치한다.
2. 제한된 게이트 집합: 이 결과는 세 가지 정규성 조건을 만족하는 광범위한 게이트 분포에 대해 유효하다. 결정적으로, 이는 얽힘 게이트가 로컬 무작위 클리포드 트월링이 결합된 CNOT뿐인 경우를 포함한다. 이는 기초적인 클리포드 생성기의 충분성에 관한 의문에 답한다.
3. 형식적 보장: 임의의 고정된 $\delta > 0$와 충분히 큰 $n$에 대하여, 비율 $k/n$이 다음을 만족하면:
   $$\frac{k}{n} < 1 - H\left(\frac{d}{n}\right) - \frac{d}{n}\log_2 3 - \delta$$
   그렇다면 $O(\log n)$ 깊이의 무작위 매칭 회로는 적어도 $d+1$의 거리를 갖는 $[n, k]$ 안정화 부호를 적어도 $1 - n^{-m} - 2^{-\Omega_\delta(n)}$의 확률로 정의한다.
4. 게이트 수 최적성: 이 구성은 $O(n \log n)$ 개의 2-큐비트 게이트를 사용한다. 저자들은 라이트 콘 논증(Proposition A.2)을 통해, 독립 무작위 매칭 모델 내에서 상수 성공 확률로 선형 거리를 달성하려면 $\Omega(n \log n)$ 개의 게이트가 필요함을 증명하여 자신들의 게이트 수가 최적임을 입증한다.

의의
본 논문은 전방향 아키텍처에서 오직 기초적이고 하드웨어 친화적인 게이트(구체적으로 로컬 트월링이 포함된 CNOT)만을 사용하여 $O(\log n)$의 최적 깊이로 양자 길버트-바브라쇼프 경계에 도달할 수 있음을 보여준다. 이는 확률적 존재성 결과와 실제적인 인코더 복잡도 사이의 간극을 메우며, 매우 구조화되고 얕은 무작위 회로가 높은 거리의 안정화 부호를 생성하는 데 충분함을 보여준다. 이 연구는 전체 2-큐비트 클리포드 군에 대한 완전한 무작위성이 필요한 것이 아니라, 파울리 확산(Pauli spreading)을 유도하기 위해 특정 정규성 조건(쌍방 불변성, 얽힘, 가역성)이 충분하다는 것을 명확히 한다.

한계 및 미해결 과제
저자들은 자신들의 결과가 결정론적인 명시적 패밀리가 아닌 무작위 앙상블에 대한 존재성 증명을 제공한다는 점을 언급한다. 매칭 시퀀스와 트월링 과정을 탈무작위화(derandomizing)하는 것은 여전히 열린 방향이다. 또한, 이 구성이 높은 거리의 코드를 생성하지만 효율적인 디코딩 알고리즘을 제공하지는 않으므로, 이 앙상블을 위한 효율적인 디코더를 설계하는 것은 향-후 과제로 남아 있다. 아울러, 정규성 조건(특히 쌍방 불변성과 가역성)은 증명에는 충분하지만, 좋은 코드의 존재를 위한 엄격한 필요조건은 아닐 수 있으며, 이는 가정의 추가적인 완화 가능성을 시사한다.