A Factor-Graph Formulation of CSS Syndrome Decoding: Joint BP and Four-State BP

Resumo Técnico: Uma Formulação de Grafo-Fatorial para Decodificação de Síndrome CSS

Enunciado do Problema
O artigo aborda a formulação da decodificação por propagação de crenças (BP) para códigos Calderbank-Shor-Steane (CSS). Na decodificação de síndrome CSS, a distribuição a posteriori dos erros de Pauli é restringida por duas matrizes de verificação de paridade binárias ($H_X$ e $H_Z$) atuando sobre os componentes de erro $X$ e $Z$, respectivamente. Um desafio central na decodificação desses códigos é lidar com a correlação local entre os componentes de erro $X$ e $Z$ em cada qubit, particularmente quando o canal não é um produto simples de erros $X$ e $Z$ independentes (por exemplo, o canal despolarizante).

As abordagens existentes geralmente se enquadram em duas categorias:

1. BP Separada: Decodifica os componentes $X$ e $Z$ independentemente usando dois grafos de Tanner binários desconectados. Esta abordagem descarta a correlação local $X/Z$ substituindo a priori conjunta $Q_j(x_j, z_j)$ por priores marginais.
2. BP de Quatro Estados: Trata cada qubit como uma única variável sobre o corpo $\mathbb{F}_4$ (ou o conjunto dos quatro estados de Pauli), utilizando um único grafo de Tanner de quatro estados. Embora isso preserve a correlação, afasta-se da estrutura de grafo-fatorial binária padrão no projeto de códigos de Paridade de Verificação de Baixa Densidade (LDPC).

O artigo investiga se uma representação de grafo-fatorial binária pode reter a correlação local $X/Z$ sem recorrer a uma representação completa de quatro estados e, em caso afirmativo, como ela se relaciona matematicamente com a abordagem de quatro estados.

Metodologia
O autor formaliza o problema de decodificação usando grafos-fatoriais e o algoritmo soma-produto. Três formulações específicas de decodificador são definidas com base em diferentes fatorizações a posteriori:

1. Decodificador BP Conjunta: Este é o foco principal. Utiliza um grafo-fatorial binário acoplado com dois conjuntos de nós de variável binária ($X$ e $Z$) e dois conjuntos de nós de verificação. Crucialmente, a priori local em cada qubit $j$ é a distribuição conjunta $Q_j(x_j, z_j)$. Este fator acopla as duas variáveis binárias, permitindo que a informação flua entre os componentes $X$ e $Z$ através do nó local, mantendo ao mesmo tempo as restrições de verificação binária.
2. Decodificador BP Separada: Um decodificador de referência onde a priori conjunta $Q_j(x_j, z_j)$ é substituída por suas marginais $Q^X_j(x_j)$ e $Q^Z_j(z_j)$. Isso resulta em dois decodificadores binários independentes que ignoram as correlações locais.
3. Decodificador BP de Quatro Estados: Um decodificador onde cada qubit é representado por uma única variável $\alpha_j \in \mathbb{F}_4$ através do reetiquetamento $\alpha = x + \omega z$. A priori local é transformada de acordo, e as restrições de verificação operam sobre as coordenadas binárias específicas de $\alpha$.

O núcleo da metodologia envolve a derivação das equações de atualização soma-produto tanto para o BP Conjunto (binário) quanto para o BP de Quatro Estados ($\mathbb{F}_4$). O autor realiza então uma comparação matemática rigorosa das dinâmicas de passagem de mensagens entre essas duas formulações.

Principais Contribuições e Resultados
A contribuição central do artigo é o Teorema 1, que estabelece uma equivalência precisa entre o decodificador BP Conjunta e o decodificador BP de Quatro Estados. O teorema demonstra que:

• Equivalência A Posteriori: Os pesos a posteriori não normalizados atribuídos às configurações de erro correspondentes são idênticos sob o mapa de reetiquetamento $\phi(x, z) = x + \omega z$.
• Equivalência de Mensagens: As mensagens passadas no decodificador BP de Quatro Estados podem ser mapeadas diretamente para as mensagens no decodificador BP Conjunta. Especificamente, as mensagens de verificação-para-variável de quatro estados marginalizam-se para as mensagens de verificação-para-variável binárias, e as mensagens de variável-para-verificação binárias correspondem à marginalização das mensagens de variável-para-verificação de quatro estados.
• Equivalência de Crenças: As crenças finais (probabilidades marginais) em cada qubit são idênticas sob o reetiquetamento. Consequentemente, as decisões rígidas (estimativas de máxima verossimilhança a posteriori) tomadas por ambos os decodificadores são idênticas.

A prova baseia-se em manipulações padrão do algoritmo soma-produto, mostrando que, como as restrições de verificação no grafo de quatro estados dependem apenas de uma coordenada binária do rótulo (por exemplo, as verificações $X$ dependem apenas de $z$), o algoritmo soma-produto naturalmente soma a coordenada irrelevante. Esse processo recupera a passagem de mensagens binárias acopladas exata do decodificador BP Conjunta.

Adicionalmente, o artigo fornece uma formulação de Razão de Verossimilhança Logarítmica (LLR) para o decodificador BP Conjunta. Isso permite que o algoritmo seja implementado eficientemente no domínio logarítmico, semelhante aos decodificadores LDPC binários padrão, enquanto ainda incorpora a priori conjunta $Q_j$ através de uma atualização de tabela $2 \times 2$ nos nós de variável.

Significado e Alegações
O artigo faz uma alegação modesta, mas precisa, sobre a natureza da decodificação CSS:

1. Distinção da BP Separada: O artigo esclarece que "BP binária" não implica inerentemente "BP separada". A perda de correlação na BP separada é um resultado da marginalização da priori antes da decodificação, não uma limitação inerente ao uso de mensagens binárias.
2. Equivalência de Representações: A capacidade de utilizar a correlação do canal local $X/Z$ é uma propriedade da fatorização a posteriori, e não do tamanho do alfabeto das mensagens. O BP Conjunto (binário acoplado) e o BP de Quatro Estados são mostrados como duas representações diferentes do mesmo cálculo soma-produto exato.
3. Representação Natural: Para códigos CSS especificamente, o grafo-fatorial binário acoplado (BP Conjunta) é apresentado como a representação "natural". Ele retém a estrutura familiar de grafo de Tanner binária e a complexidade do nó de verificação dos códigos LDPC clássicos, enquanto preserva totalmente as correlações locais do canal que são frequentemente perdidas na decodificação separada.

O artigo não alega introduzir um novo algoritmo de decodificação com desempenho superior ao BP de quatro estados; em vez disso, prova que a abordagem binária acoplada é matematicamente equivalente à abordagem de quatro estados para códigos CSS, validando assim o uso de grafos-fatoriais binários para decodificação CSS correlacionada sem sacrificar a optimalidade teórica (dentro do quadro BP).