Noisy-Syndrome Decoding of Hypergraph Product Codes

Resumo Técnico: Decodificação de Síndrome Ruidosa de Códigos Produto de Hipergrafos

Enunciado do Problema
A tolerância a falhas quântica depende da decodificação de códigos de correção de erros quânticos para identificar e corrigir erros. Um desafio crítico nas implementações práticas é o problema da decodificação de síndrome ruidosa. Em hardware real, as medições de síndrome (verificações de paridade) são realizadas em dispositivos ruidosos, levando a bits de síndrome corrompidos independentemente dos erros de dados. Isso cria um cenário onde tanto os qubits de dados quanto a informação de síndrome estão sujeitos a erros adversariais.

O artigo aborda dois objetivos específicos neste contexto para códigos Produto de Hipergrafos (HGP), uma família prototípica de códigos quânticos com parâmetros de última geração:

1. Decodificação de Síndrome Ruidosa Estável: A saída do decodificador deve degradar-se graciosamente com o ruído da síndrome; pequenos erros de síndrome devem resultar apenas em erros proporcionalmente pequenos no erro de dados estimado.
2. Recuperação Exata: O decodificador deve recuperar o erro de dados verdadeiro exatamente ($wt_H(e - \hat{e}) = 0$) mesmo na presença de ruído de síndrome.

Trabalhos anteriores assumiam síndromes sem ruído, lidavam com modelos de ruído estocástico ou forneciam decodificação estável sem garantias de recuperação exata sob condições adversariais. Este trabalho visa fornecer uma estrutura geral para recuperação exata e decodificação estável de códigos HGP sob modelos de ruído totalmente adversariais.

Metodologia
A metodologia central é uma estrutura baseada em redução que transforma o problema de decodificação quântica para códigos HGP em problemas de decodificação clássica para os códigos lineares constituintes.

1. Divisão da Equação de Síndrome Ruidosa:
   Os autores observam que a equação de síndrome ruidosa para um código HGP construído a partir de matrizes de verificação de paridade $H_1$ e $H_2$ assume a forma:
   $$s + E = (H_1 \otimes I)x + (I \otimes H_2^T)y$$
   onde $x, y$ são erros de dados e $E$ é o ruído de síndrome. Ao definir um novo termo de erro $E' = E + (H_1 \otimes I)x$, a equação pode ser reescrita para isolar $y$:
   $$s + E' = (I \otimes H_2^T)y$$
   Devido à estrutura do produto de Kronecker, isso se divide em blocos independentes, cada um representando uma equação de síndrome ruidosa para o código clássico definido por $H_2^T$. Se o código clássico admitir decodificação de síndrome ruidosa eficiente, $y$ (e consequentemente $E'$) pode ser recuperado. Desdobrar a definição de $E'$ gera então uma segunda instância de síndrome ruidosa para $H_1$, permitindo a recuperação de $x$.

2. Decodificação Estável via Códigos Expansores:
   Para decodificação estável, os autores instanciam os códigos constituintes usando códigos expansores de Sipser-Spielman. Estes códigos possuem decodificadores de síndrome ruidosa clássicos (algoritmos de redução de erro) que operam em tempo quase linear. A redução em dois estágios descrita acima produz um decodificador quântico que corrige uma fração constante de erros em relação à distância do código em tempo $O(N^{3/2})$.

3. Recuperação Exata via Matrizes de Verificação de Paridade Aumentadas:
   Para recuperação exata, os autores exploram a observação de que a equação de síndrome ruidosa $s = Hx + E$ pode ser vista como um problema padrão de decodificação de síndrome (sem ruído) para uma matriz de verificação de paridade aumentada $[I : H]$.
   $$s = [I : H] \begin{bmatrix} E \\ x \end{bmatrix}$$
   Se o código definido por $[I : H]$ possuir propriedades favoráveis (grande distância e um decodificador de síndrome eficiente), o erro de dados $x$ pode ser recuperado exatamente apesar do ruído $E$. Os autores constroem códigos HGP usando matrizes de verificação de paridade derivadas de códigos de Reed-Solomon e códigos de Sipser-Spielman que satisfazem essas propriedades, permitindo recuperação exata em tempo $O(N^{3/2})$.

Contribuições e Resultados Principais

• Teorema 1.1 (Decodificação Estável): Os autores provam que, se um código constituinte clássico $C$ admite decodificação de síndrome ruidosa $(t, \eta, \alpha)$-estável, o código HGP resultante herda essa propriedade. Especificamente, eles instanciam isso com códigos expansores para construir códigos HGP que admitem decodificação de síndrome ruidosa $(\Theta(\sqrt{N}), \Theta(\sqrt{N}), 1/2)$-estável em tempo $O(N^{3/2})$.
• Teorema 1.2 (Recuperação Exata): Os autores mostram que, se tanto um código clássico $C$ quanto seu dual $C^\perp$ possuem parâmetros $[n, \Theta(n), \Theta(n)]$ e admitem decodificadores de síndrome eficientes, o código HGP resultante admite recuperação exata de $O(\sqrt{N})$ erros de dados adversariais e $O(\sqrt{N})$ erros de síndrome adversariais em tempo $O(N^{3/2})$.
• Instanciações:
  • Códigos de Reed-Solomon: Usados para instanciar o Teorema 1.2, fornecendo recuperação exata para códigos HGP construídos a partir de códigos polinomiais.
  • Códigos de Sipser-Spielman: Usados tanto para decodificação estável (Teorema 1.1) quanto para recuperação exata (via construções específicas na Seção 4), demonstrando que códigos HGP explícitos podem ser decodificados eficientemente sob ruído adversarial.
• Pesos dos Estabilizadores: Os códigos CSS quânticos construídos possuem verificações de estabilizador de peso $O(\sqrt{N})$. Os autores observam que, embora sejam sublineares, não são constantes, e estender essas técnicas para estabilizadores de peso $O(1)$ permanece uma questão em aberto.

Significado e Afirmações
O artigo afirma abordar uma lacuna na literatura ao fornecer uma abordagem geral, baseada em redução para decodificar códigos HGP na presença de ruído de síndrome adversarial. Diferentemente de trabalhos anteriores que dependiam de algoritmos quânticos específicos (como small-set-flip) ou assumiam síndromes sem ruído, esta estrutura:

• Reduz o problema quântico à decodificação de síndrome ruidosa clássica, isolando as propriedades do código constituinte clássico como o primitivo fundamental.
• Alcança recuperação exata sob ruído adversarial, uma capacidade não estabelecida anteriormente para códigos HGP neste contexto.
• Melhora o tempo de execução de decodificadores adversariais anteriores (por exemplo, decodificador ReShape) ao corresponder à escalabilidade ótima até fatores subpolinomiais ($O(N^{3/2})$).

Os autores posicionam seu trabalho como uma solução para uma questão em aberto proposta por Golowich e Guruswami [GG24], oferecendo uma estrutura unificada que lida tanto com recuperação estável quanto exata para uma ampla classe de códigos, incluindo aqueles derivados de expansores e códigos de Reed-Solomon. Eles enfatizam que seus resultados valem para modelos de ruído de pior caso (adversariais), distinguindo-os de análises de limiar probabilísticas.