Sequences of Bivariate Bicycle Codes from Covering Graphs

Resumo Técnico: Sequências de Códigos de Biciclo Bivariados a partir de Grafos de Recobrimento

Enunciado do Problema

Códigos de Verificação de Paridade de Baixa Densidade Quântica (qLDPC) oferecem uma alternativa promissora aos códigos de superfície, fornecendo taxas constantes e uma melhor escala de distância, o que pode reduzir o overhead de espaço necessário para a computação quântica tolerante a falhas. No entanto, identificar novos códigos qLDPC de alto desempenho permanece um desafio devido ao vasto espaço de busca de possíveis polinômios de verificação de paridade. Especificamente, os códigos de Biciclo Bivariado (BB), que são códigos de álgebra de grupo definidos sobre $\mathbb{F}_2[Z_l \times Z_m]$, mostraram potencial com instâncias de alta taxa e alta distância (por exemplo, o código "gross" [[144, 12, 12]]), mas um método geral para gerar famílias infinitas de tais códigos com parâmetros previsíveis tem sido limitado. Além disso, compreender a relação entre operadores lógicos e automorfismos através de diferentes instâncias de códigos é crucial para implementar operações lógicas, mas muitas vezes é difícil de analisar para códigos grandes.

Metodologia

Os autores propõem um framework para gerar sequências infinitas de códigos BB usando o conceito matemático de grafos de recobrimento (ou levantamentos de grafos). A metodologia central envolve:

1. Condições Algébricas para Recobrimento: O artigo estabelece que um grafo de Tanner de um código BB $\tilde{Q}$ é um grafo de recobrimento de um código BB base $Q$ se condições algébricas específicas forem atendidas em relação aos seus parâmetros de rede e polinômios definidores. Especificamente, se $Q$ possui parâmetros $(l, m)$ e polinômios $A, B$, um código de recobrimento $\tilde{Q}$ com parâmetros $(\tilde{l}, \tilde{m})$ e polinômios $\tilde{A}, \tilde{B}$ é um $h$-recobrimento válido (onde $h = \tilde{l}\tilde{m}/lm$) se:

   • $\tilde{l} = ul$ e $\tilde{m} = tm$ para inteiros $u, t$.
   • Os expoentes dos monômios em $\tilde{A}$ e $\tilde{B}$ são congruentes com os de $A$ e $B$ módulo $l$ e $m$, respectivamente.
   • A atribuição de voltagem usada para gerar o grafo derivado corresponde ao "quociente" dos parâmetros de rede.

2. Espaço de Busca Reduzido: Ao restringir a busca a polinômios que satisfazem essas condições de congruência, os autores reduzem drasticamente o espaço de busca para novos códigos. Em vez de buscar no espaço total de polinômios de comprimento $n$, a busca é limitada a variações dos polinômios de um código base, reduzindo a complexidade de $O(n^6)$ para aproximadamente $O(h^4)$ para $h$-recobrimentos.

3. Mapas de Cadeia e Homologia: O mapa de recobrimento de grafo é estendido para um mapa de cadeia entre os complexos de cadeia dos códigos base e de recobrimento. Isso induz mapas em (co)homologia:

   • Mapa de Projeção ($p$): Mapeia operadores lógicos do código de recobrimento para o código base.
   • Mapa de Levantamento ($\tau$): Mapeia operadores lógicos do código base para o código de recobrimento.
   • Levantamento de Preservação de Peso ($\sigma$): Um tipo específico de levantamento que seleciona uma única pré-imagem para cada vértice, usado para estabelecer um limite superior para a distância do código de recobrimento.

4. Levantamento de Automorfismo: O framework é estendido para mostrar que os automorfismos de grafo (e, consequentemente, os automorfismos de código CSS) podem ser levantados do base para o de recobrimento. Sob condições específicas (h ímpar e contagens iguais de qubits lógicos), a ação lógica desses automorfismos é preservada.

Contribuições Principais e Resultados

• Geração de Sequências de Códigos: Os autores demonstram que códigos BB conhecidos de alto desempenho, como o código gross [[144, 12, 12]], podem ser vistos como duplos recobrimentos de códigos menores (ex: [[72, 12, 6]]). Eles geram sequências infinitas de novos códigos BB com contagens de qubits lógicos ($k$) fixas e tamanhos de bloco ($n$) crescentes.
• Novas Famílias de Códigos:
  • Códigos de Peso 6: O método reproduz famílias conhecidas, incluindo códigos de produto balanceado e códigos de toros generalizados, e gera novas sequências para $k=6, 8, 10, 12$.
  • Códigos de Peso 8: Os autores aplicam o método para buscar códigos BB com verificações de peso 8 (4 termos nos polinômios definidores). Eles encontram sequências com $k=8, 10, 12, 14$ que exibem razões $kd^2/n$ significativamente maiores que suas contrapartes de peso 6. Exemplos notáveis incluem os códigos [[64, 14, 8] e [[144, 14, 14]].
  • Códigos de Qudits: A metodologia é generalizada para códigos de qudits sobre $\mathbb{F}_q$, gerando com sucesso códigos de recobrimento para códigos BB de qudits base.
• Limites Teóricos:
  • Qubits Lógicos ($k$): Os autores provam que, para um código de $h$-recobrimento com $h$ ímpar, o número de qubits lógicos satisfaz $k_h \ge k$. Eles conjecturam que isso se aplica para todo $h$.
  • Distância ($d$): Para $h$ ímpar, eles provam o limite superior $d_h \le hd$. Se $k_h = k$ e $h$ é ímpar, eles provam o limite inferior $d_h \ge d$. Eles conjecturam que o limite geral $d \le d_h \le hd$ se aplica para todo $h$.
  • Levantamentos de Preservação de Peso: Eles mostram que, se um levantamento de preservação de peso existe, isso implica $d_h \le d$, fornecendo uma ferramenta numérica para descartar códigos de recobrimento onde a distância não aumenta.
• Análise de Operadores Lógicos e Automorfismos: O artigo fornece construções explícitas para levantar operadores lógicos e automorfismos. Ele prova que, quando $h$ é ímpar e $k_h = k$, o mapa de levantamento é um isomorfismo na homologia, garantindo que uma base lógica do código base se levante para uma base lógica completa do código de recobrimento, preservando a ação lógica de automorfismos (ex: portas CNOT e Hadamard lógicas).

Significância

Os autores afirmam que o trabalho é significativo em três áreas principais:

1. Descoberta Eficiente de Códigos: Ao identificar um espaço de busca reduzido baseado na teoria de grafos de recobrimento, os autores fornecem um método sistemático e eficiente para descobrir novos códigos BB com parâmetros promissores, evitando a necessidade de buscas por força bruta sobre o espaço total de polinômios.
2. Unificação Teórica: O trabalho unifica várias construções conhecidas de códigos BB (incluindo o código gross, códigos de produto balanceado e códigos de toros generalizados) sob um único framework de grafos de recobrimento, revelando relações estruturais entre eles.
3. Gestão de Operadores Lógicos: O desenvolvimento de mapas de projeção e levantamento oferece uma ferramenta prática para analisar códigos grandes. Ao derivar operadores lógicos e automorfismos de códigos base menores e bem compreendidos, a complexidade de gerenciar operações lógicas em grandes códigos qLDPC é reduzida.

Os autores observam que, embora o foco seja em códigos BB, os métodos devem se generalizar para outros códigos de álgebra de grupo e construções envolvendo hipergrafos ou produtos levantados. Eles também destacam que, embora o espaço de busca seja reduzido, calcular a distância exata de grandes códigos de recobrimento continua sendo um gargalo, e seus limites teóricos servem como um guia, em vez de uma solução completa para o cálculo da distância.