dSABRE: A SABRE-Style Router for Multi-Core Distributed Quantum Computers

El artículo presenta dSABRE, un nuevo enrutador para computadoras cuánticas distribuidas multinúcleo que minimiza el consumo de EPR priorizando la resolución de puertas intra-núcleo y empleando un mecanismo de puntuación de teletransportación consciente de la capacidad, logrando reducciones significativas en el uso de recursos en comparación con los métodos existentes más avanzados.

Lo esencial

Imagina que estás intentando organizar una fiesta de baile masiva y de alto riesgo, pero el lugar está dividido en varias salas separadas (llamadas núcleos). Los bailarines son qubits (bits cuánticos) y la música es un circuito cuántico (un conjunto de instrucciones).

Para que el baile funcione, a veces los pares de bailarines necesitan tomarse de las manos y girar juntos. Si están en la misma sala, pueden simplemente acercarse fácilmente. Pero si están en salas diferentes, no pueden atravesar las paredes. Deben usar un servicio especial, costoso y lento de "teletransportación" para moverse de una sala a otra. Este servicio consume un recurso limitado llamado par EPR (piensa en ello como un precioso "boleto mágico").

El problema es: ¿Cómo mueves a los bailarines para que puedan bailar juntos usando la menor cantidad posible de boletos mágicos?

Este es el problema que DSABRE resuelve. Así es como el artículo lo explica en términos sencillos:

1. El problema con los métodos anteriores

Antes de DSABRE, otros enrutadores (como TELESABRE) eran como policías de tráfico que solo reaccionaban a los problemas.

• Si una sala se llenaba demasiado de bailarines, los enrutadores antiguos esperaban hasta que se produjera un atasco.
• Una vez atascados, intentaban forzar la salida de un bailarín, pero esto a menudo consumía boletos mágicos adicionales o hacía que toda la fiesta se detuviera (un "bloqueo").
• También miraban las instrucciones de baile en un orden desordenado y aleatorio, lo que dificultaba predecir quién necesitaba moverse a continuación.

2. La solución DSABRE: Un gestor más inteligente y proactivo

DSABRE es un nuevo "enrutador" (un gestor de tráfico) que utiliza una estrategia más inteligente. Tiene tres trucos principales para ahorrar boletos mágicos:

A. La "Tarjeta de puntuación de cinco puntos" (Mejor toma de decisiones)

Cuando DSABRE decide si mover a un bailarín a una nueva sala, no solo mira "qué tan cerca" está su pareja. Utiliza una tarjeta de puntuación de cinco términos:

1. Costo de preparación: ¿Cuántos pasos necesita dar el bailarín dentro de su sala actual para llegar a la puerta?
2. Penalización de capacidad: Este es el más importante. Si una sala de destino ya está abarrotada de bailarines, DSABRE le asigna una enorme "mala puntuación". Se niega a enviar bailarines allí, evitando que la sala se convierta en un atasco.
3. Ganancia de salto: Recompensa los movimientos que acercan al bailarín a su sala de destino final, incluso si aún no está allí.
4. Ganancia inmediata: ¿Cuánto más cerca queda el bailarín de su pareja ahora mismo con este movimiento?
5. Perspectiva: Mira unos pasos hacia el futuro para ver si este movimiento ayuda con los bailes venideros.

Analogía: Imagina que estás mudando muebles. Los enrutadores antiguos simplemente empujarían un sofá a la siguiente sala porque estaba "cerca", incluso si esa sala ya estaba llena de cajas. DSABRE verifica primero si la sala está llena y dice: "No, esa sala está demasiado abarrotada; pongamos el sofá en el pasillo en su lugar".

B. La "Evacuación proactiva" (Despejando el atasco antes de que ocurra)

Esta es el arma secreta de DSABRE.

• Antigua forma: Esperar hasta que una sala esté al 100% llena, entrar en pánico e intentar sacar a la gente.
• Forma DSABRE: Mantiene una "lista de demanda". Si ve que la Sala A está a punto de ser inundada de bailarines para un baile próximo, pero la Sala A ya está casi llena, proactivamente mueve a algunos bailarines inactivos (aquellos que no están bailando ahora mismo) fuera de la Sala A antes de que comience la avalancha.
• Resultado: Cuando llega la avalancha, hay espacio. Sin atascos, sin boletos mágicos desperdiciados.

C. El mapa "Capa por capa" (Mejor planificación)

Cuando DSABRE mira hacia adelante para ver qué bailes se avecinan, no escanea la lista aleatoriamente. Construye un mapa capa por capa, respetando el orden del baile.

• Analogía: Imagina leer una receta. Un enrutador antiguo podría leer los ingredientes del postre antes que los de la sopa. DSABRE lee la receta en el orden correcto, asegurándose de saber exactamente qué ingredientes (bailarines) se necesitan a continuación, para no perder tiempo moviendo cosas que aún no se necesitan.

3. Los resultados: Una fiesta mucho más eficiente

Los autores probaron DSABRE en muchas "fiestas" (circuitos cuánticos) diferentes de varios tamaños (25, 36 y 64 bailarines).

• El resultado: DSABRE utilizó 41% a 44% menos boletos mágicos (pares EPR) que el mejor método anterior (TELESABRE).
• Escalabilidad: Cuando lo probaron en una fiesta enorme con hasta 360 bailarines, DSABRE aún funcionó perfectamente, mientras que el método antiguo a menudo se quedaba atascado y se rendía.

Resumen

En resumen, DSABRE es una forma más inteligente de organizar computadoras cuánticas que están hechas de muchos chips pequeños conectados entre sí. En lugar de esperar a que ocurran los atascos, DSABRE:

1. Verifica la capacidad antes de enviar bailarines a salas abarrotadas.
2. Mueve a los bailarines inactivos fuera temprano para hacer espacio.
3. Planifica los movimientos en un orden lógico, paso a paso.

Esto ahorra los costosos "boletos mágicos" (pares EPR) necesarios para conectar los chips, haciendo que la computadora cuántica funcione de manera más eficiente.

Resumen técnico

Resumen Técnico: DSABRE – Un Router Estilo SABRE para Computadoras Cuánticas Distribuidas de Múltiples Núcleos

Enunciado del Problema
El camino hacia la computación cuántica tolerante a fallos requiere escalar más allá de los chips monolíticos individuales hacia Computadoras Cuánticas Distribuidas (DQCs), donde múltiples Unidades de Procesamiento Cuántico pequeñas (QPUs o "núcleos") están interconectadas mediante enlaces fotónicos o de microondas. La ejecución de circuitos en DQCs implica una pipeline de compilación que comprende la asignación de qubits, la selección de primitivas de comunicación y el enrutamiento/programación. El objetivo dominante en este contexto es minimizar el consumo de EPR (pares entrelazados), ya que la generación de EPR es lenta, ruidosa y limitada en tasa en comparación con las operaciones de puertas locales.

Aunque los routers de última generación como TELESABRE utilizan heurísticas estilo SABRE para enrutar circuitos a través de núcleos, manejan la congestión de manera defensiva. TELESABRE desalienta el aterrizaje en núcleos saturados mediante penalizaciones e intenta recuperarse de los bloqueos muertos descartando información de anticipación. Sin embargo, en instancias densas o grandes, este enfoque reactivo a menudo consume un exceso de pares EPR o falla en converger por completo. El desafío central abordado por este artículo es la falta de gestión proactiva de la congestión y la ineficiencia de los mecanismos de anticipación existentes en entornos inter-núcleo.

Metodología: DSABRE
DSABRE es un router estilo SABRE diseñado para procesadores de múltiples núcleos. Opera dentro de una disposición inicial fija (generada por Qiskit SabreLayout) y se centra en la etapa de enrutamiento: ordenando los SWAP intra-núcleo y las teleportaciones inter-núcleo (específicamente teledata, moviendo qubits lógicos entre núcleos). El algoritmo ejecuta un bucle impulsado por anticipación con cuatro fases por iteración:

1. Vaciar: Ejecutar puertas de 1Q y puertas 2Q intra-núcleo adyacentes.
2. Particionar: Separar las puertas restantes de la capa frontal en intra-núcleo ($F_{intra}$) e inter-núcleo ($F_{inter}$).
3. Puntuar y Aplicar:
   • Si $F_{intra}$ no está vacío, seleccionar el mejor SWAP intra-núcleo.
   • Si $F_{intra}$ está vacío, puntuar los candidatos de teleportación inter-núcleo y los candidatos de alivio proactivo de congestión, aplicando el movimiento con la puntuación más baja.
4. Punto de Control/Reversión: Guardar el estado al lograr progreso; si se detiene durante un número fijo de iteraciones, restaurar un punto de control y forzar el progreso para escapar del bloqueo muerto.

Contribuciones y Mecanismos Clave
El artículo identifica tres mecanismos específicos que impulsan la mejora de DSABRE sobre el estado del arte:

1. Puntuación de Teletransportación Centrada en Puertas de Cinco Términos:
   A diferencia de la estimación de energía global de TELESABRE, DSABRE utiliza una puntuación local y centrada en puertas ($s$) para movimientos inter-núcleo. La puntuación combina cinco términos:

   • Costo de Preparación ($d_{prep}$): SWAPs intra-núcleo requeridos para mover un qubit a un puerto de comunicación.
   • Penalización de Capacidad ($c_{cap}$): Un término que penaliza explícitamente teletransportar a núcleos con baja capacidad libre, evitando que el router inunde núcleos saturados.
   • Ganancia de Salto ($g_{hop}$): Una recompensa direccional para movimientos que reducen la distancia inter-núcleo hacia el objetivo, compensando cuando el puerto de aterrizaje está lejos de la posición de preparación óptima.
   • Ganancia de Capa Frontal ($\Delta_F$): Reducción inmediata de la distancia física para la puerta actual.
   • Anticipación ($\tilde{\Delta}_E$): Una suma ponderada por decaimiento de reducciones futuras de distancia.

2. Alivio Proactivo de Congestión:
   DSABRE mantiene un vector de demanda explícito sobre los núcleos. Antes de que un núcleo se sature (alta demanda, baja capacidad), el router genera proactivamente "candidatos de alivio" para teletransportar qubits inactivos lejos de núcleos de alta demanda. Estos movimientos se puntuan dentro de la misma función objetivo (con $\Delta_F=0$) y compiten directamente con los movimientos impulsados por puertas. Esto previene la "cascada de expulsión" que conduce a bloqueos muertos en sistemas reactivos.

3. Conjunto Extendido Inter-Núcleo de Capas BFS:
   El SABRE estándar construye conjuntos de anticipación en orden topológico, lo que puede mezclar cables no relacionados. TELESABRE utiliza capas BFS pero pondera las puertas arbitrariamente. DSABRE construye el conjunto de anticipación inter-núcleo capa por capa utilizando Búsqueda en Anchura (BFS) sobre el DAG. Crucialmente, dentro de cada capa, las puertas que comparten un cable con la frontal se emiten primero. El decaimiento de anticipación se aplica basándose en la profundidad BFS ($\gamma^{dep(g)}$), asegurando que los sucesores a corto plazo dominen la señal y que el conjunto respete las dependencias del DAG más estrictamente que el ordenamiento topológico.

Resultados Experimentales
Los autores evaluaron DSABRE frente a TELESABRE y pytket-dqc (un router basado en teletransportación de puertas) a través de 18 circuitos MQT-Bench con 25, 36 y 64 qubits lógicos, utilizando arquitecturas de cuadrícula de cuadrículas (B-grid y H-grid).

• Reducción de EPR: DSABRE reduce el consumo geométrico medio de EPR en un 41–44% en comparación con TELESABRE y en un 16–68% en comparación con pytket-dqc.
• Escalabilidad: En un circuito aleatorio de 64 qubits, TELESABRE falló en converger en todas las semillas, mientras que DSABRE completó el enrutamiento. Un barrido de escalabilidad en circuitos de Transformada Rápida de Fourier Cuántica (QFT) de hasta 360 qubits confirmó que DSABRE mantiene su ventaja a medida que aumentan el tamaño del circuito y la arquitectura.
• Estudios de Ablación:
  • Eliminar la penalización de capacidad aumentó el consumo geométrico medio de EPR en ~59% (25q) y ~59% (64q), identificándola como el componente más crítico.
  • Desactivar el alivio proactivo de congestión aumentó el EPR en un 23.4% en la suite de 64q, con circuitos densos (AE, QFT) viendo un aumento superior al 100%.
  • Reemplazar el conjunto extendido de capas BFS con ordenamiento topológico aumentó el EPR en un 3–11%, con ganancias crecientes para circuitos más grandes.
• Sensibilidad al Costo: A medida que aumenta el costo relativo de la teletransportación ($c_{tele}$) (simulando hardware de enlace fotónico), la brecha de rendimiento entre DSABRE y TELESABRE se amplía, con DSABRE ahorrando hasta ~39% más de EPRs en ratios de costo altos.

Significado y Afirmaciones
El artículo afirma que el enrutamiento distribuido se beneficia menos de fórmulas complejas de puntuación por candidato y más de asegurar que las señales de anticipación y las restricciones de capacidad arquitectónica ingresen en el mismo paso de puntuación. Al integrar el alivio proactivo de congestión y una puntuación consciente de la capacidad, DSABRE evita los bloqueos muertos y el consumo excesivo de EPR que plagan a los routers reactivos defensivos.

Los autores posicionan a DSABRE como complementario a los métodos de asignación estática (como la partición de hipergrafos) y a los programadores conscientes del tiempo. Señalan que, aunque DSABRE actualmente utiliza solo teledata (teletransportación de estado), está diseñado para ser un motor de enrutamiento robusto que puede combinarse con otras primitivas o pasadas de ejecución en ráfaga en trabajos futuros. Los resultados sugieren que la gestión explícita de la capacidad es un componente necesario para escalar la compilación cuántica distribuida.