Learning-Based List Sequential Belief Propagation Decoding of Quantum LDPC Codes

기술 요약: 양자 LDPC 코드의 학습 기반 리스트 순차적 신념 전파(Belief Propagation) 디코딩

문제 정의
양자 저밀도 패리티 검사(QLDPC) 코드는 희소한 안정기(stabilizer) 구조와 높은 인코딩율 덕분에 결함 허용 양자 컴퓨팅을 위한 유망한 후보입니다. 그러나 이러한 코드를 효율적으로 디코딩하는 것은 여전히 큰 과제로 남아 있습니다. 표준 신념 전파(BP) 디코더를 QLDPC 코드에 적용할 경우 수렴에 실패하거나 논리적으로 잘못된 해로 수렴하는 경우가 빈번합니다. 이러한 실패는 크게 두 가지 요인에서 기인합니다:

1. 구조적 문제: 안정기 코드의 가환성 제약(commutativity constraints)은 태너 그래프(Tanner graph) 내에 많은 짧은 사이클을 유도하며, 이는 표준 BP가 요구하는 독립성 가정을 위반합니다.
2. 양자 퇴화(Quantum Degeneracy): 서로 다른 파울리 에러 패턴이 동일한 신드롬을 생성하고 동일한 복구 연산을 나타낼 수 있습니다. 결과적으로 디코더는 정확한 물리적 에러를 식별할 필요 없이 올바른 논리적 코셋(logical coset) 내의 에러를 찾아내면 됩니다. 이러한 퇴화 현상은 대칭적인 의사-코드워드(pseudo-codewords)와 트래핑 세트(trapping sets)를 생성하여 BP가 진동하거나 정체되게 만듭니다.

강화학습 기반의 순차적 스케줄링(RL-S)은 수렴성을 개선하기 위해 최적의 변수 노드 업데이트 순서를 학습함으로써 유망한 가능성을 보여주었으나, 이는 단일 궤적(single-trajectory) 접근 방식이라는 한계가 있습니다. 순차적 디코더는 "근접 실수(near-miss)" 결정에 대해 재고할 메커니즘이 부족합니다. 즉, 국소적으로 가장 가능성 높은 파울리 심볼을 초기에 선택했으나 퇴화 현상으로 인해 전역적으로 최적이 아닌 것으로 판명될 경우, 디코더는 이를 회복할 수 없습니다.

방법론
저자들은 단일 궤적 RL-S의 한계를 해결하기 위해 학습 기반 리스트 순차적(RL-LS) BP 디코더를 제안합니다. 이 방법은 기존 RL-S 프레임워크를 확장하여 단일 경로 대신 후보 디코딩 궤적들의 리스트를 유지합니다.

핵심 메커니즘은 다음과 같이 작동합니다:

1. 순차적 선택: 각 디코딩 단계에서, 학습된 정책(오프라인에서 훈련된 고정된 Q-테이블)은 RL-S 방식과 동일하게 국소 신드롬 기반 상태 표현을 바탕으로 다음 업데이트할 변수 노드를 선택합니다.
2. 리스트 확장: 단일 업데이트를 확정하는 대신, 디코더는 선택된 노드에 대해 두 가지 후보 지속 경로를 생성합니다:
   • 일반 자식(Ordinary Child): 표준 RL-S 업데이트를 따르며, 국소 사후 확률에 기반하여 가장 가능성 높은 파울리 심볼을 선택합니다.
   • 대안 자식(Alternative Child): 업데이트 후의 로그 가능도 비(LLR) 쌍을 두 번째로 가능성 높은 파울리 심볼 쪽으로 부드럽게 편향(softly bias)시킵니다. 디코더는 인접한 국소 BP 메시지를 재계산하고 해당 변수 노드를 두 번째 최선인 심볼로 설정합니다.
3. 경로 메트릭 및 가지치기(Pruning): 각 궤적에는 누적 경로 메트릭 $M$이 할당됩니다. 이 메트릭은 국소적으로 지배적인 결정으로부터의 이탈에 대해 페널티를 부여합니다. 구체적으로, 두 번째 최선 경로를 택할 때의 페널티는 최선과 두 번째 최선 심볼 사이의 국소 로그 가능도 격차($\Delta$)입니다.
   • 디코더는 경로 메트릭 $M$과 잔차 불일치 가중치 $w$의 사전식 순서(lexicographic ordering)에 따라 상위 $L$개의 후보를 유지합니다.
   • 이 가지치기 전략은 디코더가 국소적 모호성(퇴화)을 탐색하면서도, 국소적으로 지배적인 증거에 근접한 경로를 우선시하도록 보장합니다.
4. 종료: 경로가 잔차 불일치 0(신드롬 일치)을 달성하거나 최대 반복 횟수에 도달할 때까지 프로세스가 계속됩니다. 만약 어떤 경로도 수렴하지 않으면, 가장 좋은 $(M, w)$ 쌍을 가진 생존 경로를 반환합니다.

주요 기여

• 새로운 디코더 아키텍처: 본 논문은 리스트 기반 탐색을 학습된 순차적 스케줄링 프레임워크에 통합한 RL-LS 디코더를 소개합니다. 기존의 리스트 기반 접근 방식들이 무거운 후처리 과정을 추가하거나 고정된 접두사(prefix) 이후에 병렬 비트 플리핑을 실행하는 것과 달리, RL-LS는 순차적 업데이트 과정 내부에서 리스트 확장을 수행합니다.
• 연성 섭동 전략(Soft Perturbation Strategy): 저자들은 하드 플리핑(hard flipping) 대신 LLR을 두 번째 최선 심볼 쪽으로 부드럽게 편향시키는 방식을 통해 대안 궤적을 생성하는 구체적인 방법을 제안합니다. 이를 통해 디코더는 주요 학습 궤적을 버리지 않고도 경쟁하는 가설들을 탐색할 수 있습니다.
• 누적 경로 메트릭: 후보 경로의 순위를 매기기 위해 국소적 결정의 가능성과 신드롬 일치라는 전역적 요구 사항 사이의 균형을 맞추는 새로운 메트릭을 정의했습니다.
• 엄격한 확장성: 제안된 디코더는 기본 RL-S 디코더의 엄격한 확장입니다. 일반적인 RL-S 궤적은 항상 리스트의 한 후보로서 보존되므로, 기본 디코더의 성능이 결코 저하되지 않습니다.

수치 결과
저자들은 탈분극 채널(depolarizing channel) 환경에서 Bivariate Bicycle (BB) 코드 및 A5 코드를 포함한 대표적인 QLDPC 벤치마크 코드에 대해 RL-LS 디코더를 평가했습니다.

• 성능 향상: 수치 결과에 따르면, RL-LS는 블록 에러율(BLER) 측면에서 기존의 RL-S 및 다양한 BP 기반 방식(QBP, QBPGD, BP-OSD-0 등)보다 유의미하게 우수한 성능을 보였습니다.
• 효율성: 제안된 방법은 더 적은 반복 횟수로 우수한 오류 정정 성능을 달행합니다. 예를 들어, [[288, 12, 18]] BB 코드에서 리스트 크기 $L=8$, $T=100$ 반복 횟수의 RL-LS는 $T=1000$ 반복 횟수의 RL-S와 대등한 성능을 달성하여 상당한 지연 시간(latency) 이점을 제공했습니다.
• 수렴 속도: 다양한 탈분극 확률에 걸쳐 학습 기반 디코더, 특히 RL-LS는 기존 BP 기반 디코더에 비해 수렴하는 데 필요한 평균 반복 횟수가 현저히 적었습니다.

의의 및 주장
본 논문은 RL-LS 디코더가 순차적 디코딩 중 발생하는 양자 퇴화 및 짧은 사이클로 인한 조기 실수 위험을 효과적으로 완화한다고 주장합니다. 학습된 순차적 스케줄링의 개선된 수렴성과 경량화된 리스트 탐색을 결합함으로써, 이 방법은 단일 궤적 접근 방식보다 국소적 모호성을 더 견고하게 헤쳐 나갑니다.

저자들은 이 연구를 BP 기반 QLDPC 디코딩의 신뢰성을 높이는 유망한 방향으로 제시합니다. 이 접근 방식은 무거운 후처리 단계를 피하면서도 디코딩 지연 시간과 오류 정정 성능 사이의 유리한 절충안을 제공하며, 여전히 BP 메시지 전달 프레임워크 내에 머물러 있음을 강조합니다. 결과는 학습된 순차적 스케줄링에 리스트 기반 탐색을 통합하는 것이 결함 허용 양자 아키텍처를 강화하는 실행 가능한 전략임을 시사합니다.