Quantum LDPC Codes from Polynomial Minors

Resumo Técnico: Códigos Quantum LDPC a partir de Menores de Polinômios

Definição do Problema
A construção de códigos de verificação de paridade de baixa densidade (LDPC) quânticos frequentemente se baseia na estrutura de Calderbank-Shor-Steane (CSS), que requer dois códigos lineares binários clássicos, $C_X$ e $C_Z$, satisfazendo a condição de ortogonalidade $C_Z^\perp \subseteq C_X$. Embora códigos cíclicos ofereçam uma estrutura algébrica conveniente para gerar tais pares, determinar a dimensão e a distância mínima dos códigos quânticos resultantes pode ser complexo, particularmente ao lidar com estruturas quase-cíclicas (QC). Construções algébricas existentes, como códigos de bicicleta, códigos de bicicleta generalizados e códigos de produto levantado (lifted-product codes), utilizam várias abordagens polinomiais e algébrico-grupais. Este artigo aborda o desafio de construir códigos quânticos com controle explícito sobre a dimensão e distâncias mínimas verificadas usando matrizes polinomiais e seus menores.

Metodologia
Os autores propõem uma construção baseada em uma matriz polinomial $2 \times 3$ $H(x)$ sobre o anel $R_N = \mathbb{F}_2[x]/(x^N + 1)$, onde $N$ é o fator de levantamento. A construção procede da seguinte forma:

1. Formação da Matriz: As entradas da matriz $H_X(x)$ são escolhidas como palavras-código de um código cíclico gerado por um polinômio $g(x)$. Especificamente, os autores utilizam uma forma especializada onde a segunda linha é determinada pela primeira linha via um deslocamento e permutação, reduzindo o número de polinômios independentes necessários.
2. Construção Baseada em Menores: Os três menores $2 \times 2$ da matriz $2 \times 3$ $H_X(x)$ são computados. Estes menores formam as linhas de uma segunda matriz polinomial, $H_Z(x)$.
3. Ortogonalidade: Com base no Lema 1 e no Teorema 2 de literatura prévia, os autores demonstram que os menores de uma matriz residem naturalmente no núcleo dessa matriz. Consequentemente, a construção garante a condição de ortogonalidade CSS $H_X H_Z^T = 0$, assegurando a existência de um código quântico válido $Q(C_X, C_Z)$ de comprimento $3N$.
4. Análise de Dimensão: A dimensão $K$ do código quântico é derivada dos invariantes de Smith das matrizes polinomiais. Os autores expressam $K$ em termos dos máximos divisores comuns (mdc) das entradas e dos menores em relação a $x^N + 1$. Para $N$ ímpar, a fórmula simplifica-se para $K = \deg(g) + 2\deg(g_1)$, onde $g$ é o mdc das entradas e $g_1$ é o mdc dos menores.
5. Controle de Dimensão: Para controlar a dimensão, os autores introduzem condições de resíduo. Ao selecionar polinômios $a, b, c$ de modo que seus resíduos módulo fatores irredutíveis específicos de $x^N + 1$ satisfaçam relações algébricas específicas (por exemplo, formar uma matriz de posto 1 módulo um fator), fatores comuns adicionais podem ser introduzidos nos menores, aumentando assim a dimensão do código sem alterar o seu comprimento.
6. Modificação do Gerador: O artigo fornece uma condição (Proposição 7) para multiplicar o vetor dos menores por um polinômio $q$ para alterar os pesos dos geradores de $H_Z$ sem alterar o espaço do código ou sua dimensão, desde que $\gcd(q, (x^N+1)/g_1) = 1$.

Principais Contribuições

• Construção Explícita: Um método sistemático para gerar códigos quânticos CSS a partir de uma matriz polinomial $2 \times 3$ onde os estabilizadores $Z$ são derivados diretamente dos menores da matriz de estabilizadores $X$.
• Fórmula de Dimensão: Uma fórmula simplificada para a dimensão do código para fatores de levantamento $N$ ímpares, expressa explicitamente através dos graus dos mdc das entradas e dos menores.
• Caracterização de Resíduos: Uma caracterização de como os resíduos polinomiais módulo fatores irredutíveis de $x^N + 1$ influenciam o mdc dos menores, oferecendo um método para projetar a dimensão do código através da seleção de resíduos polinomiais específicos.
• Gerenciamento de Peso: Uma técnica utilizando multiplicadores para reduzir os pesos das linhas da matriz $H_Z$ enquanto preserva as propriedades do código.

Resultos
Os autores apresentam construções polinomiais explícitas que resultam em 13 códigos quânticos com distâncias mínimas verificadas. Resultados notáveis incluem:

• Um código [[255, 80, 12]] com uma taxa de aproximadamente 0,3137. A distância mínima $d=12$ foi estabelecida através de operadores lógicos explícitos e enumeração exaustiva.
• Um código [[189, 58, 10]].
• Um código [[153, 51, 8]] com uma taxa de exatamente 1/3.
• Vários outros códigos com comprimentos variando de 27 a 255 qubits.

Para o código [[255, 80, 12]], os autores verificaram que a distância-$X$ é 12 e a distância-$Z$ é de pelo menos 12 (com um limite superior de 20). A construção utilizou polinômios com pesos baixos para $H_X$ (peso 22) e pesos mais altos para $H_Z$ (peso 61) usando o multiplicador identidade ($q=1$). O artigo observa que, embora multiplicadores possam ser usados para reduzir esses pesos, o exemplo específico apresentado não empregou tal otimização.

Significância
O artigo afirma que esta construção fornece um elo algébrico direto entre os menores de uma matriz polinomial e a ortogonalidade exigida para códigos CSS. A principal significância reside na capacidade de controlar explicitamente a dimensão do código através da seleção de polinômios e condições de resíduo, em vez de depender de buscas aleatórias ou heurísticas. Além disso, os autores enfatizam que as distâncias mínimas para os códigos apresentados são verificadas exatamente através de enumeração exaustiva e análise de operadores lógicos, um padrão rigoroso frequentemente difícil de alcançar para grandes códigos quânticos. O trabalho estende a família de conhecidas construções algébricas de QLDPC, oferecendo parâmetros específicos que podem ser úteis para implementações práticas, embora os autores notem que o desempenho de decodificação e códigos com pesos baixos tanto em $H_X$ quanto em $H_Z$ permanecem tópicos para trabalhos futuros.