General circuit mapping algorithm for neutral atom quantum computers

Resumen Técnico: Algoritmo General de Mapeo de Circuitos para Computadoras Cuánticas de Átomos Neutros

Planteamiento del Problema
Las computadoras cuánticas de átomos neutros (NAQC) ofrecen una plataforma escalable caracterizada por largos tiempos de coherencia, arreglos de qubits flexibles y capacidades nativas de puertas multi-qubit (p. ej., CCZ, Ck-phase). Sin embargo, la ejecución de circuitos cuánticos en el hardware NAQC requiere mover físicamente los átomos mediante pinzas ópticas para acercar los qubits y permitir puertas de entrelazamiento (bloqueo de Rydberg). Este proceso de "remapeo" introduce una sobrecarga significativa:

1. Pérdida de Fidelidad: Cada transferencia conlleva el riesgo de pérdida de átomos o cambio de estado. Aunque las tasas de éxito de transferencia única son altas (>0.99), los errores acumulativos pueden volverse prohibitivos para circuitos con muchos qubits o transferencias.
2. Sobre carga de Tiempo: Las transferencias consumen tiempo, reduciendo la ventana general de computación.
3. Desafío de Optimización: Los compiladores existentes (p. ej., ZAC, MQT) suelen depender de heurísticas como el recocido simulado o algoritmos voraces (greedy). Aunque mejoran respecto a métodos anteriores, carecen de límites inferiores teóricos explícitos para el número de transferencias requeridas y no proporcionan una formulación general que optimice simultáneamente la distancia total recorrida y las operaciones de transferencia paralela (PTO) tanto en arquitecturas monolíticas (M-arch) como zonificadas (Z-arch).

Metodología
Los autores proponen un marco matemático unificado e independiente del circuito basado en la optimización combinatoria de la teoría de grafos. La metodología procede en cuatro etapas distintas:

1. Representación de Grafos (Fundamento Teórico):

   • El circuito cuántico se descompone en un grafo acíclico dirigido (DAG) donde los vértices representan "instrucciones" (grupos de puertas que actúan sobre qubits específicos dentro de una etapa) y las aristas representan transiciones entre etapas.
   • El problema de minimizar las transferencias entre etapas se modela como la búsqueda de un emparejamiento máximo ponderado en subgrafos bipartitos que conectan etapas consecutivas.
   • Teoremas 3.1 y 3.2: Los autores demuestran que el número mínimo de transferencias para ambas arquitecturas, M-arch y Z-arch, puede derivarse sumando los mínimos locales de estos emparejamientos. Para Z-arch, el grafo se descompone en subgrafos específicos de cada zona, ocurriendo transferencias obligatorias entre zonas.

2. Codificación de Bastones (Reducción del Problema):

   • Para optimizar la colocación física de los átomos, los autores introducen una "codificación de bastones" (stick encoding). Esta representación abstrae el problema de mapeo agrupando los qubits que permanecen estáticos entre etapas en "bastones" (sticks).
   • Dentro de un bastón, los qubits forman "sub-bastones" (substicks). La codificación captura los grados de libertad (DoF) intrínsecos: la coordenada espacial 2D del bastón en la rejilla atómica y una variable booleana que indica si los sub-bastones dentro de un bastón multi-qubit han sido permutados.
   • Esta codificación desacopla la decisión de qué qubits mover (determinada por el emparejamiento de grafos) de la colocación de dichos qubits, permitiendo una optimización eficiente de la distancia recorrida.

3. Algoritmo Genético (Optimización):

   • Se emplea un Algoritmo Genético (GA) para resolver el programa entero no lineal resultante.
   • El GA opera sin cruce (crossover), basándose en su lugar en modificaciones locales aleatorias (mover bastones o permutar sub-bastones) para explorar el espacio de configuración.
   • La función objetivo es flexible, permitiendo al usuario priorizar la minimización de la distancia total recorrida, la maximización del número de transferencias paralelas o una combinación ponderada de ambas.

4. Construcción de Operaciones de Transferencia Paralela (PTO):

   • Un paso de post-procesamiento construye la secuencia de transferencias paralelas.
   • El algoritmo analiza el dígrafo de transferencia para detectar ciclos. Si existe un ciclo (átomos bloqueando el camino de otros), se utiliza un "espacio de estacionamiento" (un espacio atómico vacío) para romper el ciclo, lo que requiere una transferencia adicional.
     im un algoritmo voraz (greedy) luego programa las transferencias, asegurando la compatibilidad con las restricciones del hardware (p. ej., limitaciones del Deflector Optoacústico) para maximizar el paralelismo evitando colisiones.

Contribuciones Clave

• Marco Matemático General: El artículo proporciona la primera formulación de teoría de grafos que determina el límite inferior teórico para el número de transferencias de átomos requeridas para cualquier circuito cuántico en plataformas NAQC, aplicable tanto a arquitecturas monolíticas como zonificadas.
• Codificación Novedosa: La introducción de la "codificación de bastones" reduce eficazmente la complejidad del problema de mapeo al aislar los grados de libertad relacionados con la colocación espacial y el orden interno de los qubits.
• Control de Compensación (Trade-off): El marco permite explícitamente un equilibrio entre minimizar la distancia total recorrida por los átomos (reduciendo el tiempo) y maximizar las operaciones de transferencia paralela (reduciendo la latencia).
• Garantías Teóricas: A diferencia de enfoques heurísticos previos, este trabajo proporciona límites inferiores demostrables para el conteo de transferencias (Teoremas 3.1/3.2) y demuestra que el método propuesto alcanza consistentemente dichos límites.

Resultados
Los autores evaluaron su algoritmo frente a mapeadores de vanguardia, específicamente ZAC (un mapeador de arquitectura zonificada consciente del reuso) y MQT (Munich Quantum Toolkit).

• Conteo de Transferencias: El método propuesto alcanza consistentemente el número mínimo teórico de transferencias (dentro de un margen de 0 a 2 transferencias debido a los requisitos de ruptura de ciclos) en todos los circuitos probados. En contraste, ZAC a menudo excede este mínimo teórico.
• Distancia y Paralelismo:
  • Al optimizar la distancia, el método propuesto reduce significamente la distancia total recorrida en comparación con ZAC (p. ej., una mejora de ~333% para el circuito QFT).
  • Al optimizar las transferencias paralelas, el método suele superar tanto a ZAC como a MQT en el número de PTOs, particularmente para circuitos complejos.
• Flexibilidad: Los resultados resaltan una compensación: optimizar la distancia no siempre minimiza las PTOs, y viceversa. El GA permite a los practicantes ajustar la función objetivo según los parámetros específicos del hardware (p. ej., la velocidad relativa del movimiento de las pinzas frente al cambio de trampa).

Significancia y Reivindicaciones
El artículo afirma proporcionar tanto un punto de referencia teórico como una herramienta práctica para la compilación eficiente de circuitos cuánticos consciente de la arquitectura.

• Teórica: Establece que el número mínimo de transferencias puede determinarse mediante el emparejamiento de grafos, ofreciendo un estándar para el desarrollo de futuros compiladores.
• Práctica: Ofrece una herramienta de optimización flexible que permite a los profesionales generar mapeos conscientes del hardware. Al reducir los errores inducidos por el movimiento y aprovechar mejor el paralelismo de la transferencia de átomos, el método mejora directamente la eficiencia de ejecución en dispositivos NAQC.
• Escalabilidad: Se describe el enfoque como general y escalable, capaz de manejar diversos conjuntos de puertas (incluyendo puertas multi-qubit) y adaptable a futuras arquitecturas NAQC con zonas adicionales (p. ej., para puertas CCZ).

Los autores mantienen un tono modesto respecto al tiempo de ejecución, señalando que la elección óptima entre minimizar la distancia o las PTOs depende de parámetros específicos del hardware (p. ej., velocidades de conmutación de SLM/AOD frente a velocidades de movimiento de las pinzas) que varían entre plataformas. Recomiendan ejecutar el mapeador con diferentes parámetros para seleccionar la mejor solución para un dispositivo dado.