Improved Quantum Codes with Transversal T Gates

문제 정의

본 논문은 가로형(transversal) T 게이트를 지원하는 양자 CSS 코드의 점근적 패밀리(asymptotic families) 구축 문제를 다룹니다. 저자는 가로형성을 가장 강력한 의미로 정의합니다. 즉, 모든 물리적 큐비트에 물리적 T 게이트를 적용하는 것이 후속 클리포드(Clifford) 보정 없이 모든 논리적 큐비트에 대한 논리적 T 게이트를 실행하는 것을 의미합니다.

T 게이트는 결함 허용 양자 컴퓨팅(fault-tolerant quantum computation)에서 필수적이지만(클리포드 게이트와 결합하여 범용성을 가능하게 함), 가로형 T 게이트를 갖는 양자 코드를 구축하는 것은 중요한 병목 현상이었습니다. 특히 Hastings와 Haah(2017) 및 Haah(2018)의 연구는 이러한 코드들에 대해 알려진 최선의 점근적 파라미터를 확립했습니다. 그러나 이러한 파라미터들은 그 이후로 개선되지 않았습니다. 또한, 기존의 구성 방식들은 종종 다중 큐비 가로형 게이트(예: CCZ)에 의존하거나 클리포드 보정을 허용했던 반면, 본 연구는 클리포드 보정 없이 엄격하게 단일 큐비 T 게이트에 초점을 맞춥니다. 목표는 다음과 같은 영역에서 달성 가능한 코드율($k/n$)과 거리($d$)를 확장하는 것입니다:

1. 다항식 비율 및 거리 영역($k = \Omega(n^\alpha), d = \Omega(n^\beta)$)에서의 개선된 파라미터.
2. 상수 비율(constant rate) 및 성장하는 거리(growing distance)(아다항식 거리 스케일링)를 갖는 코드의 첫 번째 구성.

방법론

저자는 불리언 하이퍼큐브 상의 다운셋(downset, 아래로 닫힌 집합)에서 펀처링(punctured)된 **분할 감소 모노미얼 코드(divisible decreasing monomial codes)**를 기반으로 한 프레임워크를 개발합니다.

1. 고전적 분할성과 양자 CSS 구성:
이 구성은 "X-생성 행렬(X-generator matrix)" 형식론에 의존합니다. 가로형 T 게이트를 갖는 양자 CSS 코드를 얻기 위해, 저자는 먼저 모든 코드워드의 해밍 무게(Hamming weight)가 8로 나누어지는(8-divisible) 이진 선형 코드 $C$에서 시작합니다. 좌표 집합 $\Gamma$를 선택하여 펀처링함으로써, 저자는 논리적 행이 펀처링된 좌표에 대응하는 생성 행렬 $G$를 형성합니다. 결과적으로 생성된 양자 코드 $Q[G]$는 $C$가 8-divisible이고 펀처링이 특정 비-소멸(non-annihilation) 조건을 만족할 때 가로형 T 속성을 갖게 됩니다.

2. 감소 모노미얼 코드와 다운셋:
저자는 모노미얼 집합 $\Delta$를 사용하는 이진 모노미얼 코드 $C(\Delta)$를 활용합니다. 이들은 $\Delta$를 다운셋(만약 $A \in \Delta$이고 $B \subseteq A$이면, $B \in \Delta$임)으로 제한합니다.

• 핵심 기술적 림마(Technical Lemma): 저자는 다운셋 $\Gamma$에서 펀처링된 감소 모노미얼 코드의 거리에 대한 폐쇄형 식을 도출합니다. 만약 $\Delta$와 $\Gamma$가 모두 다운셋이라면, 거리는 다음과 같습니다:
  $$d(C(\Delta, \Gamma)) = \min_{A \in \Delta} |\{V \subseteq \bar{A} : V \in \bar{\Gamma}\}|$$
  이 공식은 이전에 펀처링된 코드에 대해 분석하기 어려웠던 정밀한 거리 분석을 가능하게 합니다.

3. 명시적 구성 (가중치 리드-뮬러 코드):
높은 코드율을 달성하기 위해, 저자는 표준 리드-뮬러 코드를 넘어 가중치 리드-뮬러(Weighted Reed-Muller, WRM) 코드로 확장합니다. 저자는 마지막 변수가 무거운 가중치 $h$를 갖는 가중치 벡터 $s = (1, 1, \dots, 1, h)$를 정의합니다.

• 이 가중치들을 기반으로 $\Delta$를 선택하고, 낮은 해밍 무게의 점들(구체적으로 처음 $m-1$개 변수의 부분집합)로 정의된 다운셋 $\Gamma$에서 펀처링함으로써, 8-divisible한 코드를 구성합니다.
• 이 명시적 구성은 상수 비율과 성장하는 거리를 달성하기 위해 파라미터를 미세 조정할 수 있게 해줍니다.

4. 보호된 점들을 이용한 무작위 구성:
다항식 비율 영역에서 파라미터를 더욱 개선하기 위해, 저자는 무작위 펀처링 전략을 도입합니다.

• 저자는 처음 $m-1$개 변수에 대한 하이퍼그래프 $H$를 정의합니다.
• 펀처링 집합 $\Gamma$는 특정 점들을 "보호"하도록 수정됩니다: 어떤 점이 하이퍼에지(hyperedge) $H$를 포함하고 있다면 그 점은 펀처링되지 않습니다.
• 이러한 보호 조치는 많은 수의 점을 펀처링할 때도 듀얼 코드의 거리(따라서 양자 코드의 거리)가 유지되도록 하여, 코드의 거리를 보존하면서 동시에 코드율을 높입니다.
• 저자는 확률적 방법을 사용하여 에지의 수가 적은 이러한 하이퍼그래프가 존재함을 증명합니다.

5. 합성(Concatenation):
무작위 구성의 경우, 저자는 다항식 영역에서의 최종적인 최적 경계에 도달하기 위해 자신들의 WRM 기반 코드를 Haah의 "분할 타워(divisible tower)" 코드와 합성합니다.

주요 기여 및 결과

1. 개선된 다항식 비율 및 거리 영역:
본 논문은 $k = \Omega(n^\alpha)$ 및 $d = \Omega(n^\beta)$인 달성 가능한 지수 $(\alpha, \beta)$의 새로운 경계를 설정합니다.

• 명시적 구성: 저자는 $\alpha > H_2(1/6)$인 영역에서 Hastings-Haah 경계를 엄격히 개선하는 새로운 함수 $\beta_{explicit}(\alpha)$를 도출합니다.
• 존재적 구성: 무작위 구성과 합성을 사용함으로써, 저자는 특히 $1/2 < \alpha < 1$ 범위에서 기존에 알려진 모든 비명시적(non-explicit) 패밀리의 경한을 개선하는 새로운 경계 $\beta_{exist}(\alpha)$를 달성합니다.

2. 최초의 상수 비율, 성장하는 거리 코드:
본 논문은 상수 비율($R > 0$)과 성장하는 거리($n \to \infty$일 때 $d \to \infty$)를 달성하는 가로형 T 게이트를 가진 최초의 명시적 양자 CSS 코드 패밀리를 제시합니다.

• 거리는 $d = \Omega(2^{(c_R + o(1))\sqrt{\log_2 n}})$로 스케일링됩니다.
• 이는 매우 중요한 돌파구인데, 이전의 가로형 T 게이트 코드들은 소멸하는 비율을 갖거나 상수의 거리를 가졌기 때문입니다.

3. 매직 상태 증류 오버헤드:
저자는 자신들이 구성한 코드에 대해 오버헤드 지수 $\gamma = \frac{\log(n/k)}{\log(d)}$가 0으로 수렴함($\gamma \to 0$)을 보여줍니다.

• 이는 Hastings와 Haah의 기존 최솟값인 $\gamma \approx 0.678$을 개선한 것입니다.
• 이 결과는 가로형 T 게이트 이후 클리포드 보정을 허용하지 않는 상황에서도 유효합니다.

4. 새로운 수학적 도구:

• 다운셋에서의 펀처링된 감소 모노미얼 코드의 거리에 대한 폐쇄형 식 (Lemma 3.2).
• 거리를 보존하기 위해 펀처링 스킴에서 점들을 "보호"하기 위한 하이퍼그래프의 참신한 적용.

의의 및 주장

본 논문은 가로형 T 게이트를 갖는 양자 코드의 달성 가능한 파라미터를 크게 확장한다고 주장하며, 이는 결함 허용 양자 컴퓨팅의 핵심 요소입니다.

• 이론적 영향: 본 연구는 2017년 이후 지속된 가로형 T 게이트 코드의 파라미터 정체 현상을 해결합니다.
• 실질적 함의: 구성된 코드들이 반드시 저밀도 패리티 체크(LDPC) 코드는 아니어서(따라서 모든 아키텍처에서 물리적 수준으로 직접 구현하기 어려울 수 있음) 저자는 이들이 매직 상태 증류를 위한 논리 수준 코드나 합성 아키텍처의 구성 요소로 사용될 수 있다고 언급합니다.
• 이전 연구와의 차별점: 다중 큐비 게이트(예: CCZ)를 사용하여 $\gamma \to 0$을 달성했던 이전 연구들과 달리, 본 연구는 단일 큐비 T 게이트를 사용하여 이를 달성합니다. 저자는 단일 큐비 가로형 게이트가 다중 큐비 가로형 게이트에서는 보장되지 않는 특성인, 더 낮은 단계의 클리포드 계층 게이트들에 대한 가로형 주소 지정(addressability)을 함의한다는 점을 강조합니다.
• 겸손함: 저자는 자신들의 명시적 구성이 무작위 대응물에 비해 상수 비율 영역에서 파라미터를 개선하지는 못한다는 점을 인정합니다(두 방식 모두 새로운 방식임). 또한 무작위 구성이 명시적 구성에 비해 상수 비율 영역을 개선하지도 못한다고 언급합니다. 또한 스테빌라이저 코드 제한을 완화하면 추가적인 개선이 가능할 수 있으나, 스테빌라이저 코드의 성숙한 결함 허용 절차 때문에 범위를 제한했음을 밝힙니다.

요약하자면, 이 연구는 상수 비율과 성장하는 거리를 달성하는 가로형 T 게이트를 가진 최초의 명시적 및 무작위 패밀리 양자 코드를 제공하며, 다항식 영역에서의 비율과 거리 사이의 트레이드오프를 크게 개선하여 매직 상태 증류의 오버헤드를 줄입니다.