When T-Depth Misleads: Predicting Fault-Tolerant Quantum Execution Slowdown under Magic-State Delivery Constraints

Resumen Técnico: Cuando la Profundidad T Engaña

1. El Problema

En la computación cuántica tolerante a fallos (FTQC), la ejecución eficiente de algoritmos depende críticamente de la producción y entrega de estados mágicos (magic states), necesarios para realizar operaciones no Clifford (como las puertas T).

• La limitación actual: Las métricas de compilación tradicionales, como la profundidad T (T-depth), asumen una entrega ilimitada de estados mágicos. La profundidad T mide el número mínimo de capas secuenciales de puertas T bajo recursos infinitos.
• La realidad física: En la práctica, las fábricas de estados mágicos tienen una tasa de producción limitada (capacidad $C$) y un búfer de almacenamiento finito ($B$).
• El conflicto: Un circuito con una profundidad T baja puede tener un rendimiento de ejecución peor que uno con mayor profundidad T si la demanda de puertas T se concentra en "ráfagas" que exceden la capacidad de entrega. Esto provoca pausas (stalls) donde los qubits lógicos deben permanecer inactivos bajo corrección de errores activa, aumentando el volumen espacio-temporal y el riesgo de fallos.
• Fenómeno de inversión: El artículo identifica que, bajo restricciones de entrega, un programa con menor profundidad estática puede terminar ejecutándose más lento que uno con mayor profundidad estática (inversión de profundidad T).

2. Metodología y Modelo

Los autores proponen un modelo de ejecución que cuantifica el desequilibrio entre la demanda y la oferta de estados mágicos.

• Representación del Circuito: Se modela como un Grafo Acíclico Dirigido (DAG) donde los nodos son operaciones y las aristas son dependencias.
• Parámetros del Sistema:
  • $C$: Capacidad de entrega (estados mágicos producidos por paso de tiempo).
  • $B$: Capacidad del búfer (estados almacenables de antemano).
  • $A_\sigma(t)$: Demanda acumulada hasta el tiempo $t$ bajo un programa de ejecución $\sigma$.
• Métricas Propuestas:
  1. Ratio de Holgura (Slack Ratio): Una métrica estructural que mide la flexibilidad de programación del circuito. Se calcula como la fracción de puertas T que tienen "holgura" positiva (diferencia entre el tiempo de inicio más tardío posible -ALAP- y el más temprano posible -ASAP-). Indica cuánto se puede redistribuir la demanda de puertas T sin violar dependencias.
  2. $\Delta_{max}$: Una métrica a nivel de programa de ejecución que mide el desequilibrio acumulativo entre la demanda y la capacidad de producción. Se define como el máximo hueco vertical entre la curva de demanda acumulada y la línea de producción ($C \times t$).
     • Si $\Delta_{max} > B$, se genera un retraso inevitable.
• Límite Inferior Provable: Derivan una cota inferior para el tiempo de ejecución real ($T_{exe}$):
  $$T_{exe} \ge T_{static} + \left\lceil \frac{\max(0, \Delta_{max} - B)}{C} \right\rceil$$
  Esto establece que el retraso es proporcional al exceso de demanda sobre la capacidad de búfer, dividido por la tasa de producción.

3. Contribuciones Clave

1. Demostración de la insuficiencia de la Profundidad T: Se prueba que minimizar solo la profundidad T no garantiza un mejor rendimiento bajo restricciones de entrega de estados mágicos.
2. Nuevos Predictores:
   • El Ratio de Holgura es un predictor estructural más fuerte que la profundidad T para predecir riesgos de pausa e inversión de rendimiento.
   • $\Delta_{max}$ es el predictor más fuerte a nivel de programación para el retraso de ejecución y las pausas.
3. Validación Empírica: Se valida el límite inferior en 4,904 instancias finitas (circuitos sintéticos y trazas reales). No se observó ninguna violación del límite. El 88.9% de las instancias cayeron dentro de un ciclo del límite predicho.
4. Herramienta de Evaluación: Se libera un marco de trabajo (GitHub: C2-Q/BARC) con generadores de DAG y scripts de análisis para reproducibilidad.

4. Resultados Experimentales

El estudio evaluó familias de DAGs sintéticos (alta, media y baja compresibilidad) y circuitos reales (Sumadores, Multiplicadores y Transformada Cuántica de Fourier - QFT).

• Inversión de Profundidad T: En circuitos de "alta compresibilidad" (alta flexibilidad estructural), el 35.7% de las configuraciones mostraron inversión: el programa optimizado por profundidad estática fue más lento que uno optimizado por holgura.
• Precisión Predictiva:
  • El $\Delta_{max}$ logró una correlación de Spearman de 0.992 para predecir el ratio de ralentización y un AUC de 0.998 para predecir pausas, superando ampliamente a la profundidad T y al ratio de holgura por separado.
  • La profundidad T sola tuvo un rendimiento predictivo muy bajo ($R^2 \approx 0.12$).
• Circuitos Reales:
  • Los circuitos aritméticos (sumadores/multiplicadores) tienen baja holgura y baja presión de entrega.
  • La QFT exacta tiene alta holgura pero una presión de entrega masiva ($\Delta_{max}$ en el orden de decenas de miles), lo que la hace extremadamente sensible a las restricciones de entrega.
• Impacto de la Aproximación: En la QFT, usar una descomposición aproximada (en lugar de exacta) no redujo la profundidad del DAG, pero sí redujo significativamente la demanda pico y el $\Delta_{max}$, disminuyendo la severidad de la ralentización sin cambiar la estructura de dependencias ideal.

5. Significado e Implicaciones

• Para el Diseño de Compiladores: Los compiladores cuánticos tolerantes a fallos (como Qiskit o tket) no deben optimizar únicamente la profundidad T. Deben incorporar $\Delta_{max}$ y el ratio de holgura como objetivos o restricciones explícitas para evitar la concentración de demanda que excede la capacidad de las fábricas de estados mágicos.
• Planificación de Arquitectura: Las métricas propuestas permiten estimar la capacidad necesaria de las fábricas de estados mágicos ($C$) y el tamaño del búfer ($B$) necesarios para ejecutar un algoritmo sin pausas significativas, sin necesidad de simulaciones completas y costosas.
• Fiabilidad y Costo: Las pausas inducidas por la falta de estados mágicos aumentan el tiempo que los qubits lógicos permanecen activos bajo corrección de errores, incrementando el volumen espacio-temporal y, por ende, la probabilidad de fallos lógicos. Minimizar $\Delta_{max}$ es, por tanto, una cuestión de fiabilidad, no solo de velocidad.
• Nueva Dirección de Investigación: Se sugiere que la "inversión de profundidad T" debe tratarse como un problema de primer orden en el diseño de compiladores para FTQC, priorizando la redistribución de la demanda temporal sobre la minimización estática de capas.

En conclusión, el artículo demuestra que la mismatch temporal entre la demanda y la oferta de recursos es el factor determinante del rendimiento en FTQC, y ofrece herramientas matemáticas y empíricas para predecir y mitigar estos retrasos de manera eficiente.