Quantum group codes for non-Clifford logic: enhanced decoding, addressability and parallelizability

Resumen Técnico: Códigos de Grupos Cuánticos para Lógica No Cliffordiana

Planteamiento del Problema
Los esquemas actuales de computación cuántica tolerante a fallos sufren sobrecargas significativas de espacio y tiempo, lo que dificulta la realización de computadoras cuánticas prácticas. Si bien los códigos de Calderbank-Shor-Steane (CSS) que admiten puertas transversales ofrecen un camino hacia la tolerancia a fallos, las construcciones existentes enfrentan dos limitaciones primarias:

1. Complejidad de Decodificación: Los códigos de Geometría Algebraica (AG) cuánticos de vanguardia que admiten puertas transversales no cliffordianas (esenciales para la Destilación de Estados Mágicos, o MSD) dependen de algoritmos de decodificación con complejidad de tiempo cúbica ($O(n^3)$). Esta alta complejidad se propaga al protocolo MSD, limitando su eficiencia.
2. Direccionabilidad y Paralelización: Los códigos existentes con puertas no cliffordianas transversales típicamente implementan operaciones globales que actúan sobre todos los qudits físicos simultáneamente. Esta falta de "direccionabilidad" —la capacidad de apuntar a subconjuntos específicos de qudits lógicos— limita la flexibilidad algorítmica. Además, aunque trabajos recientes han demostrado la existencia de códigos con puertas direccionables, las construcciones suelen depender de familias muy específicas de códigos AG transitivos, y la paralelización de estas puertas requiere una optimización adicional para reducir la profundidad del circuito.

Metodología
Los autores proponen un marco basado en códigos de grupos cuánticos, derivados de códigos de cuasi grupos clásicos con propiedades de multiplicación específicas. La metodología procede en tres etapas principales:

1. Definición del Marco (Códigos de Grupos Cuánticos):
   Los autores definen una clase de códigos CSS cuánticos donde los códigos clásicos subyacentes ($C_0$ y $C_1$) son códigos quasi-$G$ (isomorfos a ideales derechos de un álgebra de grupo $F_q[G]$). Al asegurar la existencia de una sección de homomorfismo de módulo-$G$ para el mapa cociente, establecen las condiciones bajo las cuales estos códigos cuánticos admiten puertas multi-control-Z ($C_{m-1}Z$) transversales, paralelizables y direccionables.

   • Mecanismo Clave: La acción de grupo permite la construcción de funciones de modulación que posibilitan la implementación de puertas lógicas en órbitas específicas de qudits lógicos utilizando circuitos físicos de profundidad uno.

2. Construcción de Códigos mediante Levantamiento:
   Para generar códigos con buenos parámetros y una decodificación eficiente, los autores emplean un procedimiento de levantamiento basado en la teoría de campos de clase (específicamente de [CG26]).

   • Comienzan con un buen código AG clásico $C$ sobre $F_q$ que satisface la propiedad de $m$-multiplicación.
   • Construyen una extensión abeliana no ramificada del campo de funciones subyacente, creando un nuevo código $\tilde{C}$ sobre $F_{q^2}$.
   • Este proceso de levantamiento dota al nuevo código de un gran grupo de automorfismo de permutación abeliano $G$, convirtiéndolo en un módulo libre de $F_{q^2}[G]$. Crucialmente, el levantamiento preserva la propiedad de $m$-multiplicación requerida para las puertas transversales.

3. Optimización de la Decodificación:
   Los autores aprovechan la estructura de módulo de los códigos levantados. A diferencia de los códigos AG estándar que requieren una decodificación de tiempo cúbico, la estructura de módulo libre permite la adaptación de algoritmos de decodificación para utilizar la multiplicación rápida de matrices sobre el álgebra de grupo. Esto resulta en un decodificador de tiempo cuasi-cuadrático ($O(n^2 \cdot \text{polylog}(n))$) con un radio de decodificación lineal.

Contribuciones Clave y Resultados

• Teorema 1.1 (Familias de Códigos): El artículo construye dos familias de códigos de grupos cuánticos de qudits de $q$-dimensiones (donde $q=t^4$):

  1. Familia Totalmente Direccionable: Códigos con parámetros $[[n, \Theta(n/\log n), \Theta(n)]]_q$. Estos admiten puertas $C_{\tilde{m}-1}Z$ transversales totalmente direccionables. La profundidad de los circuitos lógicos que involucran $m$ bloques de código está acotada superiormente por $O(k^{\tilde{m}-1})$.
  2. Familia de Alta Tasa: Códigos con parámetros $[[n, \Theta(n), \Theta(n)]]_q$. Estos admiten una puerta $C_{\tilde{m}}Z$ transversal global y puertas $C_{\tilde{m}-1}Z$ direccionables por órbita a través de $\Theta(\log n)$ órbitas.
  • En ambos casos, los códigos soportan un decodificador de tiempo $O(n^2 \cdot \text{polylog}(n))$ con un radio de decodificación lineal, una mejora significativa respecto a la complejidad de tiempo $O(n^3)$ de las construcciones previas basadas en AG.

• Corolario 1.2 (Destilación de Estados Mágicos): Al aplicar la familia de alta tasa a los protocolos de Destilación de Estados Mágicos (MSD), los autores demuestran la existencia de un protocolo de destilación de sobrecarga constante para estados mágicos CCZ de qubits con una complejidad de tiempo de $O(n^2 \cdot \text{polylog}(n))$. Esto representa una reducción casi lineal en la complejidad de tiempo comparado con los protocolos de vanguardia de $O(n^3)$.

• Paralelización: El trabajo establece que los circuitos lógicos multi-control-Z pueden paralelizarse en un alto grado. Para circuitos densos, la profundidad mínima está acotada por $O(k^{m-1})$, lo cual es óptimo para tales circuitos.

Significancia
El artículo afirma que su trabajo aborda cuellos de botella críticos en la computación cuántica tolerante a fallos:

1. Eficiencia: Al reducir la complejidad de decodificación de cúbica a cuasi-cuadrática, la sobrecarga de tiempo para los protocolos MSD disminuye sustancialmente, acercando la computación tolerante a fallos práctica a la viabilidad.
2. Flexibilidad: La introducción de puertas no cliffordianas direccionables y paralelizables va más allá de las operaciones globales, permitiendo un control más preciso sobre los qudits lógicos. Esto es esencial para la compilación de circuitos y algoritmos que no requieren entrelazamiento global.
3. Generalización: La construcción va más allá de los códigos AG transitivos específicos utilizados en trabajos previos, utilizando una clase más amplia de códigos AG levantados con grandes grupos de automorfismo abeliano. Esto proporciona un conjunto de herramientas más versátil para diseñar códigos cuánticos con puertas no cliffordianas transversales.

Los autores enfatizan que sus resultados se derivan de construcciones teóricas y técnicas de levantamiento existentes, verificando que estas transformaciones preservan las propiedades necesarias para las puertas no cliffordianas transversales mientras mejoran la eficiencia de la decodificación.