Quantum group codes for non-Clifford logic: enhanced decoding, addressability and parallelizability

기술 요약: 비-클리포드 로직을 위한 양자 그룹 코드

문제 정의
현재의 결함 허용 양자 컴퓨팅(fault-tolerant quantum computation) 방식은 상당한 공간 및 시간 오버헤드로 인해 실용적인 양자 컴퓨터 구현을 저해하고 있습니다. 트랜스버설 게이트(transversal gates)를 지원하는 칼더뱅크-쇼어-스티인(Calderbank-Shor-Steane, CSS) 코드는 결함 허용을 위한 경로를 제시하지만, 기존의 구성 방식은 다음과 같은 두 가지 주요 한계에 직면해 있습니다:

1. 디코딩 복잡도: 매직 상태 증류(Magic State Distillation, MSD)에 필수적인 비-클리포드 트랜스버설 게이트를 지원하는 최첨단 양자 대수 기하(Algebraic Geometry, AG) 코드는 $O(n^3)$의 세제곱 시간 복잡도를 갖는 디코딩 알고리즘에 의존합니다. 이러한 높은 복잡도는 MSD 프로토콜로 전파되어 그 효율성을 제한합니다.
2. 주소 지정 가능성 및 병렬화 가능성: 비-클리포드 트랜스버설 게이트를 갖는 기존 코드들은 일반적으로 모든 물리적 큐딧(qudit)에 동시에 작용하는 글로벌 연산을 수행합니다. 이러한 "주소 지정 불가능성"(특정 논리 큐딧의 부분 집합을 타겟팅하는 능력의 부재)은 알고리즘의 유연성을 제한합니다. 또한, 최근 주소 지정 가능한 게이트를 가진 코드들의 존재가 밝혀졌으나, 이러한 구성은 매우 특정한 전이적(transitive) AG 코드 가문에 의존하며, 이 게이트들의 병렬화 가능성을 높이기 위해 회로 깊이를 줄이는 추가적인 최적화가 필요합니다.

방법론
저자들은 특정 곱셈 성질을 가진 클래식 **준 그룹 코드(quasi group codes)**로부터 유도된 양자 그룹 코드에 기반한 프레임워크를 제안합니다. 이 방법론은 세 가지 주요 단계로 진행됩니다:

1. 프레임워크 정의 (양자 그룹 코드):
   저자들은 밑바탕이 되는 클래식 코드($C_0$ 및 $C_1$)가 준-$G$ 코드(group algebra $F_q[G]$의 우측 아이디얼과 동형인 코드)인 양자 CSS 코드의 클래스를 정의합니다. quotient map에 대한 $G$-모듈 호모모피즘 섹션의 존재를 보장함으로써, 이 양자 코드들이 병렬화 가능하고 주소 지정 가능한 트랜스버설 멀티-컨트롤-Z ($C_{m-1}Z$) 게이트를 수용할 수 있는 조건을 확립합니다.

   • 핵심 메커니즘: 그룹 작용(group action)을 통해 논리 큐딧의 특정 궤도(orbit)에 대해 로직 게이트를 구현할 수 있게 하는 변조 함수(modulation functions)를 구축할 수 있습니다.

2. 리프팅(Lifting)을 통한 코드 구성:
   좋은 파라미터와 효율적인 디코딩을 갖는 코드를 생성하기 위해, 저자들은 대수적 수체론(class field theory, 특히 [CG26])에 기반한 리프팅 절차를 사용합니다.

   • 먼저 $m$-곱셈 성질을 만족하는 $F_q$ 상의 우수한 클래식 AG 코드 $C$에서 시작합니다.
   • 밑바탕이 되는 함수체의 비분기 아벨 확장(unramified abelian extension)을 구축하여, $F_{q^2}$ 상의 새로운 코드 $\tilde{C}$를 생성합니다.
   • 이 리프팅 과정은 새로운 코드에 큰 아벨 순열 자기 동형군(automorphism group) $G$를 부여하여, 이를 $F_{q^2}[G]$의 자유 모듈(free module)로 만듭니다. 결정적으로, 이 리프팅은 트랜스버설 게이트에 필요한 $m$-곱셈 성질을 보존합니다.

3. 디코딩 최적화:
   저자들은 리프팅된 코드의 모듈 구조를 활용합니다. 표준 AG 코드가 세제곱 시간 디코딩을 요구하는 것과 달리, 자유 모듈 구조를 통해 디코딩 알고리즘을 그룹 대수 상의 빠른 행렬 곱셈을 활용하도록 적응시킬 수 있습니다. 이는 준-이차 시간 디코더($O(n^2 \cdot \text{polylog}(n))$)와 선형 디코딩 반경을 결과로 가져옵니다.

주요 기여 및 결과

• 정리 1.1 (코드 가문): 본 논문은 두 가지 $q$-차원 큐딧 양자 그룹 코드($q=t^4$) 가문을 구축합니다:

  1. 완전 주소 지정 가능 가문: 파라미터가 $[[n, \Theta(n/\log n), \Theta(n)]]_q$인 코드입니다. 이들은 완전히 주소 지정 가능한 트랜스버설 $C_{\tilde{m}-1}Z$ 게이트를 수용합니다. $m$개의 코드 블록을 포함하는 논리 회로의 깊이는 $O(k^{\tilde{m}-1})$로 상한이 정해집니다.
  2. 고율(High-Rate) 가문: 파라미터가 $[[n, \Theta(n), \Theta(n)]]_q$인 코드입니다. 이들은 글로벌 트랜스버설 $C_{\tilde{m}}Z$ 게이트와 $\Theta(\log n)$개의 궤도에 걸친 궤도별 주소 지정 가능한 $C_{\tilde{m}-1}Z$ 게이트를 수용합니다.
  • 두 경우 모두, 선형 디코딩 반경을 가지는 $O(n^2 \cdot \text{polylog}(n))$ 시간 디코더를 지원하며, 이는 기존의 $O(n^3)$ AG 기반 구성들에 비해 현저한 개선입니다.

• 따름정리 1.2 (매직 상태 증류): 고율 가문을 매직 상태 증류(MSD) 프로토콜에 적용함으로써, 저자들은 $O(n^2 \cdot \text{polylog}(n))$ 시간 복잡도를 갖는 큐비트 CCZ-매직 상태를 위한 상수 오버헤드 증류 프로토콜의 존재를 입증합니다. 이는 기존의 $O(n^3)$ 프로토콜과 비교했을 때 시간 복잡도의 거의 선형적인 감소를 나타냅니다.

• 병렬화 가능성: 본 연구는 논리적 멀티-컨트롤-Z 회로가 높은 수준으로 병렬화될 수 있음을 확립합니다. 조밀한(dense) 회로의 경우, 최소 깊이는 $O(k^{m-1})$로 제한되며, 이는 해당 회로들에 대해 최적입니다.

의의
본 논문은 자신의 연구가 결함 허용 양자 컴퓨팅의 핵심적인 병목 현상을 해결한다고 주장합니다:

1. 효율성: 디코딩 복잡도를 세제곱에서 준-이차 시간으로 줄임으로써, MSD 프로토콜의 시간 오버헤드를 실질적으로 감소시켜 실용적인 결함 허용 컴퓨팅의 실현 가능성을 높였습니다.
2. 유연성: 주소 지정 및 병렬화 가능한 비-클리포드 게이트의 도입은 글로벌 연산을 넘어 더 정밀한 논리 큐딧 제어를 가능하게 합니다. 이는 글로벌 얽힘(entanglement)을 요구하지 않는 알고리즘 및 회로 컴파일에 필수적입니다.
3. 일반화: 이 구성은 이전 연구에서 사용된 특정한 전이적 AG 코드를 넘어, 큰 아벨 자기 동형군을 가진 더 넓은 범위의 리프팅된 AG 코드 가문을 활용합니다. 이는 트랜스버설 비-클리포드 게이트를 갖는 양자 코드를 설계하기 위한 더욱 다각적인 도구 상자를 제공합니다.

저자들은 자신의 결과가 이론적 구성과 기존의 리프팅 기법으로부터 도출되었음을 강조하며, 이러한 변환이 트랜스버설 비-클리포드 게이트에 필요한 속성을 유지하면서도 디코딩 효율성을 개선함을 검증하였습니다.