Quantum Bicycle LDPC Codes with High $kd^2/n$ from Divisor-Driven Search

기술 요약: 디비저 드리븐 서치(Divisor-Driven Search)를 통한 높은 $kd^2/n$ 값을 갖는 양자 바이시클 LDPC 코드

문제 정의
양자 저밀도 패리티 검사(LDPC) 코드, 특히 바이시클(bicycle) 계열(두 개의 블록 순환 코드)은 큐비트 오버헤드를 줄이면서도 높은 오류 임계값을 유지할 수 있어 표면 코드(surface code)의 유망한 대안으로 꼽힌다. 그러나 이러한 코드 설계는 역사적으로 군 대수적 정식화(예: 일반화된 바이시클 군 대수 코드, 두 블록 군 대수 코드)에 의존해 왔다. 이러한 프레임워크에서 탐색 공간은 군-부분군 쌍과 서포트 집합(support sets)에 의해 인덱싱되는데, 이는 간접적이며 가지치기(pruning)가 어렵다. 결정적으로, 핵심적인 양자 파라미터인 차원($k$)과 거리($d$)는 거대한 패리티 검사 행렬을 구축하기 전에는 대수적으로 결정될 수 없다. 이는 모든 후보에 대해 비용이 많이 드는 행렬 연산을 필요로 하며, 특히 높은 차원 $k$를 가진 파라미터 영역의 탐색을 제한한다.

방법론
저자들은 바이시클 코드 구성을 순환형 케이스(기저 군이 $G = \mathbb{Z}_l$인 경우)에 대해 전체적으로 심플렉틱 다항식 도메인 내에서 재정식화한다. 저자들은 군 대수 $\mathbb{F}_2[\mathbb{Z}_l]$를 몫 환(quotient ring) $R = \mathbb{F}_2[x]/(x^l - 1)$로 매핑함으로써 다음과 같은 대수적 프레임워크를 확립한다:

1. 자기 직교성(Self-Orthogonality): CSS 직교 조건($H_X H_Z^T = 0$)은 다항식 환의 가환성(commutativity)의 자동적인 결과가 되어, 명시적인 가환성 체크를 제거한다.
2. 차원 제어: 양자 차원 $k$는 다항식 최대 공약수(gcd)를 통해 정확하게 유도된다: $k = 2 \deg \gcd(a(x), b(x), x^l - 1)$. 이를 통해 행렬을 구축하기 전에 차원을 기준으로 후보를 사전 필터링할 수 있다.
3. 거리 인증(Distance Certification): 최소 거리는 스태빌라이저 코드를 $\mathbb{F}_4$ 상의 가법 코드(additive codes)로 매핑하는 칼더뱅크 대응(Calderbank correspondence)을 사용하여 정확하게 계산된다. 저자들은 스태빌라이저 이미지를 제외하기 위해 "두 개의 커널(two-kernel)" 계산을 구현하여, 거리가 단순히 체크 가중치가 아닌 실제 양자 거리를 반영하도록 보장한다.

저자들은 디비저 드리븐 서치 알고리즘(Algorithm 1)을 제안한다. 무작위 샘플링 대신, 이 탐색은 타겟 디비저(target divisor) $g(x)$에 저가중치 "리프트(lift)" 다항식 $u(x)$와 $v(x)$를 곱함으로써 다항식 $a(x)$와 $b(x)$를 구성한다. 이러한 구조는 특정 차원 범위($k \approx 2 \deg g$)를 보장하며 스태빌라이저 행 가중치를 낮게 유지한다(LDPC 특성). 이 파이프라인은 정확한 거리 계산에 앞서 대수적 필터(gcd 체크, 인볼루션 대칭성 체크)를 적용한다.

주요 기여

1. 다항식 프레임워크: 본 논문은 순환 군의 경우, 바이시클 구성이 자기 직교성이 자동적이고 차원이 단순한 gcd 계산인 다항식 환으로 축소됨을 보여준다. 이는 코드 탐색을 행렬 기반의 열거에서 대수적으로 사전 필터링되는 과정으로 변환한다.
2. 고성능 코드 발견: 이 프레임워크를 사용하여 저자들은 경쟁력 있는 성능 지표($kd^2/n$)를 가진 코드 패밀리를 발견했다. 특히, 저자들은 $kd^2/n = 14.85$인 $[[66, 20, 7]]_2$ 코드를 찾아냈다. 이는 블록 길이가 절반 미만임에도 불구하고 바이베리에이트 바이시클 코드(bivariate bicycle code)인 $[[144, 12, 12]]_2$ ($kd^2/n = 12$)보다 우수한 성능을 보인다. 다른 주목할 만한 발견으로는 $[[46, 2, 8]]_2$, $[[66, 2, 9]]_2$ 및 $n=90$에서 차원이 $k=20$에 달하는 코드들이 있다.
3. 경계 정리(Boundary Theorem): 저자들은 분석을 $n=48$에서의 가중치-8 대칭 코셋-2BGA 패밀리로 확장한다. 저자들은 이 특정 패밀리에서 거리 $d=5$가 랭크 퇴화(rank degeneracy, $k=9$)를 강제함을 증명하여, 이 패밀리 내에서 $[[48, 10, 5]]_2$ 코드가 존재할 수 없음을 밝혀냈다. 반대로, 저자들은 최소 48-요소 군을 사용하여 $[[48, 10, 6]]_2$ 코드를 구축함으로써, 기존에 72-요소 군이 필요했던 구현을 개선했다.

결과

• 코드 파라미터: 탐색을 통해 짧은 코드들인 $[[42, 12, 4]]_2$ 및 $[[62, 12, 4]]_2$를 회복하였으며, $n \in \{46, 50, 54, 66, 70, 78, 90, 170\}$에 대한 포괄적인 코드 테이블을 생성했다. $[[66, 20, 7]]_2$ 코드는 고차원, 중간 거리 영역에서 중요한 돌파구를 의미하며, 이 영역은 기존의 군론적 탐색에 의해 과소 샘플링되었던 영역이다.
• 디코딩 성능: 저자들은 코드 용량 노이즈 하에서 BP-OSD(Belief Propagation with Ordered Statistics Decoding)를 사용하여 선택된 저가중치 코드들을 벤치마킹했다. 결과는 명확한 워터폴(waterfall) 영역을 보여준다. 참조용 바이베리에이트 바이시클 코드(예: $[[144, 12, 12]]_2$)는 더 낮은 체크 가중치($w=6$)로 인해 더 가파른 서브스레숄드(sub-threshold) 기울기를 보이는 반면, 새로운 코드들은 경쟁력 있는 논리적 오류율을 보여주며, 일부(예: $[[170, 10, 8]]_2$)는 물리적 오류율이 2%에 도달할 때까지 논리적 실패가 나타나지 않았다.
• 구조적 통찰: 본 논문은 다항식 gcd에 기반한 차원 공식이 코셋 작용(coset action)을 포함하는 더 일반적인 랭크 공식의 "결함 제로(defect-zero)" 케이스임을 식별한다. $n=48$ 분석은 랭크 퇴화가 대칭 코셋 패밀리에서 거리 $d=5$와 구체적으로 연결되어 있음을 보여주며, 이는 다항식 프레임워크가 포착하는 현상과 진정한 코셋 이론적 분석이 필요한 현상을 구분한다.

의의
본 논문은 전통적인 군론적 탐색의 범위를 넘어서는 바이시클 유형의 양자 LDPC 코드로 가는 체계적인 경로를 제시한다고 주장한다. 탐색 패러다임을 다항식 도메인으로 전환함으로써, 저자들은 기존에 접근 불가능했던 높은 차원($k$)을 가진 코드의 효율적인 발견을 가능하게 했다. 이 프레임워크는 자신의 경계를 정밀하게 획정한다. 즉, 순환 구조가 대수적 사전 필터링을 허용하는 코드는 성공적으로 포착하는 한편, "진정한 코셋 이론적 현상"(예: 랭크 퇴화)이 시작되는 지점을 $n=48$ 케이스를 통해 명시적으로 식별한다. 이 연구는 코드 발견을 위한 실용적인 도구뿐만 아니라, 군 대수적 구성과 심플렉틱 다항식 정식화 사이의 관계에 대한 이론적 명료함을 제공한다.