Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes

논문 개요

이 논문은 고전적인 오류 정정 코드 (Classical Error Correcting Codes) 의 비터비 (Viterbi) 디코딩을 수행하기 위한 하이브리드 양자 - 고전적 Viterbi 디코더를 제안합니다. 저자들은 양자 근사 최적화 알고리즘 (QAOA) 을 활용하여 트렐리스 (Trellis) 상에서 수신된 오류 벡터에 대한 최소 해밍 거리 (Hamming distance) 를 갖는 경로를 찾는 문제를 해결하고, 이를 위해 균일 파라미터 최적화 (Uniform Parameter Optimization, UPO) 전략을 도입하여 NISQ(Noisy Intermediate-Scale Quantum) 장치에서의 실행 효율성을 극대화했습니다.

1. 문제 정의 (Problem Statement)

• 배경: 통신 및 데이터 저장 채널의 노이즈를 처리하기 위해 오류 정정 코드가 사용되며, 수신된 오류 신호로부터 가장 가능성 높은 전송된 코드워드를 찾는 디코딩은 NP-hard 문제입니다.
• 기존 접근법의 한계:
  • 최대 가능도 (ML) 디코딩: 코드 공간 내 모든 가능한 코드워드를 계산하므로 시간 복잡도가 $O(2^n)$으로 지수적으로 증가합니다.
  • 기존 양자 알고리즘: 그로버 (Grover) 알고리즘 기반의 검색이나 진폭 증폭 (IAA) 기반의 양자 비터비 알고리즘은 이론적으로 2 차 속도 향상을 제공하지만, 회로 깊이가 깊어지고 NISQ 장치의 잡음에 취약하여 실제 구현에 비효율적입니다.
• 목표: NISQ 장치에 적합한 낮은 깊이 (low-depth) 의 변분 양자 알고리즘 (VQA) 을 사용하여 고전적 선형 블록 코드의 비터비 디코딩을 효율적으로 수행하는 것입니다.

2. 방법론 (Methodology)

2.1 QAOA 기반 하이브리드 아키텍처

저자들은 Viterbi 디코딩 문제를 QAOA 의 최적화 문제로 매핑했습니다.

• 비용 함수 (Cost Function): 수신된 벡터 $y$와 코드워드 $c$ 사이의 해밍 거리를 최소화하는 것을 목표로 합니다.
  • $f(c) = \sum (c_i \oplus y_i)$
  • 이를 대각 해밀토니안 $H_f$로 변환하여 양자 회로에서 기대값을 계산합니다.
• 믹서 해밀토니안 (Mixer Hamiltonian): 탐색 공간 (코드 공간 $C$) 을 유지하면서 상태 간의 전이를 가능하게 합니다.
  • Theorem 1: 선형 블록 코드의 최소 해밍 거리 $d$를 기반으로 믹서 해밀토니안 $H_m$을 구성합니다. $H_m$은 $d$-local Pauli-X 연산자의 합으로 정의되며, 널 상태 (all-zero codeword) 를 코드 공간 내의 다른 유효한 상태들로 매핑합니다.
  • 이 구조는 코드 공간 밖으로 상태가 이탈하는 것을 방지하여 유효한 디코딩 경로를 보장합니다.

2.2 파라미터화된 양자 회로 (PQC) 설계

• 초기 상태: 코드 공간 내 모든 코드워드의 균등 중첩 상태 (Equal Superposition) 를 생성하기 위해 생성 행렬 (Generator Matrix) 을 기반으로 한 유니타리 연산자 $U_g$를 사용합니다.
• 회로 구조: 비용 유니타리 $U_f(\gamma)$와 믹서 유니타리 $U_m(\beta)$를 교대로 적용하여 $p$개의 레이어로 구성된 PQC 를 구성합니다.
• 고전적 최적화: 양자 회로에서 측정된 비용 함수의 기대값을 최소화하는 파라미터 ($\gamma, \beta$) 를 고전적 최적화기를 통해 찾습니다.

2.3 균일 파라미터 최적화 (UPO) 전략

• 문제점: PQC 의 파라미터를 무작위로 초기화하거나 레이어별로 독립적으로 최적화 (Fixed Parameter Optimization, FPO) 하면 '메마른 대지 (Barren Plateaus)' 현상이 발생하여 기울기가 소실되고 최적화가 어렵습니다.
• 해결책 (UPO): 모든 레이어의 믹서 파라미터 ($\beta_i$) 를 하나의 값 $\beta_0$로, 비용 파라미터 ($\gamma_i$) 를 하나의 값 $\gamma_0$로 동일하게 설정합니다.
  • $\beta_1 = \beta_2 = \dots = \beta_p = \beta_0$
  • $\gamma_1 = \gamma_2 = \dots = \gamma_p = \gamma_0$
• 효과: 파라미터 수를 줄이고 최적화 지형을 평탄하지 않게 만들어, 낮은 깊이 (shallow depth) 의 회로에서도 전역 최소값을 효율적으로 찾을 수 있도록 합니다.

3. 주요 기여 (Key Contributions)

1. 일반화된 매핑 방법: 임의의 고전적 선형 블록 코드를 QAOA 기반의 비용 및 믹서 해밀토니안으로 매핑하는 일반화된 방법을 제시했습니다.
2. Theorem 1 (믹서 해밀토니안 구성): 코드의 최소 해밍 거리 $d$에 기반하여 코드 공간을 보존하는 유효한 믹서 해밀토니안을 수학적으로 증명하고 구성했습니다.
3. UPO 전략 제안: 기존 무작위 초기화 및 FPO 전략보다 우수한 성능을 보이는 균일 파라미터 최적화 기법을 제안하고, 이를 통해 barren plateau 문제를 완화했습니다.
4. 효율적인 하이브리드 디코더: 기존 양자 비터비 알고리즘 (IAA 기반) 보다 낮은 회로 깊이와 더 높은 정확도로 디코딩을 수행할 수 있음을 시뮬레이션을 통해 입증했습니다.

4. 실험 결과 (Results)

• 시뮬레이션 환경: IBM Quantum Experience 의 Qiskit 및 QASM 시뮬레이터를 사용했습니다.
• 테스트 코드: [6, 3, 3], [9, 4, 4], [3, 2, 1] 등 다양한 선형 블록 코드를 대상으로 실험했습니다.
• 성능 비교:
  • UPO vs FPO: UPO 를 사용한 경우, 실제 해 (최소 경로 메트릭을 가진 상태) 가 높은 확률로 증폭되는 반면, FPO 는 무작위적인 결과를 보였습니다. 특히 $p=3$ 및 $p=15$의 깊은 회로에서도 UPO 가 안정적인 성능을 보였습니다.
  • 정확도: 수신된 오류 벡터에 대해 최소 해밍 거리를 갖는 경로 (코드워드) 를 높은 확률로 찾아냈습니다. 예를 들어, [6, 3, 3] 코드에서 수신 벡터 $y=111011$에 대해 해밍 거리 1 인 경로 $011011$을 성공적으로 디코딩했습니다.
  • 다중 경로 처리: 최소 경로 메트릭을 갖는 경로가 여러 개 존재하는 경우 (예: [3, 2, 1] 코드), 하이브리드 디코더는 모든 최소 경로에 대해 균등한 확률로 솔루션을 반환하여 이론과 일치함을 보였습니다.
  • 비교 평가: 표준 Min-Sum Belief Propagation 디코더와 비교했을 때, 반복 코드 (Repetition Code) 에 대해 유사한 단어 오류율 (WER) 을 보이며 고전적 디코더와 경쟁 가능한 성능을 입증했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• NISQ 적합성: 제안된 방법은 낮은 회로 깊이에서도 작동하며, 파라미터 최적화의 효율성을 높여 현재의 NISQ 하드웨어 제약 내에서 고전적 오류 정정 디코딩을 수행할 수 있는 가능성을 열었습니다.
• 하이브리드 접근법의 우위: 기존 양자 알고리즘에 비해 회로 복잡도를 줄이고, UPO 전략을 통해 최적화 난이도를 낮춤으로써 실용적인 양자 디코더의 후보로 자리 잡았습니다.
• 미래 전망:
  • 대규모 코드로의 확장성 검증 필요.
  • 양자 오류 정정 코드와의 결합을 통한 NISQ 장치에서의 실제 구현.
  • 추론 문제 (Inference problems) 등 다른 최적화 문제로의 확장 가능성.

이 논문은 양자 컴퓨팅이 고전적인 통신 및 데이터 저장 시스템의 핵심 문제인 오류 정정 디코딩에 실질적인 이점을 제공할 수 있음을 보여주는 중요한 사례입니다.