SDP bounds on quantum codes: rational certificates

1. Planteamiento del Problema

El problema central en la teoría de códigos cuánticos es determinar el tamaño máximo ($K$) de un código cuántico para una longitud de bloque ($n$) y una distancia ($\delta$) dadas. Específicamente, se busca saber si existe un código $((n, K, \delta))_2$ (para qubits).

Históricamente, los límites superiores se han obtenido mediante:

• Métodos analíticos: Como las desigualdades de Singleton o de Hamming.
• Programación Lineal (LP): Basada en los enumeradores de peso cuánticos y la identidad de MacWilliams.
• Programación Semidefinida (SDP): Una técnica más reciente que refuerza los límites de la LP, introducida previamente por los mismos autores.

La limitación crítica: Tanto la LP como la SDP se ejecutan típicamente con aritmética de punto flotante. Esto genera certificados de infactibilidad aproximados. Debido a errores numéricos, estos resultados no constituyen pruebas matemáticas rigurosas; pueden ser correctos pero formalmente no demostrados, o en el peor de los casos, producir límites espurios (falsos positivos/negativos) debido a la inestabilidad numérica.

2. Metodología

El objetivo principal de este trabajo es transformar los resultados numéricos aproximados en pruebas matemáticas rigurosas mediante la generación de certificados de infactibilidad racionales.

La metodología se basa en los siguientes pilares:

• Solver de Rango Bajo Agrupado (Clustered Low-Rank Solver): Se utiliza un solver numérico de alta precisión (disponible en Julia) desarrollado por Leijenhorst et al. Este solver explota la estructura de bajo rango y el agrupamiento de restricciones en los problemas de SDP.
• Redondeo Heurístico a Expresiones Algebraicas: Una vez que el solver encuentra una solución numérica aproximada, se aplica un método heurístico para redondear los valores a números racionales o algebraicos exactos. Esto permite reconstruir una solución exacta en el campo de los números algebraicos.
• Verificación Exacta: Para validar que la solución redondeada es realmente factible (o infactible), se utiliza la descomposición LDLT (una variante de la descomposición de Cholesky) sobre extensiones de campos racionales (específicamente $\mathbb{Q}(\sqrt{3})$ en este caso).
  • Se verifica la semidefinición positiva de las matrices mediante la comprobación de que los elementos de la matriz diagonal $D$ son no negativos.
  • Dado que los elementos son de la forma $a + b\sqrt{3}$, se verifica la no negatividad acotando $\sqrt{3}$ con números racionales ($r_\ell < \sqrt{3} < r_u$) para asegurar que la desigualdad se cumple estrictamente sin errores de redondeo.
• Reducción de Simetría: Para manejar la complejidad computacional, se utiliza una versión reducida por simetría del SDP basada en el álgebra de Terwilliger no binaria. Esto reduce el número de variables de $O(n^4)$ a un tamaño manejable, permitiendo resolver problemas para $n \le 19$.

3. Contribuciones Clave

1. Certificados Racionales Rigurosos: Por primera vez, se proporcionan pruebas formales (certificados) de la inexistencia de ciertos códigos cuánticos, eliminando la ambigüedad de los errores de punto flotante.
2. Mejora de Límites Superiores: Se han mejorado 18 límites superiores conocidos para el tamaño máximo de códigos de $n$ qubits, donde $6 \le n \le 19$.
3. Validación de Resultados Previos: Se han convertido en pruebas exactas los resultados numéricos previos sobre la inexistencia de códigos como $((8, 9, 3))_2$ y $((10, 5, 4))_2$.
4. Escalabilidad: Se demuestra que los métodos de SDP, combinados con técnicas de certificación racional, son prácticos y escalables para parámetros de códigos cuánticos relevantes para la computación cuántica actual.

4. Resultados Principales

Los autores presentan una tabla actualizada de límites superiores e inferiores para códigos cuánticos no aditivos. Destacan los siguientes hallazgos:

• Inexistencia de Códigos Específicos: Se ha probado rigurosamente que no existen códigos como $((7, 1, 4))_2$, $((8, 9, 3))_2$ y $((10, 5, 4))_2$.
• Mejoras en Códigos No Aditivos: Se han reducido los límites superiores para varios casos. Por ejemplo, para $n=14, \delta=3$, el límite superior se reduce de 324 a 295 (marcado en negrita en la Tabla 1 del artículo).
• Códigos Puros vs. Impuros: Se han establecido límites más estrictos para códigos puros. Por ejemplo, se demuestra que el código $((6, 2, 3))_2$ debe ser impuro, extendiendo un resultado conocido para códigos aditivos.
• Códigos Aditivos: Se confirma la inexistencia de ciertos códigos aditivos y no aditivos correspondientes, como $((13, 1, 6))_2$ y $((19, 1, 8))_2$.
• Problema Abierto: Se plantea un problema abierto sobre la existencia de un código estabilizador hipotético $[[24, 0, 10]]_2$, donde se conoce un enumerador de peso entero que satisface las restricciones de LP, pero aún no se sabe si existe un enumerador de peso matricial entero compatible.

5. Significado e Impacto

Este trabajo es fundamental para la teoría de códigos cuánticos por varias razones:

• Rigor Matemático: Cierra la brecha entre la computación numérica y la demostración matemática formal en el contexto de límites de códigos. En un campo donde la corrección de errores es vital para la viabilidad de las computadoras cuánticas, saber con certeza absoluta qué parámetros son imposibles es crucial.
• Herramientas para la Investigación: Proporciona una metodología reproducible (código y certificados disponibles en GitHub) que otros investigadores pueden utilizar para verificar o mejorar límites en futuros trabajos.
• Optimización de Recursos: Al establecer límites superiores más estrictos, se evita el desperdicio de recursos intentando construir códigos que matemáticamente no pueden existir, guiando así los esfuerzos de construcción hacia regiones de parámetros prometedoras.
• Avance en SDP Cuántica: Demuestra que las técnicas avanzadas de optimización convexa, cuando se combinan con métodos de certificación algebraica, pueden resolver problemas complejos de la teoría de la información cuántica que antes eran inaccesibles o solo aproximables.

En resumen, el artículo transforma los límites de programación semidefinida de "evidencia numérica fuerte" a "pruebas matemáticas definitivas", estableciendo un nuevo estándar de rigor en la determinación de la viabilidad de códigos cuánticos.