Sequences of Bivariate Bicycle Codes from Covering Graphs

기술 요약: 피복 그래프로부터 생성된 이변량 바이사이클 코드의 수열

문제 정의
양자 저밀도 패리티 검사(qLDPC) 코드는 상수율(constant rate)과 개선된 거리 스케일링을 제공함으로써 표면 코드(surface code)의 유망한 대안이 될 수 있으며, 결함 허용 양자 컴퓨팅에 필요한 공간 오버헤드를 줄일 수 있습니다. 그러나 가능한 패리티 검사 다항식의 방대한 탐색 공간으로 인해 새로운 고성능 qLDPC 코드를 식별하는 것은 여전히 과제로 남아 있습니다. 특히, $\mathbb{F}_2[Z_l \times Z_m]$ 상의 군 대수 코드(group algebra codes)인 이변량 바이사이클(Bivariate Bicycle, BB) 코드는 높은 비율과 높은 거리의 인스턴스(예: [[144, 12, 12]] "gross" 코드)를 보여주었으나, 예측 가능한 파라미터를 가진 무한한 코드 패밀리를 생성하는 일반적인 방법은 제한적이었습니다. 또한, 서로 다른 코드 인스턴스 전반에 걸친 논리 연산자와 자기동형 사상(automorphisms) 사이의 관계를 이해하는 것은 논리 연산을 구현하는 데 매우 중요하지만, 대규모 코드에 대해서는 분석하기 어려운 경우가 많습니다.

방법론
저자들은 피복 그래프(covering graphs 또는 graph lifts)라는 수학적 개념을 사용하여 BB 코드의 무한 수열을 생성하는 프레임워크를 제안합니다. 핵심 방법론은 다음과 같습니다:

1. 피복을 위한 대수적 조건: 저자들은 BB 코드 $\tilde{Q}$의 태너 그래프(Tanner graph)가 베이스 BB 코드 $Q$의 피복 그래프가 되기 위한 특정 대수적 조건(격자 파라미터 및 정의 다항식에 관한 조건)을 확립했습니다. 구체적으로, $Q$가 파라미터 $(l, m)$과 다항식 $A, B$를 가질 때, 파라미터 $(\tilde{l}, \tilde{m})$와 다항식 $\tilde{A}, \tilde{B}$를 갖는 피복 코드 $\tilde{Q}$가 유효한 $h$-피복($h = \tilde{l}\tilde{m}/lm$)이 되기 위한 조건은 다음과 같습니다:

   • $\tilde{l} = ul$이고 $\tilde{m} = tm$이며, 여기서 $u, t$는 정수입니다.
   • $\tilde{A}$와 $\tilde{B}$에 포함된 단항식의 지수(exponents)는 각각 $l$과 $m$에 대해 $A$와 $B$의 지수와 합동(congruent)이어야 합니다.
   • 유도된 그래프를 생성하는 데 사용된 전압 할당(voltage assignment)은 격자 파라미터의 "몫(quotient)"에 대응해야 합니다.

2. 축소된 탐색 공간: 저자들은 이러한 합동 조건을 만족하는 다항식으로 탐색 범위를 제한함으로써 새로운 코드를 위한 탐색 공간을 획기적으로 줄였습니다. 길이 $n$인 전체 다항식 공간을 탐색하는 대신, 탐색은 베이스 코드의 다항식 변형으로 제한되며, 이를 통해 복잡도가 $O(n^6)$에서 $h$-피복의 경우 약 $O(h^4)$로 감소합니다.

3. 체인 맵(Chain Maps) 및 호몰로지(Homology): 그래프 피복 맵은 베이스 코드와 피복 코드의 체인 복합체(chain complexes) 사이의 체인 맵으로 확장됩니다. 이는 (코)호몰로지에 다음과 같은 사상을 유도합니다:

   • 투영 맵 ($p$): 피복 코드의 논리 연산자를 베이스 코드로 매핑합니다.
   • 리프팅 맵 ($\tau$): 베이스 코드의 논리 연산자를 피복 코드로 매핑합니다.
   • 가중치 보존 리프팅 ($\sigma$): 각 정점에 대해 단일 역상을 선택하는 특수한 유형의 리프팅으로, 피복 코드의 거리를 상한(upper bound)으로 결정하는 데 사용됩니다.

4. 자기동형 사상 리프팅: 이 프레임워크는 그래프 자기동형 사상(및 그에 따른 CSS 코드 자기동형 사상)이 베이스에서 피복으로 리프팅될 수 있음을 보여주는 방식으로 확장됩니다. 특정 조건(홀수 $h$ 및 동일한 논리 큐비트 수) 하에서, 이러한 자기동형 사상의 논리적 작용은 보존됩니다.

주요 기여 및 결과

• 코드 수열 생성: 저자들은 알려진 고성능 BB 코드(예: [[144, 12, 12]] gross 코드)가 더 작은 코드(예: [[72, 12, 6]])의 이중 피복(double covers)으로 볼 수 있음을 입증했습니다. 이들은 고정된 논리 큐비트 수($k$)와 증가하는 블록 크기($n$)를 가진 새로운 BB 코드의 무한 수열을 생성합니다.
  • 가중치 6 코드: 이 방법은 균형 잡힌 곱 코드(balanced product codes)와 일반화된 토릭 코드(generalized toric codes)를 포함한 알려진 패밀리를 재현하며, $k=6, 8, 10, 12$에 대한 새로운 수열을 생성합니다.
  • 가중치 8 코드: 저자들은 가중치 8 체크(정의 다항식에 4개의 항이 있음)를 가진 BB 코드를 탐색하기 위해 이 방법을 적용했습니다. 그들은 $k=8, 10, 12, 14$를 가지며 가중치 6 코드보다 훨씬 높은 $kd^2/n$ 비율을 보이는 수열을 발견했습니다. 주목할 만한 예로는 [[64, 14, 8]] 및 [[144, 14, 14]] 코드가 있습니다.
  • 큐디트(Qudit) 코드: 본 방법론은 $\mathbb{F}_q$ 상의 큐디트 코드로 일반화되어, 베이스 큐디트 BB 코드에 대한 피복 코드를 성공적으로 생성했습니다.
• 이론적 경계:
  • 논리 큐비트 ($k$): 저자들은 $h$가 홀수인 $h$-피복 코드에 대해 논리 큐비트 수가 $k_h \ge k$임을 증명했습니다. 이들이 모든 $h$에 대해 성립한다고 추측합니다.
  • 거리 ($d$): $h$가 홀수일 때, $d_h \le hd$임을 증명했습니다. 만약 $k_h = k$이고 $h$가 홀수라면, $d_h \ge d$임을 증명했습니다. 이들은 일반적인 경계 $d \le d_h \le hd$가 모든 $h$에 대해 성립한다고 추측합니다.
  • 가중치 보존 리프팅: 가중치 보존 리프팅이 존재하면 $d_h \le d$임을 의미하며, 이는 거리가 증가하지 않는 피복 코드를 배제하는 수치적 도구를 제공함을 보여줍니다.
• 논리 연산자 및 자기동형 사상 분석: 논리 연산자와 자기동형 사상을 리프팅하는 명시적인 구성을 제공합니다. $h$가 홀수이고 $k_h = k$일 때, 리프팅 맵이 호몰로지 상의 동형 사상(isomorphism)임을 증명하여, 베이스 코드의 논리 기저가 피복 코드의 완전한 논리 기저로 리프팅되어 자기동형 사상(예: 논리적 CNOT 및 Hadamard 게이트)의 논리적 작용을 보존함을 보장합니다.

의의

저자들은 본 연구가 다음 세 가지 영역에서 중요하다고 주장합니다:

1. 효율적인 코드 발견: 피복 그래프 이론에 기반한 축소된 탐색 공간을 식별함으로써, 저자들은 전수 조사(brute-force search) 없이도 유망한 파라미터를 가진 새로운 BB 코드를 발견할 수 있는 체계적이고 효율적인 방법을 제공합니다.
2. 이론적 통합: 이 작업은 다양한 알려진 BB 코드 구축 방식(gross 코드, 균형 잡힌 곱 코드, 일반화된 토릭 코드 포함)을 피복 그래프라는 단일 프레임워크 아래로 통합하여, 이들 사이의 구조적 관계를 밝혀냅니다.
3. 논리 연산 관리: 투영 및 리프팅 맵의 개발은 대규모 코드를 분석하기 위한 실질적인 도구를 제공합니다. 작고 잘 이해된 베이스 코드로부터 논리 연산자와 자기동형 사상을 유도함으로써, 대규모 qLDPC 코드의 논리 연산 관리 복잡도를 줄여줍니다.

저자들은 연구의 초점이 BB 코드에 맞춰져 있지만, 본 방법론이 다른 군 대수 코드 및 하이퍼그래프(hypergraph)나 리프티드 프로덕트(lifted products)를 포함하는 구성에도 일반화될 수 있을 것으로 기대한다고 언급했습니다. 또한, 탐색 공간이 축소되었음에도 불구하고 대규모 피복 코드의 정확한 거리를 계산하는 것은 여전히 병목 현상으로 남아 있으며, 이들의 이론적 경계는 완전한 해결책이라기보다 가이드 역할을 한다고 강조했습니다.