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

Resumo Técnico: Decodificação de Propagação de Crença Sequencial de Lista Baseada em Aprendizado para Códigos QLDPC

Enunciado do Problema
Códigos de Verificação de Paridade de Baixa Densidade Quântica (QLDPC) são candidatos promissores para a computação quântica tolerante a falhas devido à sua estrutura de estabilizador esparsa e altas taxas de codificação. No entanto, decodificar esses códigos de forma eficiente continua sendo um desafio significativo. Os decodificadores de Propagação de Crença (BP) padrão frequentemente falham em convergir ou convergem para soluções logicamente incorretas quando aplicados a códigos QLDPC. Essa falha decorre de dois fatores primários:

1. Problemas Estruturais: As restrições de comutatividade dos códigos estabilizadores induzem muitos ciclos curtos no grafo de Tanner, violando as suposições de independência necessárias para o BP padrão.
2. Degenerescência Quântica: Diferentes padrões de erro de Pauli podem gerar o mesmo síndrome e representar operações de recuperação equivalentes. Consequentemente, um decodificador não precisa identificar o erro físico exato, mas sim um erro no cosseto lógico correto. Essa degenerescência cria pseudocódigos simétricos e conjuntos de armadilhas (trapping sets), fazendo com que o BP oscile ou estagne.

Embora o escalonamento sequencial baseado em aprendizado por reforço (RL-S) tenha mostrado promessa ao aprender uma ordem ótima de atualização de nós de variável para melhorar a convergência, ele permanece uma abordagem de trajetória única. Um decodificador sequencial carece de um mecanismo para revisitar decisões de "quase acerto"; se o símbolo de Pauli localmente mais provável for escolhido precocemente, mas provar ser globalmente suboptimal devido à degenerescência, o decodificador não consegue se recuperar.

Metodologia
Os autores propõem um decodificador BP de Lista Sequencial Baseado em Aprendizado (RL-LS) para abordar as limitações da abordagem de trajetória única do RL-S. O método estende o framework RL-S existente mantendo uma lista de trajetórias de decodificação candidatas em vez de um único caminho.

O mecanismo central opera da seguinte forma:

1. Seleção Sequencial: Em cada etapa de decodificação, uma política aprendida (uma tabela Q congelada treinada offline) seleciona o próximo nó de variável para atualizar com base em uma representação de estado local impulsionada pelo síndrome, idêntica à abordagem RL-S.
2. Expansão de Lista: Em vez de se comprometer com uma única atualização, o decodificador gera duas continuações candidatas para o nó selecionado:
   • Filho Ordinário: Segue a atualização padrão do RL-S, selecionando o símbolo de Pauli mais provável com base na posterior local.
   • Filho Alternativo: Sesga suavemente o par de Razão de Verossimilhança Logarítmica (LLR) pós-atualização em direção ao segundo símbolo mais provável. O decodificador recomputa as mensagens de BP locais incidentes e define o nó de variável para este segundo melhor símbolo.
3. Métrica de Caminho e Poda: Cada trajetória é atribuída a uma métrica de caminho cumulativa $M$. A métrica penaliza desvios da decisão localmente dominante. Especificamente, a penalidade por tomar o segundo melhor ramo é o hiato de log-verossimilhança ($\Delta$) local entre os símbolos melhor e segundo melhor.
   • O decodificador retém os $L$ candidatos principais com base em uma ordenação lexicográfica da métrica de caminho $M$ e do peso de desajuste residual $w$.
   • Esta estratégia de poda garante que o decodificador explore ambiguidades locais (degenerescência) enquanto prioriza caminhos que permanecem próximos à evidência localmente dominante.
4. Terminação: O processo continua até que um caminho atinja um desajuste residual zero (consistência de síndrome) ou o limite máximo de iterações seja atingido. Se nenhum caminho convergir, o decodificador retorna o caminho sobrevivente com o melhor par $(M, w)$.

Principais Contribuições

• Arquitetura de Decodificador Inovadora: O artigo introduz o decodificador RL-LS, que integra a busca baseada em lista ao framework de escalonamento sequencial aprendido. Ao contrário de abordagens anteriores baseadas em lista que adicionam um pós-processamento pesado ou executam bit-flipping paralelo após um prefixo fixo, o RL-LS realiza a expansão de lista dentro do próprio processo de atualização sequencial.
• Estratégia de Perturbação Suave: Os autores propõem um método específico para gerar trajetórias alternativas perturbando suavemente os LLRs em direção ao segundo melhor símbolo de Pauli, em vez de um flip rígido. Isso permite que o decodificador explore hipóteses concorrentes sem descartar a trajetória principal aprendida.
• Métrica de Caminho Cumulativa: Uma nova métrica é definida para classificar caminhos candidatos, equilibrando a verossimilhança das decisões locais contra o requisito global de consistência de síndrome.
• Extensão Estrita: O decodificador proposto é uma extensão estrita do decodificador RL-S subjacente; a trajetória RL-S ordinária é sempre preservada como um candidato na lista, garantindo que o desempenho do decodificador base nunca seja degradado.

Resultos Numéricos
Os autores avaliaram o decodificador RL-LS em códigos de referência QLDPC representativos, incluindo códigos Bivariate Bicycle (BB) e códigos A5, sobre o canal de depolarização.

• Ganhos de Desempenho: Resultados numéricos demonstram que o RL-LS supera significativamente o decodificador RL-S subjacente e os métodos convencionais baseados em BP (como QBP, QBPGD e BP-OSD-0) em termos de Taxa de Erro de Bloco (BLER).
• Eficiência: O método proposto alcança um desempenho de correção de erro superior com menos iterações. Por exemplo, no código BB [[288, 12, 18]], o RL-LS com um tamanho de lista $L=8$ e $T=100$ iterações alcançou um desempenho comparável ao RL-S com $T=1000$ iterações, oferecendo uma vantagem substancial de latência.
• Velocidade de Convergência: Os decodificadores baseados em aprendizado, particularmente o RL-LS, exigiram significativamente menos iterações médias para convergir em comparação com os decodificadores baseados em BP convencional através de várias probabilidades de depolarização.

Significância e Alegações
O artigo afirma que o decodificador RL-LS mitiga efetivamente os riscos de erros precoces na decodificação sequencial causados pela degenerescência quântica e ciclos curtos. Ao combinar a convergência melhorada do escalonamento sequencial aprendido com a exploração de lista leve, o método navega pelas ambiguidades locais de forma mais robusta do que as abordagens de trajetória única.

Os autores posicionam este trabalho como uma direção promissora para melhorar a confiabilidade da decodificação QLDPC baseada em BP. Eles enfatizam que a abordagem permanece totalmente dentro do framework de passagem de mensagens BP, evitando a complexidade de estágios de pós-processamento pesados, ao mesmo tempo em que oferece um compromisso favorável entre latência de decodificação e desempenho de correção de erro. Os resultados sugerem que integrar a busca baseada em lista ao escalonamento sequencial aprendido é uma estratégia viável para aumentar as arquiteturas quânticas tolerantes a falhas.