An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise

Resumo Técnico: Um Algoritmo de Decodificação de Tempo Quase-Linear para Códigos QLDPC sob Ruído de Nível de Circuito

Definição do Problema
A realização prática da computação quântica tolerante a falhas exige a decodificação em tempo real de síndromes de correção de erros quânticos (QEC), frequentemente dentro de escalas de microssegundos. Embora a Propagação de Crença (BP) ofereça uma abordagem de decodificação rápida de tempo linear ($O(n)$) adequada para códigos de Verificação de Paridade de Baixa Densidade (LDPC), ela frequentemente falha em convergir em códigos LDPC Quânticos (QLDPC) devido a erros degenerados e conjuntos de aprisionamento (trapping sets). Decodificadores de alto desempenho existentes, como o Ordered Statistics Decoding (BP+OSD) ou decodificadores baseados em emparelhamento, frequentemente dependem de técnicas de inversão de matriz que aumentam a complexidade de tempo de pior caso para $O(n^3)$, criando um gargalo para a implementação de hardware em tempo real. Além disso, a decodificação sob ruído de nível de circuito (em vez de ruído fenomenológico) introduz mecanismos complexos de propagação de erro que são difíceis de lidar com a BP padrão, particularmente quando o modelo de erro do detector (DEM) contém colunas de alto peso e loops curtos que dificultam as estratégias de pós-processamento.

Metodologia
Os autores propõem um arcabouço de decodificação híbrido, BP+BP+OTF, projetado para alcançar complexidade de tempo quase-linear enquanto mantém alta supressão de erro sob ruído de nível de circuito. A metodologia consiste em três estágios principais:

1. Esparsificação do Grafo do Detector:
   Os autores introduzem uma técnica para mapear o modelo de erro do detector completo ($H_{dem}$), que relaciona os mecanismos de falha do circuito às medições de síndrome, para um grafo do detector esparsificado ($H_{sdem}$). Este grafo esparsificado possui um peso máximo de coluna comparável às matrizes de verificação de paridade do código (tipicamente $\leq 2$ para códigos de superfície ou constantes baixas para QLDPC).

   • Uma matriz de transferência ($A_{tr}$) é construída para mapear o DEM completo para o DEM esparsificado. Esta matriz garante que a ação lógica dos erros seja preservada e permite a tradução da informação suave (soft information — probabilidades de erro) do grafo completo para o grafo esparsificado.
   • A esparsificação reduz o número de colunas (mecanismos de erro) e elimina loops curtos, tornando o grafo mais adequado para o pós-processamento baseado em árvores.

2. Propagação de Crença de Dois Estágios (BP+BP):

   • Estágio 1: A BP padrão é aplicada ao grafo do detector completo para extrair a informação suave inicial sobre as probabilidades de erro.
   • Estágio 2: A informação suave do Estágio 1 é mapeada para o grafo do detector esparsificado usando a matriz de transferência. Uma segunda rodada de BP é executada neste grafo esparsificado. Este estágio beneficia-se de um canal de erro não uniforme derivado da primeira rodada, o que acelera a convergência.

3. Pós-Processamento de Floresta de Tanner Ordenada (OTF):
   Se os estágios de BP não satisfizerem a síndrome, o algoritmo OTF é invocado no grafo esparsificado.

   • Mecanismo: O algoritmo OTF utiliza uma versão modificada do algoritmo de Kruskal para construir uma floresta geradora ordenada. Ele ordena os qubits (colunas da matriz de verificação de paridade) com base em suas probabilidades de erro a posteriori (da saída da BP) e adiciona iterativamente os elementos ao grafo, descartando qualquer coluna que introduza um loop.
   • Convergência: O grafo resultante é uma floresta (uma coleção de árvores). Como a BP é garantida para convergir em estruturas do tipo árvore, uma rodada final de BP neste grafo de floresta é garantida para encontrar uma solução se a síndrome estiver dentro da imagem da matriz reduzida.
   • Complexidade: Os passos de ordenação e construção da floresta têm uma complexidade de $O(n \log n)$, e o passo final de BP é $O(n)$, resultando em uma complexidade de tempo quase-linear global.

Principais Contribuições

• Pós-Processador OTF: A introdução do algoritmo Ordered Tanner Forest como um pós-processador que evita a inversão de matriz, oferecendo uma alternativa aos métodos de inversão baseados em $O(n^3)$ como o BP+OSD.
• Esparsificação com Matrizes de Transferência: Um procedimento inovador para mapear modelos de erro de detector de nível de circuito para grafos mais esparsos, preservando informações críticas de propagação de erro via matriz de transferência. Isso permite que o decodificador aproveite a estrutura do modelo de ruído de circuito completo sem ser prejudicado por sua complexidade.
• Arquitetura BP+BP+OTF: Um decodificador unificado que combina BP padrão, BP esparsificada e pós-processamento OTF, especificamente otimizado para ruído de nível de circuito.
• Viabilidade de Hardware: O algoritmo baseia-se em BP padrão e no algoritmo de Kruskal, ambos altamente adequados para implementação em ASICs ou FPGAs comerciais.

Resultados
Os autores testaram o decodificador BP+BP+OTF usando simulações de Monte Carlo em códigos de bicicleta bivariados e códigos de superfície rotacionados sob ruído de nível de circuito depolarizante.

• Desempenho: O decodificador alcança uma supressão de erro lógico comparável à de decodificadores de última geração. Para códigos de bicicleta bivariados, ele iguala o desempenho do BP+OSD-0. Para códigos de superfície, atinge supressão comparável ao MWPM (Minimum-Weight Perfect Matching) e supera significativamente o BP+OSD-0.
• Velocidade: A implementação demonstra um aumento de velocidade de mais de 10x em comparação com uma implementação padrão de BP+OSD (especificamente referenciando a implementação em [27]) ao decodificar códigos de bicicleta bivariados.
• Eficiência: Para códigos de superfície, o decodificador alcança decodificação confiável com um número muito pequeno de iterações (por exemplo, 107 iterações totais de BP para um código de distância-17).
• Eficácia da Esparsificação: Experimentos mostraram que aplicar a BP diretamente ao modelo esparsificado sem a rodada inicial do grafo completo degrada o desempenho, mas a abordagem híbrida BP+BP recupera o desempenho do decodificador do modelo completo, reduzindo o tempo médio de decodificação em um fator de três.

Significância
O artigo afirma que o BP+BP+OTF representa um passo significativo em direção aos requisitos de decodificação em tempo real para computadores quânticos tolerantes a falhas. Ao alcançar complexidade de tempo quase-linear ($O(n \log n)$) sem sacrificar os limiares de erro de métodos mais lentos baseados em inversão, o algoritmo aborda o gargalo crítico da latência de decodificação. Os autores enfatizam que a dependência do decodificador de algoritmos padrão e bem compreendidos (BP e Kruskal) o torna um candidato altamente atraente para aceleração de hardware, permitindo potencialmente a construção de sistemas tolerantes a falhas com menores custos de desenvolvimento e maior escalabilidade em comparação com decodificadores especializados complexos. O trabalho também sugere que a técnica de esparsificação pode beneficiar outras famílias de decodificadores além da arquitetura específica BP+BP+OTF proposta.