Random Construction of Quantum LDPC Codes

기술 요약: 양자 LDPC 코드의 무작위 생성

문제 정의
양자 저밀도 패리티 검사(LDPC) 코드, 특히 직교하는 이진 패리티 검사 행렬 $H_X$와 $H_Z$($H_X H_Z^T = 0$을 만족)로 정의되는 칼더뱅크-쇼어-스테인(CSS) 유형은 확장 가능한 결함 허용 양자 컴퓨팅을 위해 유망합니다. 그러나 기존의 구성 방식들은 구조적 제어와 무작위성 사이에서 트레이드오프를 겪고 있습니다:

• 순환/준순환(Quasi-Cyclic) 구성: 바이사이클(bicycle) 코드나 준순환 LDPC 코드와 같은 방법은 차수 분포(degree distributions)에 대한 유연한 제어를 허용하지만, 대규모 직교 쌍을 생성하고 중복 행을 제거하는 과정에 의존하기 때문에 종종 작은 최소 거리를 초래할 수 있습니다.
• 텐서 곱(Tensor-Product) 구성: 하이퍼그래프 곱(HGP) 코드와 같은 방법은 큰 최소 거리를 달성할 수 있지만, 차수 분포를 정밀하게 제어하기 어렵습니다.
• 공백(The Gap): 클래식 무작위 LDPC 구성과 유사하면서도, 벨리프 프로파게이션(BP) 디코딩 성능에 결정적인 특정 행 및 열 가중치 분포를 엄격하게 유지하는 고도로 무작위화된 양자 LDPC 코드 앙상블을 생성할 수 있는 구성 방법이 부족합니다.

방법론
저자들은 초기 직교 행렬 쌍의 가중치 분포를 보존하면서 이를 수정하는 방식으로 양자 LDPC 코드 앙상블을 생성하는 프레임워크를 제안합니다. 핵심 절차는 세 단계로 이루어집니다:

1. 초기화: 원하는 차수 분포를 가진 초기 직교 행렬 쌍 $(H_X, H_Z)$를 준비합니다. 흔한 예로, 블록 배열에 항등 행렬을 타일링하여 구성된 정규(regular) 쌍이 있으며, 이는 직교 조건을 자명하게 만족합니다.
2. 국소 무작위 수정 (Cross-Swap): 한 행렬(예: $H_X$)에 무작위 $2 \times 2$ "크로스 스왑(cross-swap)" 연산을 적용합니다. 이 연산은 서브매트릭스가 $\begin{smallmatrix} 1 & 0 \\ 0 & 1 \end{smallmatrix}$인 두 행과 두 열을 선택하여 이를 $\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}$로 바꿉니다. 이 연산은 수정된 행렬의 행 및 열 가중치는 보존하지만, 일반적으로 직교 조건 $H_X H_Z^T = 0$을 위반합니다.
3. ILP 기반 국소 복구(Local Repair): 수정되지 않은 행렬(예: $H_Z$)의 가중치 분포를 변경하지 않으면서 직교성을 복구하기 위해, 저자들은 국소 복구 문제를 정형화합니다.
   • 국소화(Localization): 직교성 위반을 스왑에 의해 영향을 받은 특정 행($I$) 및 열($J$) 인덱스 집합으로 국한시킵니다.
   • 정형화: 복구는 영향을 받은 서브매트릭스에 적용될 이진 복구 행렬 $\Delta$를 결정 변수로 하는 컴팩트한 정수 선형 계획법(ILP)으로 모델링됩니다.
   • 제약 조건: ILP는 다음을 강제합니다:
     • 직교성: 복구된 행렬은 $H_X H_Z^T = 0$으로부터 유도된 선형 시스템을 만족해야 합니다.
     • 가중치 보존: "부호 균형(signed balance)" 제약 조건은 각 영향을 받은 행과 열에서 $1 \to 0$ 및 $0 \to 1$ 플립의 수가 같음을 보장하여, 원래의 가중치 분포를 정확하게 유지합니다.
   • 목적 함수: 솔버는 최소한의 플립($\Delta$의 $L_1$ 노름)을 찾아 가장 작은 규모의 복구를 수행합니다.
   • 반복: 이 과정을 $H_X$와 $H_Z$의 역할을 교대로 바꾸며 무작위로 반복하여, 완전히 무작위화된 앙상블을 생성합니다.

주요 기여

• 분포 보존을 동반한 구조적 무작위성: 단순한 치환(permutation)과 달리, 제안된 크로스 스왑 및 복구 메커니즘은 주어진 행 및 열 가중치 분포를 엄격하게 유지하면서도 진정한 구조적 무작위성을 도입합니다.
• 확장 가능한 복잡도: 국소 복구 단계의 계산 복잡도는 전체 행렬 크기(블록 길이)와 무관하게 오직 최대 행 및 열 가중치($d_r, d_c$)에만 의존합니다.
  • 로컬 ILP의 변수 수는 $O(d_c^2 d_r)$로 제한됩니다.
  • 패리티 제약 조건의 수는 $O(d_c^3 d_r)$로 제한됩니다.
  • 이는 해당 방법이 실용적인 양자 코드를 위한 필수 요구 사항인 매우 큰 코드 블록에도 확장 가능하다는 것을 보장합니다.
• 알고리즘 구현: 저자들은 로컬 ILP 인스턴스를 효율적으로 처리하기 위해 OR-Tools CP-SAT 솔버를 사용하는 구체적인 알고리즘을 제공합니다.

결과

• 토이 예제: 저자들은 $12 \times 32$ 정규 직교 쌍에서 시작하는 토이 예제를 통해 이 방법을 시연했습니다. 단 한 번의 크로스 스왑을 적용하고 로컬 ILP를 해결한 후, 직교성과 가중치 보존을 성공적으로 복구했습니다.
• 앙상블 생성: 수백 번의 무작위 스위치-복구(switch-repair) 반복 후에, 이 방법은 잘 무작위화된 직교 쌍을 생성했습니다.
• 코드 특성: 결과로 얻은 $12 \times 32$ 쌍에 대해 저자들은 다음을 검증했습니다:
  • 직교성: $H_X H_Z^T = 0$.
  • 계수(Rank): 두 행렬 모두 풀 랭크(full rank, 12)를 가집니다.
  • 차원(Dimension): 결과적인 CSS 코드는 차원 $k = 32 - 12 - 12 = 8$을 가집니다.
  • 거리(Distance): 커널(kernel)에 대한 전수 조사를 통해 정확한 거리 $d_X = 4$와 $d_Z = 2$를 얻었으며, 이는 $[[32, 8, 2]]$ 코드를 정의합니다.
• 성능: 일반적인 파라미터(예: $d_c=3, d_r=8$)에 대한 복구 과정은 수백 개의 변수를 포함하는 로컬 ILP를 사용하여 표준 노트북에서 몇 초 내에 해결되었습니다.

의의 및 주장
본 논문은 이 방법이 원하는 구조적 특성(특히 차수 분포)과 일치하는 무작위화된 양자 LDPC 코드 앙상블을 탐색하는 체계적인 방법을 제공한다고 주장합니다.

• 디코딩 함의: BP의 점근적 디코딩 동작은 주로 가중치 분포에 의해 결정되므로, 이 방법은 차수 프로필의 변화라는 혼란 변수 없이 무작위 앙상블의 성능을 연구할 수 있게 해줍니다.
• 미래 잠재력: 저자들은 이 작업이 구성 방법론과 복잡성에 초점을 맞추고 있지만, 무작위화가 작은 트래핑 세트(trapping sets)를 제거함으로써 에러 플로어(error floor)를 낮출 잠재력이 있다고 제안합니다. 또한 ILP 기반 접근 방식이 향후 작업(예: 짧은 사이클 방지 또는 공간 결합)에서 추가적인 제약 조건을 통합할 수 있을 만큼 유연하다는 점을 언급합니다.
• 한계: 논문은 벨리프 프로파게이션 디코딩 성능에 대한 분석은 향후 연구 과제로 남겨두고 있음을 명시적으로 밝히고 있습니다. 현재의 작업은 구성 프레임워크와 그 계산 가능성을 확립하는 데 목적이 있습니다.