Sequences of Bivariate Bicycle Codes from Covering Graphs

Resumen Técnico: Secuencias de Códigos de Bicicletas Bivariantes a partir de Grafos de Recubrimiento

Planteamiento del Problema
Los códigos de comprobación de paridad de baja densidad cuántica (qLDPC) ofrecen una alternativa prometedora a los códigos de superficie al proporcionar tasas constantes y una mejora en la escala de la distancia, lo que potencialmente reduce la sobrecarga de espacio requerida para la computación cuántica tolerante a fallos. Sin embargo, la identificación de nuevos códigos qLDPC de alto rendimiento sigue siendo un desafío debido al vasto espacio de búsqueda de posibles polinomios de comprobación de paridad. Específicamente, los códigos de Bicicleta Bivariante (BB), que son códigos de álgebra de grupos definidos sobre $\mathbb{F}_2[Z_l \times Z_m]$, han mostrado potencial con instancias de alta tasa y alta distancia (por ejemplo, el código "gross" [[144, 12, 12]]), pero un método general para generar familias infinitas de tales códigos con parámetros predecibles ha sido limitado. Además, comprender la relación entre los operadores lógicos y los autótopismos a través de diferentes instancias de códigos es crucial para implementar operaciones lógicas, pero suele ser difícil de analizar para códigos grandes.

Metodología
Los autores proponen un marco para generar secuencias infinitas de códigos BB utilizando el concepto matemático de grafos de recubrimiento (o elevaciones de grafos). La metodología central consiste en:

1. Condiciones Algebraicas para el Recubrimiento: El artículo establece que un grafo de Tanner de un código BB $\tilde{Q}$ es un grafo de recubrimiento de un código BB base $Q$ si se cumplen ciertas condiciones algebraicas con respecto a sus parámetros de red y polinomios definitorios. Específicamente, si $Q$ tiene parámetros $(l, m)$ y polinomios $A, B$, un código de recubrimiento $\tilde{Q}$ con parámetros $(\tilde{l}, \tilde{m})$ y polinomios $\tilde{A}, \tilde{B}$ es un $h$-recubrimiento válido (donde $h = \tilde{l}\tilde{m}/lm$) si:

   • $\tilde{l} = ul$ y $\tilde{m} = tm$ para enteros $u, t$.
   • Los exponentes de los monomios en $\tilde{A}$ y $\tilde{B}$ son congruentes con los de $A$ y $B$ módulo $l$ y $m$, respectivamente.
   • La asignación de voltaje utilizada para generar el grafo derivado corresponde al "cociente" de los parámetros de la red.

2. Espacio de Búsqueda Reducido: Al restringir la búsqueda a polinomios que satisfacen estas condiciones de congruencia, los autores reducen drásticamente el espacio de búsqueda de nuevos códigos. En lugar de buscar en el espacio completo de polinomios de longitud $n$, la búsqueda se limita a variaciones de los polinomios de un código base, reduciendo la complejidad de $O(n^6)$ a aproximadamente $O(h^4)$ para $h$-recubrimientos.

3. Mapas de Cadena y Homología: El mapa de recubrimiento de grafos se extiende a un mapa de cadena entre las cadenas de complejos del código base y del código de recubrimiento. Esto induce mapas en la (co)homología:

   • Mapa de Proyección ($p$): Mapea los operadores lógicos del código de recubrimiento al código base.
   • Mapa de Elevación ($\tau$): Mapea los operadores lógicos del código base al código de recubrimiento.
   • Elevación de Preservación de Peso ($\sigma$): Un tipo específico de elevación que selecciona una única preimagen para cada vértice, utilizado para acotar superiormente la distancia del código de recubrimiento.

4. Elevación de Autotopismos: El marco se extiende para mostrar que los autótopismos de grafos (y, consecuentemente, los autótopismos de códigos CSS) pueden elevarse del base al de recubrimiento. Bajo condiciones específicas (h impar y conteos de cúbits lógicos iguales), la acción lógica de estos autótopismos se preserva.

Contribuciones Clave y Resultados

• Generación de Secuencias de Códigos: Los autores demuestran que los códigos BB conocidos de alto rendimiento, como el código gross [[144, 12, 12]], pueden verse como doble recubrimientos de códigos más pequeños (por ejemplo, [[72, 12, 6]]). Generan secuencias infinitas de nuevos códigos BB con conteos de cúbits lógicos ($k$) fijos y tamaños de bloque ($n$) crecientes.
• Nuevas Familias de Códigos:
  • Códigos de Peso 6: El método reproduce familias conocidas, incluyendo códigos de producto balanceados y códigos toroidales generalizados, y genera nuevas secuencias para $k=6, 8, 10, 12$.
  • Códigos de Peso 8: Los autores aplican el método para buscar códigos BB con comprobaciones de peso 8 (4 términos en los polinomios definitorios). Encuentran secuencias con $k=8, 10, 12, 14$ que exhiben relaciones $kd^2/n$ significativamente mayores que sus contrapartes de peso 6. Ejemplos notables incluyen los códigos [[64, 14, 8] y [[144, 14, 14]].
  • Códigos de Qudits: La metodología se generaliza a códigos de qudits sobre $\mathbb{F}_q$, generando con éxito códigos de recubrimiento para códigos BB de qudits base.
• Límites Teóricos:
  • Cúbits Lógicos ($k$): Los autores demuestran que para un código de $h$-recubrimiento con $h$ impar, el número de cúbits lógicos satisface $k_h \ge k$. Conjeturan que esto se cumple para todo $h$.
    im
  • Distancia ($d$): Para $h$ impar, demuestran el límite superior $d_h \le hd$. Si $k_h = k$ y $h$ es impar, demuestran el límite inferior $d_h \ge d$. Conjeturan que el límite general $d \le d_h \le hd$ se cumple para todo $h$.
  • Elevaciones de Preservación de Peso: Muestran que si existe una elevación de preservación de peso, esto implica $d_h \le d$, proporcionando una herramienta numérica para descartar códigos de recubrimiento donde la distancia no aumenta.
• Análisis de Operadores Lógicos y Autotopismos: El artículo proporciona construcciones explícitas para elevar operadores lógicos y autótopismos. Demuestra que cuando $h$ es impar y $k_h = k$, el mapa de elevación es un isomorfismo en la homología, asegurando que una base lógica del código base se eleva a una base lógica completa del código de recubrimiento, preservando la acción lógica de los autótopismos (por ejemplo, puertas CNOT y Hadamard lógicas).

Significancia
Los autores afirman que el trabajo es significativo en tres áreas principales:

1. Descubrimiento Eficiente de Códigos: Al identificar un espacio de búsqueda reducido basado en la teoría de grafos de recubrimiento, los autores proporcionan un método sistemático y eficiente para descubrir nuevos códigos BB con parámetros prometedores, evitando búsquedas de fuerza bruta sobre el espacio completo de polinomios.
2. Unificación Teórica: El trabajo unifica varias construcciones de códigos BB conocidas (incluyendo el código gross, códigos de producto balanceados y códigos toroidales generalizados) bajo un único marco de grafos de recubrimiento, revelando relaciones estructurales entre ellos.
3. Gestión de Operadores Lógicos: El desarrollo de mapas de proyección y elevación ofrece una herramienta práctica para analizar códigos grandes. Al derivar operadores lógicos y autótopismos de códigos base más pequeños y bien comprendidos, se reduce la complejidad de gestionar las operaciones lógicas en grandes códigos qLDPC.

Los autores señalan que, aunque el enfoque está en los códigos BB, se espera que los métodos se generalicen a otros códigos de álgebra de grupos y construcciones que involucren hipergrafos o productos elevados. También destacan que, si bien el espacio de búsqueda se reduce, calcular la distancia exacta de los grandes códigos de recubrimiento sigue siendo un cuello de botella, y sus límites teóricos sirven como una guía más que como una solución completa para el cálculo de la distancia.