Multiple-Bases Belief Propagation List Decoding for Quantum LDPC Codes

Resumo Técnico: Decodificação por Lista de Propagação de Crenças com Múltiplas Bases para Códigos QLDPC Quânticos

Declaração do Problema
Os códigos de Paridade-Verificação Quântica de Baixa Densidade (QLDPC) são críticos para a computação quântica tolerante a falhas escalável devido às suas matrizes de verificação de paridade esparsas, que minimizam as interações entre qubits. No entanto, o desempenho da decodificação padrão por Propagação de Crenças (BP) para códigos QLDPC é frequentemente degradado pela degenerescência do código, ciclos curtos e conjuntos de armadilha no gráfico de Tanner. Embora decodificadores de alto desempenho existentes, como BP com Decodificação por Estatísticas Ordenadas (BP-OSD) e Propagação de Crenças com Decimação Guiada (BPGD), ofereçam taxas de erro melhoradas, eles sofrem de desvantagens significativas: o BP-OSD requer complexidade de pós-processamento superlinear ($O(n^3)$), e o BPGD envolve altos contagens de iterações e etapas de decimação complexas, levando ao aumento da latência e do custo computacional. Há uma necessidade de uma estratégia de decodificação que melhore o desempenho da taxa de erro em relação ao BP padrão, mantendo a complexidade de tempo linear e evitando pós-processamento superlinear.

Metodologia
O artigo propõe o Decodificador por Lista de Propagação de Crenças com Múltiplas Bases (MBBP-LD). Esta estrutura estende o conceito clássico de Propagação de Crenças com Múltiplas Bases (MBBP) para o cenário quântico, gerando diversidade estruturada de decodificação sem depender de seleção aleatória de linhas ou pós-processamento complexo.

1. Representações Redundantes Estruturadas: Em vez de duplicar aleatoriamente linhas de verificação de paridade (como na Decodificação de Paridade-Verificação Aumentada), o método proposto constrói múltiplas representações redundantes de verificação de paridade usando decomposições de subárvores sem ciclos do gráfico de Tanner.

   • O algoritmo particiona os nós de verificação em uma coleção de subárvores maximais ($\mathcal{T}$) com base em uma permutação específica dos nós de verificação.
   • Uma subárvore é definida como maximal se a adição de qualquer nó de verificação adjacente criasse um ciclo.
   • Para cada subárvore $t \in \mathcal{T}$, uma matriz de verificação de paridade aumentada $H^{(t)}$ é formada anexando a submatriz correspondente à subárvore ($H_t$) à matriz original $H$.
   • O Lema 1 estabelece que, para grafos regulares de verificação, o número de linhas adicionais introduzidas é limitado, garantindo que a aumento não aumente drasticamente a complexidade.

2. Decodificação Paralela e Agregação de Lista:

   • Múltiplos decodificadores BP executam em paralelo, cada um operando em uma matriz aumentada distinta $H^{(t)}$.
   • Decodificadores que convergem dentro de um limite fixo de iterações contribuem com suas estimativas de erro para uma lista de candidatos $\mathcal{L}$.

3. Regra de Decisão (Pontuação Ponderada por Frequência):

   • Uma função de decisão $f_{DM}$ seleciona a estimativa de erro final da lista de candidatos.
   • A regra proposta de Pontuação Ponderada por Frequência (FWS) atribui uma pontuação a cada candidato com base em sua frequência de ocorrência na lista e seu peso de Hamming:
     $$\text{Pontuação}(e) = \frac{|\{e' \in \mathcal{L} : e' = e\}|}{w_H(e) + 1}$$
   • Esta regra favorece candidatos que aparecem repetidamente (indicando robustez através de diferentes estruturas de gráfico) enquanto penaliza erros de alto peso. Se nenhum decodificador convergir, o sistema declara uma falha e retorna o vetor de todos os zeros.

Principais Contribuições

• Diversidade Estruturada: O artigo introduz um método determinístico, baseado em subárvores, para construir representações redundantes de verificação de paridade, contrastando com abordagens anteriores de aumento aleatório. Esta estrutura é projetada para induzir trajetórias de decodificação diversas que mitigam os efeitos dos conjuntos de armadilha.
• Preservação da Complexidade: A estrutura mantém a complexidade de tempo linear e a eficiência de hardware do BP padrão. Sob implementação paralela, a latência de decodificação permanece comparável ao BP padrão, pois o número de linhas adicionais é limitado por um fator constante em relação ao comprimento do bloco.
• Evitação de Pós-Processamento Superlinear: Ao contrário do BP-OSD e do BPGD, o MBBP-LD evita estágios de decimação com $O(n^3)$ ou alto custo, oferecendo uma alternativa mais eficiente para implementação prática.

Resultados Numéricos
Simulações foram conduzidas em códigos de bicicleta bivariados ($[[144, 12, 12]]$ e $[[288, 12, 18]]$) e no código B1 ($[[882, 24, 18 \le d \le 24]]$) sobre um canal simétrico binário com erros do tipo X independentes.

• Ganhos de Desempenho: O MBBP-LD supera consistentemente o BP-OSD e o BPGD em vários regimes de ruído.
  • Para o código $[[144, 12, 12]]$, ele alcança uma redução de 3–24% na Taxa de Erro Lógico (LER) em comparação com o BP-OSD e de 7–17% em comparação com o BPGD.
  • Para o código $[[288, 12, 18]]$, as reduções chegam a 49% em comparação com o BP-OSD e 36% em comparação com o BPGD.
  • Para o código B1 maior, o MBBP-LD alcança mais de 91% de redução na LER em comparação com o BP-OSD em $p=0,04$ e até 66% de redução em comparação com o BPGD paralelo.
• Eficiência: Embora o BPGD-Serial às vezes mostre uma LER ligeiramente melhor em regimes de baixo ruído, ele incorre em custos computacionais significativamente mais altos (por exemplo, em $p=0,04$, o BPGD-Serial média 2,5 iterações por estágio, mas requer decodificação repetida, enquanto o MBBP-LD média 14,4 iterações totais). O MBBP-LD mantém uma contagem de iterações comparável ao BP padrão, preservando latência semelhante à do BP.
• Subárvore vs. Aleatório: Comparações no código $[[288, 12, 18]]$ mostram que partições baseadas em subárvores produzem consistentemente uma LER mais baixa do que partições aleatórias correspondentes, com melhorias variando de 2,5% a 9,4%, particularmente em regimes de baixo ruído.

Significado e Alegações
O artigo afirma que o MBBP-LD conecta com sucesso a lacuna entre o alto desempenho de decodificadores complexos com pós-processamento e a eficiência do BP padrão. Ao aproveitar as propriedades semelhantes a árvores das estruturas locais de grafos para criar redundância estruturada, o decodificador melhora a convergência e as capacidades de correção de erros sem sacrificar a complexidade de tempo linear essencial para a computação quântica escalável. Os autores posicionam isso como uma solução prática que evita o custo superlinear dos métodos de alto desempenho existentes, enquanto entrega melhorias substanciais na taxa de erro. Trabalhos futuros são notados como focados em construções específicas de códigos de verificações redundantes e regras de decisão refinadas.