Pair-Partition Constructions for CPM-Based Quantum LDPC Codes

기술 요약: CPM 기반 양자 LDPC 코드를 위한 쌍-분할 구성(Pair-Partition Constructions)

문제 정의
본 논문은 순환 치환 행렬(Circulant Permutation Matrices, CPM)을 사용하여 이진 칼더뱅-쇼어-스틴(Calderbank–Shor–Steane, CSS) 양자 저밀도 패리티 검사(LDPC) 코드를 구성하는 문제를 다룬다. 준주기적(Quasi-cyclic, QC) LDPC 행렬은 압축된 표현 방식을 제공하지만, CSS 직교 조건($H_X H_Z^T = 0$)을 보장하는 동시에 짧은 사이클(특히 girth $\ge 6$를 보장하기 위한 4-사이클)을 피하고 코드 거리를 최대화하는 것은 도전적인 설계 문제이다. 기존의 대수적 구성들은 특정 구조나 아핀 치환(affine permutations)에 의존하는 경우가 많으나, 본 연구는 명시적인 고율(high-rate) 예시와 검증된 구조적 특성을 제공하기 위해 엄격하게 CPM 하위 클래스에 집중한다.

방법론
저자들은 열 가중치 $J$, 행 가중치 $L$, 그리고 소수 리프트 크기 $P$에 의해 매개변수화된 구성을 제안한다. 핵심 혁신은 CSS 직교성을 대수적으로 강제하기 위한 **쌍-분할 배열(pair-partition array)**의 사용이다.

1. 쌍-분할 프레임워크:

   • $J \times J$ 배열인 쌍-분할 배열 $(M_{ij})$가 정의되며, 각 엔트리는 $L$개의 열 유형을 $L/2$개의 순서 없는 쌍으로 분할한다.
   • 혼합 차이 방정식(Mixed-Difference Equations): 모든 쌍 $(u, v) \in M_{ij}$에 대하여, 유한체 $\mathbb{F}_P$ 상의 지수 배열 $(e_{j\ell})$ 및 $(d_{j\ell})$에 대해 다음과 같은 선형 방정식이 부과된다:
     $$d_{j,u} - e_{i,u} = d_{j,v} - e_{i,v}$$
     이는 각 쌍의 양 끝단에 대한 "혼합 차이(mixed differences)"가 동일하도록 강제한다.
   • CSS 직교성: 보조정리 1(Lemma 1)은 이러한 쌍 결합 제약 조건이 $H_X H_Z^T = 0$을 보장함을 증명한다. 이 논리는 블록 행 쌍에 대해, 쌍을 이룬 열 유형들로부터의 기여가 동일한 CPM이 되어 $\mathbb{F}_2$에서 상쇄된다는 사실에 기초한다.

2. 구조적 제약 조건:

   • 혼합-독립성(Mixed-Distinctness): X-체크와 Z-체크가 0개 또는 정확히 2개의 위치에서만 교차하도록 하여(가중치-1 논리 연산자를 방지하고 교차를 제어함), 쌍으로부터 유도된 혼합 값 $\delta_{ij}(p)$가 각 셀 내에서 서로 달라야 한다.
   • Girth 제약 조건: 테너 그래프(Tanner graph)의 girth가 최소 6이 되도록 하기 위해, $H_X$와 $H_Z$의 지수 배열에 대해 표준적인 타입 수준 4-사이클 테스트가 적용된다.

3. 탐색 및 검증 파이프라인:

   • 후보 생성: 쌍-분할 방정식에 의해 정의된 선형 시스템을 풀어 지수 배열의 해 공간을 찾는다. 후보들은 이 해 공간에서 샘플링된다.
   • 스크리닝: 후보들은 혼합-독립성 조건과 4-사이클 테스트를 기준으로 필터링된다. "금지된 패턴 뱅크(forbidden-pattern bank)"는 낮은 가중치의 논리 연산자를 생성할 가능성이 높은 할당을 폐기하기 위한 휴리스틱 사전 필터로 사용된다.
   • 거리 검증: 생존한 후보들에 대해, 저자들은 두 가지 엄격한 검사를 수행한다:
     • 하한(Lower Bound): 연결 성분 분해(connected component decomposition)와 만족되지 않은 체크 노드에 기반한 가지치기(pruning)를 활용하여, 특정 가중치 $W$까지의 모든 비-스테빌라이저 제로-신드롬 벡터를 배제하는 전수 조사 기반의 컴퓨터 보조 탐색을 수행한다.
     • 상한(Upper Bound): 정확한 거리를 설정하기 위해 명시적인 비-스테빌라이저 제로-신드롬 벡터(witnesses)를 식별한다. 가장 큰 인스턴스의 경우, 인증된 하한값만을 보고한다.

주요 기여

• 대수적 구성: 본 논문은 주어진 쌍-분할을 CSS 직교성을 보장하는 선형 쌍-차이 시스템으로 변환하는 방법을 공식화한다.
• 압축된 탐색 공간: 직교성 방정식의 해 공간에 동일-타입 4-사이클 부등식을 부과함으로써, 저자들은 거리 유도 필터와 결합될 수 있는 CPM을 위한 압축된 탐색 공간을 정의한다.
• 정확한 거리 검증: 점근적 경계나 휴리스틱 추정에 의존하는 많은 연구와 달리, 본 논문은 전수 조사 기반의 저가중치 배제와 명시적 witness 생성을 통해 특정 리프트 행렬에 대한 정확한 거리를 제공한다.
• 고율 예시: 본 구성은 최소 거리 $d$가 행 가중치 $L$을 초과하는($d > L$) 사례를 생성하며, 이는 양자 LDPC 코드에서 바람직한 속성이다.

결과
저자들은 열 가중치($J=3$ 및 $J=4$)와 리프트 크기($P$)가 다른, girth 6을 가진 12개의 특정 CPM 기반 CSS 인스턴스를 보고한다. 주목할 만한 결과는 다음과 같다:

• 열 가중치 4 ($J=4$):
  • $[[276, 98, 14]]$ (율 0.355).
  • $[[574, 252, 18]]$ (율 0.439).
  • $[[944, 478, \ge 20]]$ (율 0.506, 인증된 하한만 보고됨).
• 열 가중치 3 ($J=3$):
  • $[[472, 122, 14]]$ 및 $[[488, 126, 14]]$.
• 검증: 처음 11개 인스턴스의 경우, $d-2$까지의 비-스테빌라이저 벡터를 배제하고 가중치 $d$인 명시적 witness를 제공함으로써 정확한 거리를 확립하였다. 마지막 인스턴스($[[944, 478, \ge 20]]$)는 상한 witness가 주장되지 않았으므로 20의 인증된 하한값으로 기록되었다.

의의 및 주장
본 논문은 양자 LDPC 코드 설계에 대한 구조적 기여로서 자리매김한다. 저자들은 디코더를 최적화하거나 새로운 디코딩 알고리즘을 제안하는 것이 아니라, 기존 디코더(예: 순서 통계 후처리(ordered-statistics postprocessing)를 사용하는 신념 전파(belief propagation))와 함께 사용할 수 있는 검증된 파라미터를 가진 구조적 인스턴스를 제공한다는 점을 명시적으로 밝힌다.

그 의의는 순수하게 대수적인 CPM 프레임워크를 사용하여 큰 girth와 검증된 거리를 가진 명시적인 고율 양자 코드를 생성할 수 있는 능력에 있다. 저자들은 거리 주장이 대수적 구성과는 별개이며, 파라미터를 검증하기 위해 컴퓨터 보조 전수 조사와 명시적 witness에 의존하고 있음을 강조한다. 본 연구는 엄격한 구조적 제약(girth 6, CSS 직교성)을 충족하면서 경쟁력 있는 율과 거리를 제공하는 구체적이고 검증된 코드 인스턴스의 저장소 역할을 한다.