Resumen Técnico: RASP-QAOA

Planteamiento del Problema

La simulación exacta del Algoritmo de Optimización Cuántica Aproximada (QAOA) depende de representaciones computacionales clásicas que exhiben características de rendimiento marcadamente divergentes según la estructura del grafo, la profundidad del circuito ($p$), la precisión numérica y la memoria disponible. Ningún backend o representación única es uniformemente óptimo. Por ejemplo, las implementaciones de estado completo en GPU son eficientes cuando la memoria lo permite pero fallan para valores grandes de $n$; la contracción de tensores evita la materialización del estado pero escala mal con el ancho de contracción; además, los evaluadores locales son efectivos solo a profundidades bajas. Asimismo, los mezcladores que preservan las restricciones pueden reducir el tamaño de la base de $2^n$ a $\binom{n}{k}$, abriendo regiones factibles distintas.

Los enfoques actuales suelen seleccionar un "nombre de backend" (por ejemplo, CUDA-Q), lo que fija implícitamente la representación, el adaptador, el modo de precisión y la política de memoria. Esta selección gruesa no logra explotar la heterogeneidad de los simuladores disponibles. El artículo argumenta que la decisión debe tomarse al nivel de la acción ejecutable —una tupla específica de representación, adaptador, configuración, precisión y política de memoria— en lugar de un backend genérico. El desafío central es seleccionar la acción óptima para una solicitud de QAOA específica $x = (G, H_C, p, M, \epsilon, B, H)$, donde $G$ es el grafo, $p$ es la profundidad y $B$ es el presupuesto de memoria, asegurando al mismo tiempo que la acción sea semánticamente compatible y pueda completarse dentro de las restricciones de recursos.

Metodología: RASP-QAOA

El autor propone RASP-QAOA (Selección por Instancia Basada en Recursos para QAOA Exacto), un marco de selección de dos etapas que opera sobre un portafolio de diez acciones ejecutables distintas. El método separa la decisión en compatibilidad (factibilidad) y ordenación (predicción de rendimiento).

1. Filtrado de Compatibilidad

Antes de la clasificación, el sistema filtra el portafolio de acciones para formar un conjunto de candidatos $C(x)$. Una acción $a$ se incluye solo si satisface cuatro condiciones:

• Semántica ($S_a$): La representación y el mezclador soportan las restricciones del problema (por ejemplo, los mezcladores de peso fijo requieren representaciones de subespacio específicas).
• Precisión ($P_a$): La precisión configurada (por ejemplo, fp32 vs. fp64) coincide con la tolerancia numérica de la solicitud.
• Despliegue ($D_a$): El paquete de software y la ruta del dispositivo requeridos están disponibles.
• Memoria ($M_a$): Una estimación de pico de memoria calibrada (basada en $n$, $p$ y el tipo de representación) se ajusta dentro de $\min(B, 0.9 \times \text{VRAM})$.

Esta etapa asegura que la acción seleccionada sea capaz de implementar la semántica de QAOA solicitada y los requisitos de ejecución.

2. Estrategia de Ordenación

Una vez establecido $C(x)$, RASP-QAOA ordena las acciones utilizando un enfoque híbrido:

• Soporte Aprendido ($A_\phi$): Para acciones observadas durante el desarrollo, un clasificador basado en características $q_\phi(a, z(x))$ predice el rendimiento. El vector de características $z(x)$ incluye el tamaño del grafo, densidad, profundidad, estadísticas de grado y aproximaciones del ancho de contracción o conos causales.
• Estimación Analítica: Si $C(x)$ contiene acciones fuera del soporte aprendido (es decir, $C(x) \cap A_\phi = \emptyset$), el sistema recurre a estimaciones de trabajo conscientes de la representación. Estas son aproximaciones analíticas basadas en el escalamiento teórico, tales como $p2^n$ para estado completo, $p\binom{n}{k}$ para peso fijo, y estimaciones de ancho de contracción para métodos tensoriales.

La política final selecciona la acción con la puntuación más alta del conjunto aprendido si está disponible; de lo contrario, selecciona la acción con la estimación de trabajo analítico más baja. Las dos etapas nunca se comparan en una escala compartida; la vía aprendida tiene prioridad.

Contribuciones Clave

1. Formulación por Instancia: El objeto de decisión se define como una clave de acción ejecutable completa (representación + adaptador + configuración), con la compatibilidad determinada estrictamente antes de la clasificación de rendimiento.
2. Política de Selección Híbrida: RASP-QAOA integra verificaciones de compatibilidad conscientes de la solicitud, ordenación basada en características para acciones soportadas por el desarrollo y ordenación analítica para acciones compatibles fuera del soporte aprendido.
3. Evaluación Resuelta por Componentes: El artículo proporciona una evaluación rigurosa en un portafolio de hardware H200 nuevo, distinguiendo entre cobertura (encontrar una acción válida) y calidad de clasificación (encontrar la acción más rápida válida).

Resultados Experimentales

La evaluación se realizó con un conjunto de prueba de 60 solicitudes nuevo utilizando GPUs NVIDIA H200, disjunto de los datos de desarrollo.

• Cobertura: Entre las 60 solicitudes, 31 tenían al menos una acción admisible que se completó y validó (completitud estricta). RASP-QAOA seleccionó con éxito una acción válida para todas las 31 de estas solicitudes. En contraste, el CUAOA seleccionado durante el desarrollo cubrió solo 19, y un baseline de prioridad estática cubrió 23.
• Calidad de Clasificación: En las 31 solicitudes solubles, RASP-QAOA logró 27/31 selecciones top-1 (dentro del primer grupo del 5% equivalente en tiempo) y 31/31 selecciones top-2.
• Métricas de Rendimiento:
  • Regret de media geométrica: 1.051.
  • PAR10 penalizado por fallo: 0.0396 veces el del CUAOA seleccionado en desarrollo (una mejora de 25.26 veces).
  • Tiempo de Planificación: Mediana de 22.5 $\mu$s.
• Cruce Estructural: Un experimento de cruce separado de 30 solicitudes variando las estructuras de los grafos (con $n=20, p=2$ fijos) mostró que el uso de características estructurales completas mejoró la selección top-1 de 12/30 a 25/30 en comparación con el uso de solo $n$ y $p$. Un simple "decision stump" de profundidad 1 igualó el rendimiento del gradient boosting, lo que sugiere que las ganancias provienen de las características de la representación más que de la complejidad del clasificador.
• Robustez: Los resultados se mantuvieron estables a través de diferentes horizontes de reutilización ($h=1$ a $32$) y configuraciones de tolerancia numérica.

Significado y Reivindicaciones

El artículo afirma que la selección de representación consciente de los recursos es crítica para la simulación exacta de QAOA a escalas de $n \le 35$ y $p \le 5$. La contribución principal no es un nuevo simulador, sino un mecanismo de selección que empareja dinámicamente la instancia del problema con la representación computacional más adecuada.

El autor enfatiza que las mejoras de rendimiento observadas son impulsadas por:

1. Amplitud del Portafolio: La capacidad de identificar y seleccionar representaciones (como peso fijo o evaluadores locales) que las bases seleccionadas durante el desarrollo (como CUAOA) no pueden usar debido a incompatibilidades semánticas o de memoria.
2. Ordenación Basada en Características: La capacidad de clasificar acciones compatibles superpuestas basándose en la estructura de la instancia.

El artículo establece explícitamente que los resultados son específicos para el hardware probado (H200), el stack de software y la simulación exacta de valores de expectativa. No pretende resolver la simulación aproximada ni otros objetivos de hardware, señalando que estos requerirían nuevas definiciones de acción y calibración. El trabajo demuestra que separar las verificaciones de compatibilidad de la clasificación de rendimiento permite una política de selección robusta que maximiza la cobertura manteniendo una alta precisión de clasificación.