Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

Resumen Técnico: Búsqueda Cuántica Generativa para la Optimización Combinatoria

Planteamiento del Problema
Esta investigación investiga si los muestreadores cuánticos de baja profundidad pueden superar a los muestreadores clásicos en la optimización combinatoria mediante la colocación de una mayor masa de probabilidad dentro de un "cuenca de recuperación clásica". El estudio adapta la arquitectura de Autoestado Cuántico Generativo + Interacción de Configuración Seleccionada por Cuántica (GQE+QSCI), desarrollada originalmente para la química cuántica, al dominio de la optimización de grafos (específicamente, el Conjunto Independiente Máximo Ponderado, MWIS). La hipótesis central es que un muestreador cuántico podría generar una distribución de soluciones candidatas que, al ser refinadas por un algoritmo de reparación y expansión clásica, produzca una tasa de éxito mayor que los muestreadores clásicos.

Metodología
El autor propone el marco GQO+QSS (Optimización Cuántica Generativa + Búsqueda Seleccionada por Cuántica), el cual sigue un flujo de cuatro etapas:

1. Política Generativa: Un modelo de aprendizaje automático (política condicionada al grafo) genera programas de circuitos cuánticos (por ejemplo, parámetros de QAOA).
2. Muestreo Cuántico: Los circuitos se ejecutan en un simulador o en un QPU (Piast-Q) para producir cadenas de bits (soluciones candidatas).
3. Recuperación Clásica: Una función de reparación específica del problema corrige las soluciones infactibles, seguida de una expansión local (por ejemplo, vecindad de $r$-flips) para crear un subespacio de búsqueda restringido.
4. Solucionador Restringido: Un solucionador clásico exacto encuentra la solución óptima dentro de este subespacio restringido.

Formulación Teórica Clave
El artículo formaliza la cuestión del "beneficio cuántico" utilizando la masa de la cuenca de recuperación ($p_r$):
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
donde $A_r(G)$ es el conjunto de estados que, tras la reparación y la expansión de $r$-flips, contienen el óptimo global. La probabilidad de éxito con $B$ disparos es $P_{success} = 1 - (1 - p_r)^B$. El estudio postula que la métrica crítica no es el tamaño del subespacio muestreado en relación con el espacio total ($|S_Q|/2^n$), sino la masa de probabilidad $p_r$ que el muestreador coloca en la cuenca recuperable.

Protocolo Experimental

• Conjuntos de Datos: 150 instancias de MWIS con verdades de campo certificadas mediante CBC + verificación por fuerza bruta.
• Líneas Base: Se compararon nueve muestreadores, incluyendo la selección aleatoria uniforme, codiciosa (greedy), recocido simulado (SA), búsqueda tabu, búsqueda local de inicio múltiple, Metropolis, QAOA con arranque en caliente (warm-start) y QAOA de oráculo (mejor de 50 configuraciones), y una política clásica aprendida emparejada.
• Restricciones: Un protocolo pre-registrado y congelado con un presupuesto fijo de 200 disparos por muestreador.
• Hardware: Los experimentos incluyeron simulaciones y ejecución en el procesador de iones atrapados Piast-Q (20 qubits).

Resultos Clave

1. Dominancia Clásica: La búsqueda tabu y el Recocido Simulado (SA) superaron significativamente a todos los muestreadores cuánticos y clásicos aprendidos en todos los tamaños de problema probados ($n=16$ a $n=28$). La búsqueda tabu logró una masa de cuenca de recuperación ($p_r$) que varió de 0.822 en $n=16$ a 0.944 en $n=18$, con valores de 0.878 en $n=20$, 0.943 en $n=24$ y 0.901 en $n=28$. El SA osciló entre 0.088 y 0.428 en estos tamaños.
2. Bajo Rendimiento Cuántico: Todos los muestreadores cuánticos (QAOA de arranque en caliente, QAOA de oráculo y políticas generativas) perdieron ante SA y la búsqueda tabu en cada tamaño de problema bajo el protocolo justo y pre-registrado.
3. El Artefacto del "Oráculo": Los resultados positivos previos que mostraban que QAOA superaba a SA fueron identificados como artefactos de la selección de configuración por instancia (un límite superior de "oráculo"). Cuando se evaluó con configuraciones aleatorias (un método desplegable), el QAOA de oráculo alcanzó un $p_r = 0.014$ en $n=28$, muy por debajo del 0.088 de SA.
4. Paridad Clásica Aprendida: Una política clásica aprendida (140K parámetros) logró un rendimiento comparable al QAOA de oráculo ($p_r = 0.005–0.101$ vs. $0.014–0.113$), lo que indica que el circuito cuántico no ofrece ninguna ventaja estructural sobre un modelo clásico emparejado en este entorno.
5. Robustez del Hardware: Los experimentos en Piast-Q mostraron una consistencia de recuperación del 93.4% entre las muestras del QPU y el simulador, confirmando la robustez del hardware pero revelando ninguna ventaja cuántica en la calidad de la optimización.
6. Transición de Recuperación: El estudio mapeó una "transición de recuperación" donde la recuperación clásica es suficiente para $n \le 16$, pero comienza a fallar para $n \ge 20$ con la expansión de 2-flips. Sin embargo, incluso en este régimen de transición, las bases clásicas fuertes (SA, Tabu) mantuvieron un rendimiento superior.

Significancia y Reivindicaciones
El artículo se presenta como un estudio de falsificación. Su reivindicación principal es que, bajo una evaluación rigurosa y pre-registrada con líneas base clásicas emparejadas, las distribuciones de propuesta derivadas de QAOA de baja profundidad no superan a los modelos de propuesta clásicos emparejados para capturar las cuencas de recuperación clásica en MWIS.

• Sin Ventaja Cuántica: El autor afirma explícitamente que no hay ventaja cuántica para la arquitectura GQO+QSS en los regímenes probados.
• Refutación de Reivindicaciones Previas: El estudio atribuye los resultados positivos anteriores al efecto del "oráculo" de seleccionar la mejor configuración por instancia, lo cual no es un método desplegable.
• Corrección de Métrica: El artículo argumenta que la "fracción del subespacio" ($|S_Q|/2^n$) es una métrica tautológica bajo presupuestos de disparos fijos, y que la masa de la cuenca de recuperación ($p_r$) es la cantidad científicamente precisa para medir.
• Dirección Futura: El autor sugiere que, para que el muestreo cuántico aporte valor, debe colocar consistentemente más masa en la cuenca de recuperación que las bases clásicas fuertes (como SA) en los regímenes donde la recuperación clásica falla ($n \ge 55$), un desafío que los circuitos actuales de baja profundidad no han logrado alcanzar.

El trabajo concluye que, si bien la arquitectura GQO+QSS es un marco válido para la optimización híbrida, los actuales muestreadores cuánticos de baja profundidad no proporcionan una ventaja estructural sobre los métodos de búsqueda estocástica clásicos fuertes para la tarea específica de captura de la cuenca de recuperación de MWIS.