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

Resumo Técnico: Algoritmo de Otimização Aproximada Quântica para Decodificação Viterbi Baseada em Treliça

1. O Problema

A decodificação de códigos de correção de erros clássicos (como códigos de bloco lineares e códigos convolucionais) é fundamental para comunicações e armazenamento de dados. O objetivo é encontrar o codeword (palavra-código) mais provável transmitido, dado um vetor recebido com ruído.

• Desafio Clássico: A decodificação por Máxima Verossimilhança (ML) é um problema NP-difícil para classes gerais de códigos lineares, com complexidade temporal exponencial $O(2^n)$.
• Desafio Quântico: Algoritmos quânticos anteriores, como os baseados no algoritmo de Grover ou em Amplificação de Amplitude Iterativa (IAA), oferecem aceleração quadrática, mas exigem circuitos profundos e são vulneráveis a ruídos em dispositivos NISQ (Noisy Intermediate-Scale Quantum). Além disso, encontrar os parâmetros ótimos para algoritmos variacionais (como QAOA) em circuitos profundos é difícil devido ao fenômeno de "platôs estéreis" (barren plateaus), onde os gradientes desaparecem exponencialmente, tornando a otimização ineficiente.

2. Metodologia

Os autores propõem um decodificador híbrido quântico-clássico baseado no Algoritmo de Otimização Aproximada Quântica (QAOA) para realizar a decodificação Viterbi baseada em treliça.

• Mapeamento do Problema:

  • O problema de encontrar o caminho na treliça com a menor distância de Hamming (métrica de caminho mínima) é mapeado para a determinação do estado fundamental de um Hamiltoniano de custo.
  • Hamiltoniano de Custo ($H_f$): Representa a distância de Hamming entre o vetor recebido $y$ e os codewords candidatos. É construído como uma soma de operadores Pauli-Z locais.
  • Hamiltoniano Misturador ($H_m$): Projetado para garantir que a evolução do estado permaneça restrita ao espaço de códigos válido ($C$). O artigo estabelece um teorema (Teorema 1) que define $H_m$ como uma soma de operadores Pauli-X de ordem $d$ (onde $d$ é a distância mínima de Hamming do código), mapeando o elemento nulo para outros elementos no espaço de códigos com peso de Hamming $d$.

• Estrutura do Circuito (PQC):

  • O circuito quântico parametrizado (PQC) consiste em camadas alternadas de unitárias de custo ($U_f$) e unitárias de mistura ($U_m$).
  • O estado inicial é uma superposição uniforme de todos os codewords válidos, gerada por um operador de codificação $U_g$ baseado na matriz geradora do código.

• Estratégia de Otimização Uniforme (UPO):

  • Para contornar o problema de platôs estéreis e a dificuldade de otimização, os autores propõem a Uniform Parameter Optimization (UPO).
  • Diferente dos métodos tradicionais que otimizam parâmetros independentes para cada camada ($\gamma_1, \gamma_2...$ e $\beta_1, \beta_2...$), a UPO força todos os parâmetros de custo ($\gamma$) e de mistura ($\beta$) em todas as camadas a serem iguais ($\gamma_1 = ... = \gamma_p = \gamma_0$ e $\beta_1 = ... = \beta_p = \beta_0$).
  • Isso reduz drasticamente o número de parâmetros a serem otimizados pelo otimizador clássico, tornando o problema mais tratável em dispositivos NISQ e evitando a formação de platôs estéreis em circuitos de baixa profundidade.

3. Principais Contribuições

1. Mapeamento Geral: Desenvolvimento de um método generalizado para mapear o problema de decodificação Viterbi de qualquer código de bloco linear clássico em um circuito quântico parametrizado via QAOA.
2. Construção do Hamiltoniano Misturador: Derivação teórica de um Hamiltoniano misturador que preserva o espaço de códigos, dependente da distância mínima de Hamming ($d$) do código, garantindo que a busca não saia do espaço válido.
3. Estratégia UPO: Proposta e validação da técnica de Otimização de Parâmetros Uniformes. Os autores demonstram que essa abordagem é superior às estratégias de inicialização aleatória e de fixação de parâmetros (FPO) sugeridas anteriormente, especialmente para circuitos rasos (low-depth).
4. Eficiência em NISQ: Demonstração de que o decodificador híbrido QAOA-Viterbi é mais eficiente em termos de profundidade de circuito comparado a algoritmos anteriores de Viterbi quântico baseados em IAA.

4. Resultados

Os autores realizaram simulações utilizando o Qiskit e o simulador QASM da IBM Quantum Experience para códigos como $[6,3,3]$, $[9,4,4]$ e $[3,2,1]$.

• Desempenho da UPO vs. FPO:
  • Em simulações com 2000 "shots" (tiros) e múltiplas tentativas de treinamento, a estratégia UPO mostrou uma amplificação consistente e alta da probabilidade do estado solução (o codeword correto).
  • A estratégia FPO (Fixed Parameter Optimization) mostrou-se inconsistente, falhando em encontrar bons parâmetros em várias instâncias de treinamento e exibindo paisagens de otimização mais planas (platôs).
• Precisão da Decodificação:
  • Para o código $[6,3,3]$ com vetor recebido $y=111011$, o algoritmo identificou corretamente o codeword $011011$ com a menor métrica de caminho (distância de Hamming = 1).
  • O algoritmo também conseguiu identificar múltiplos caminhos com métrica mínima igual quando existiam (caso do código $[3,2,1]$), distribuindo a probabilidade corretamente entre as soluções equivalentes.
• Comparação com Decodificadores Clássicos:
  • Ao comparar com o decodificador de propagação de crença (Belief Propagation) para códigos de repetição, o decodificador híbrido apresentou taxas de erro de palavra (WER) quase idênticas, validando sua eficácia como um decodificador ativo para correção de erros clássicos.

5. Significância e Conclusão

O trabalho estabelece um marco importante na aplicação de algoritmos variacionais quânticos para problemas de comunicação clássica.

• Viabilidade Prática: Ao demonstrar que a otimização uniforme permite obter bons resultados em circuitos de baixa profundidade, o artigo torna a decodificação Viterbi quântica viável para a era NISQ, onde a profundidade do circuito é uma limitação crítica.
• Eficiência Computacional: A abordagem híbrida distribui o trabalho entre o processador quântico (avaliação do Hamiltoniano) e o clássico (otimização), oferecendo uma alternativa promissora aos métodos puramente clássicos para certos tipos de códigos e aos métodos quânticos profundos que são atualmente inviáveis.
• Futuro: Os autores sugerem que, embora a complexidade do Hamiltoniano misturador aumente com a estrutura do código, a técnica UPO deve escalar melhor do que métodos não uniformes para códigos maiores. O trabalho abre caminho para o uso de algoritmos variacionais em problemas de inferência e decodificação em larga escala, desde que assistido por correção de erros quântica.

Em suma, o artigo propõe uma solução híbrida robusta e eficiente para um problema clássico difícil, utilizando uma estratégia de otimização inteligente (UPO) para superar as limitações atuais do hardware quântico.