⚛️ quantum physics

Heuristic and Optimal Synthesis of CNOT and Clifford Circuits

Este artículo introduce tres familias de algoritmos para la síntesis heurística y óptima de circuitos CNOT y Clifford que minimizan tanto el recuento de puertas como la profundidad del circuito, demostrando un rendimiento superior sobre los métodos existentes y proporcionando una implementación de código abierto.

Autores originales: Mark Webster, Stergios Koutsioumpas, Dan E Browne

Publicado 2026-08-17

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Mark Webster, Stergios Koutsioumpas, Dan E Browne

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando construir una máquina compleja con piezas de Lego, pero con un giro: las piezas son invisibles y las instrucciones están escritas en un lenguaje de matemáticas puras. Este es el mundo de la computación cuántica. En este reino, los científicos no solo construyen estructuras estáticas; construyen "circuitos" que manipulan el tejido mismo de la realidad para resolver problemas demasiado difíciles para las computadoras regulares. Para hacer que estos circuitos funcionen, necesitan realizar movimientos específicos, como accionar un interruptor o intercambiar dos piezas. Los movimientos más comunes se llaman puertas "CNOT" (piensa en ellas como un interruptor maestro que activa una pieza solo si otra pieza está en un determinado estado) y puertas "Clifford" (un conjunto de movimientos ligeramente más complejos que incluyen el interruptor maestro más algunas rotaciones especiales).

¿Por qué es esto importante? Porque estos circuitos son la columna vertebral de la "corrección de errores cuánticos". Al igual que una señal de radio con ruido necesita un decodificador para dar sentido a la estática, las computadoras cuánticas son increíblemente frágiles y propensas a cometer errores. Para corregir estos errores y ejecutar algoritmos útiles, necesitamos construir estos circuitos de la manera más eficiente posible. El problema es que hay millones de formas de organizar el mismo conjunto de movimientos. Algunas disposiciones son como una bola de estambre enredada: largas, lentas y propensas a romperse. Otras son como una línea recta y elegante: cortas, rápidas y fiables. El objetivo es encontrar el camino más corto y eficiente para lograr el trabajo, porque en el mundo cuántico, cada paso adicional aumenta la posibilidad de que un error arruine todo el cálculo.

Aquí entra un equipo de investigadores del University College London, que decidió abordar este enredo de piezas de Lego con un nuevo conjunto de herramientas. No solo querían encontrar una forma de construir estos circuitos; querían encontrar la mejor forma, o al menos una forma que fuera significamente mejor que lo que todos los demás estaban usando. Desarrollaron tres estrategias diferentes, cada una diseñada para un tamaño distinto de rompecabezas.

Primero, para los rompecabezas más pequeños (que involucran hasta 7 qubits, o bits cuánticos), crearon un método "Óptimo". Imagina esto como un cartógrafo súper lento y súper detallado que revisa cada uno de los caminos posibles a través de un laberinto para garantizar que ha encontrado la ruta absolutamente más corta. Construyeron una base de datos masiva de todos los posibles "atajos" agrupando caminos que parecen diferentes pero que son en realidad los mismos cuando rotas o volteas el tablero. Esto les permitió buscar instantáneamente la mejor solución para problemas pequeños, superando a los métodos anteriores en velocidad y eficiencia.

Para rompecabezas de tamaño mediano, utilizaron una estrategia "A*". Piensa en esto como un excursionista inteligente con una brújula. El excursionista no revisa cada camino, sino que utiliza una suposición inteligente (una "heurística") para estimar qué dirección parece más prometedora. Mantienen una lista de posibles caminos, eligiendo siempre aquel que parece estar más cerca de la meta. Los investigadores descubrieron que, al usar un tipo específico de matemática para hacer estas suposiciones, su excursionista podía encontrar rutas que eran casi tan cortas como las rutas del cartógrafo perfecto, pero mucho más rápidas de encontrar.

Finalmente, para los rompecabezas gigantes y masivos (docenas de qubits), utilizaron un enfoque "Codicioso" (Greedy). Esto es como un excursionista que solo mira el paso inmediatamente delante de él y siempre toma el que parece reducir la distancia más en ese momento. Usualmente, este tipo de pensamiento "miope" te deja atrapado en un callejón sin salida (un mínimo local), pero el equipo inventó una nueva forma de mirar el mapa. En lugar de solo contar pasos, miraron la "forma" del problema usando un vector (una lista de números) que les ayudó a evitar callejones sin salida. Este método produjo consistentemente circuitos más cortos que las mejores herramientas existentes, como las de Qiskit o Rustiq, especialmente para sistemas grandes.

Los resultados son impresionosos. Cuando probaron sus métodos en circuitos aleatorios y códigos de corrección de errores específicos (como el famoso código Golay), sus algoritmos utilizaron consistentemente menos puertas de dos qubits "entrelazantes" —las partes más costosas y propensas a errores del circuito— que cualquier otro método disponible actualmente. Para el código Golay, incluso encontraron un circuito con 56 puertas, superando el mejor anterior de 57. No solo encontraron una forma ligeramente mejor; encontraron una forma que escala mucho mejor a medida que los problemas se vuelven más grandes.

Sin embargo, los autores son cuidadosos al señalar dónde termina su magia. El cartógrafo "perfecto" (Óptimo) solo funciona para circuitos muy pequeños porque el número de caminos crece tan rápido que se vuelve imposible revisarlos todos para tamaños mayores. El "excursionista inteligente" (A*) es excelente para tamaños medianos, pero aún puede volverse lento si el laberinto es demasiado complejo. Y el "excursionista miope" (Codicioso), aunque es excelente para circuitos grandes, no garantiza el camino absolutamente más corto, solo uno muy bueno. También señalan que su trabajo se centra en el número teórico de puertas; hacer que estos circuitos funcionen en hardware físico real con limitaciones de conexión específicas es el siguiente paso.

En resumen, este artículo proporciona un nuevo kit de herramientas para los ingenieros cuánticos. Ofrece una forma de encoger el estambre enredado de los circuitos cuánticos en líneas elegantes y eficientes, haciendo que el sueño de las computadoras cuánticas libres de errores esté un poco más cerca de la realidad. Al combinar una base de datos de atajos perfectos para trabajos pequeños, un juego de suposiciones inteligentes para trabajos medianos y una estrategia de "mirada hacia adelante" para trabajos grandes, han demostrado que podemos construir estos circuitos con menos movimientos y menos desperdicio que nunca antes.

Resumen Técnico: Síntesis Heurística y Óptima de Circuitos CNOT y Clifford

Planteamiento del Problema

La implementación eficiente de circuitos Clifford es fundamental para la corrección de errores cuánticos y los algoritmos cuánticos. La eficiencia de estos circuitos se mide típicamente por el recuento de puertas de dos cúbits entrelazantes (específicamente CNOT para circuitos reversibles lineales) o la profundidad del circuito. Optimizar estas métricas es un desafío porque un único operador Clifford puede implementarse mediante numerosas configuraciones de circuitos con recuentos de puertas y profundidades muy diferentes. Los métodos existentes, como la eliminación gaussiana o enfoques heurísticos como los de rustiq, tket y qiskit, a menudo no logran encontrar las implementaciones más compactas, particularmente para recuentos de cúbits mayores o circuitos de codificación específicos. La literatura clásica sobre circuitos reversibles lineales (solo CNOT) ha establecido diversas técnicas de síntesis, pero persiste la necesidad de métodos unificados y eficientes que minimicen los recuentos de puertas de dos cúbits tanto para circuitos de solo CNOT como para circuitos Clifford generales.

Metodología

Los autores proponen un marco unificado para la síntesis de circuitos CNOT y Clifford generales utilizando tres familias algorítmicas distintas: síntesis Óptima, A* y Greedy (voraz). El núcleo de su enfoque consiste en mapear los operadores de los circuitos a matrices binarias y explotar las clases de equivalencia para reducir los espacios de búsqueda.

1. Representaciones Matemáticas

Circuitos CNOT: Mapeados a matrices binarias invertibles en $GL(n, 2)$. Una puerta CNOT corresponde a sumar una columna a otra.
Circuitos Clifford Generales: Mapeados a matrices binarias simplécticas en $Sp(2n, 2)$. Los autores utilizan una estructura de circuito de tres capas: permutaciones de cúbits, Cliffords de un solo cúbit y transvecciones simplécticas de dos cúbits (que son equivalentes a CNOTs hasta con Cliffords de un solo cúbit).
Clases de Equivalencia: Los autores reducen significativamente la complejidad computacional considerando clases de equivalencia de matrices bajo:
- Permutaciones de filas y columnas (permutaciones de cúbits).
- Transposición e inversión de matrices.
- Para circuitos Clifford, multiplicación por la izquierda y por la derecha por operadores Clifford de un solo cúbit.
- Esto permite la selección del miembro del circuito con el menor recuento de puertas o profundidad de una clase de equivalencia.

2. Familias de Algoritmos

A. Síntesis Óptima

Enfoque: Genera una base de datos de todas las clases de equivalencia de matrices hasta un determinado número de cúbits ( $n \le 7$ para CNOT, $n \le 5$ para Clifford).
Mecanismo: Las matrices se generan aplicando todas las puertas posibles secuencialmente. La equivalencia se determina mapeando las matrices a grafos bicolor (para CNOT) o grafos generalizados (para Clifford) y comprobando el isomorfismo utilizando paquetes como nauty o Bliss.
Uso: Para una matriz objetivo, el algoritmo busca su clase de equivalencia en la base de datos precalculada y recupera la secuencia de puertas óptima, aplicando las permutaciones necesarias para coincidir con el objetivo.

B. Síntesis A*

Enfoque: Un algoritmo de búsqueda de mejor primera opción (best-first search) diseñado para circuitos de tamaño intermedio donde las bases de datos óptimas son demasiado grandes.
M mecanismo: Utiliza una cola de prioridad para explorar secuencias de puertas. Emplea una función heurística $h(P)$ para estimar el costo restante para alcanzar una matriz de permutación (para CNOT) o una permutación más Cliffords de un solo cúbit (para Clifford).
Heurísticas: Los autores derivan estimadores robustos basados en las sumas de filas y columnas de la matriz (específicamente las métricas $H_{sum}$ y $H_{prod}$ ). Encontraron que escalar estas heurísticas ( $r \cdot h$ ) mejora el rendimiento. El algoritmo no se compromete con una puerta inmediatamente, sino que expande el nodo con el valor de $g(P) + h(P)$ más bajo.
Optimización: Para gestionar la complejidad exponencial en el peor de los casos, el tamaño de la cola de prioridad se limita (por ejemplo, a 100 entradas), eliminando las entradas máximas si se excede el límite.

C. Síntesis Greedy (Voraz)

Enfoque: Un algoritmo rápido y determinista para circuitos grandes.
Mecanismo: En cada paso, evalúa todas las puertas posibles y selecciona la que minimiza una heurística específica.
Innovación: A diferencia de las heurísticas escalares anteriores (que suman entradas o log-sumas y a menudo quedan atrapadas en mínimos locales), los autores introducen una heurística basada en vectores. Este vector se forma ordenando las sumas de las columnas de la matriz, su inversa, su transpuesta y su inversa-transpuesta.
Optimización de Profundidad: El algoritmo greedy puede modificarse para minimizar la profundidad del circuito tratando la profundidad como un costo primario y la heurística como una penalización secundaria.

Contribuciones Clave y Resultados

1. Mejoras Algorítmicas

Heurística de Vector: La heurística basada en vectores propuesta para la síntesis greedy supera significativamente a las heurísticas escalares (como $H_{sum}$ y $H_{prod}$ ) en evitar mínimos locales. Para circuitos con $n \ge 32$ cúbits, la heurística de vector fue dominante, mientras que las heurísticas escalares fallaron (ejecuciones abandonadas) con una tasa de abandono del 100% para circuitos con $n > 32$ cúbits.
Reducción de Clases de Equivalencia: Al mapear a problemas de isomorfismo de grafos y considerar permutaciones, transposiciones e inversas, los autores generaron bases de datos exponencialmente más pequeñas que los métodos anteriores (por ejemplo, reduciendo el espacio de búsqueda para $Sp(2n, 2)$ significativamente en comparación con Bravyi et al. [4]).

2. Resultados de Benchmarking

Los autores evaluaron sus métodos frente a rustiq, tket, qiskit, PyZX y Volanto utilizando matrices aleatorias y conjuntos de datos específicos.

Circuitos CNOT:
- Óptimo/A:* Para $n \le 7$ , el algoritmo A* iguala los recuentos de puertas óptimos. Para circuitos de hasta $n = 32$ cúbits, el algoritmo A* proporciona los recuentos de puertas más bajos. Para circuitos con $n \ge 32$ cúbits, el algoritmo greedy con la heurística de vector produce los recuentos de CNOT más bajos, superando a la eliminación gaussiana con una reducción promedio del 50% en el recuento de puertas.
Circuitos Clifford Generales:
- Matrices Aleatorias: El algoritmo A* iguala los recuentos óptimos para $n \le 5$ y proporciona los recuentos más bajos para circuitos de hasta $n = 16$ . Para circuitos con $n > 16$ , el algoritmo greedy supera significativamente a todos los demás métodos probados (incluyendo pytket y rustiq).
- Conjunto de Datos Hamiltoniano: En un conjunto de datos de circuitos de evolución hamiltoniana (4 a 64 cúbits), el algoritmo greedy superó al algoritmo BSHM (seguido de la optimización de pytket) tanto en recuento de puertas como en tiempo de ejecución.
- Circuitos de Codificación: Para el código Golay $[[23, 1, 7]]$ , los autores encontraron un circuito de codificación con 56 puertas de dos cúbits entrelazantes usando A*, mejorando el mejor resultado anterior de 57 (método de Steane) y 61 (Aprendizaje por Refuerzo).
Comparación con Solucionadores SAT: Comparado con qsynth (un solucionador basado en SAT), los algoritmos óptimo y A* de los autores igualaron o mejoraron los recuentos de puertas para circuitos de hasta 5 cúbits, con tiempos de procesamiento órdenes de magnitud más rápidos. Para $n \ge 6$ , qsynth agotó el tiempo de espera en casi todas las instancias, mientras que los métodos de los autores completaron con éxito.

3. Implementación

Los algoritmos están implementados en un paquete de Python disponible en GitHub, lo que permite a la comunidad reproducir los resultados y aplicar los métodos a sus propios circuitos.

Significado y Reivindicaciones

El artículo afirma que su principal significancia radica en proporcionar un conjunto de herramientas de síntesis que alcanzan consistentemente recuentos de puertas de dos cúbits más bajos que los métodos de vanguardia actuales en una amplia gama de tamaños de circuito.

Escalabilidad: El trabajo cierra la brecha entre la síntesis óptima a pequeña escala y la síntesis heurística a gran escala, ofreciendo una solución práctica para circuitos de hasta 64 cúbits donde los métodos óptimos anteriores fallan debido al tamaño de la base de datos y los solucionadores SAT fallan debido a las restricciones de tiempo.
Robustez: La heurística basada en vectores se destaca como un avance clave que evita la trampa de los "mínimos locales" común en los enfoques greedy basados en escalares.
Impacto Práctico: La capacidad de encontrar circuitos más compactos para códigos de corrección de errores (como el de Golay) impacta directamente en la viabilidad de la computación cuántica tolerante a fallos al reducir la sobrecarga de recursos requerida para las operaciones lógicas.
Modestia: Los autores reconocen que su síntesis óptima está actualmente limitada a $n \le 7$ (CNOT) y $n \le 5$ (Clifford) debido al tamaño de la base de datos, aunque sugieren que esto podría extenderse con mejores técnicas de codificación. También señalan que, si bien su algoritmo greedy es rápido, no garantiza la optimalidad global para circuitos grandes, aunque empíricamente supera a sus competidores.

El trabajo concluye señalando que los algoritmos son actualmente independientes del dispositivo y podrían optimizarse aún más mediante la portabilidad a C/Rust o adaptándolos a restricciones específicas de conectividad de hardware en iteraciones futuras.