Geometry-Informed Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

Resumen Técnico: Esquemas de Aproximación Cuántica de Tiempo Polinomial con Información Geométrica para la Optimización con Restricciones

Planteamiento del Problema
La optimización combinatoria con restricciones implica encontrar configuraciones óptimas sujetas a restricciones estrictas (por ejemplo, asignación, emparejamiento, enrutamiento). Aunque existen algoritmos clásicos para subclases específicas tratables, muchos de estos problemas son NP-duros. Los enfoques cuánticos, particularmente el Algoritmo de Aproximación de Optimización Cuántica (QAOA), enfrentan desafíos en dispositivos de la era NISQ:

1. Factibilidad: El QAOA estándar suele muestrear fuera del subespacio factible definido por las restricciones estrictas.
2. Ruido: El ruido del dispositivo induce violaciones de las restricciones, degradando la calidad de las muestras.
3. Garantías: Los métodos existentes a menudo carecen de garantías de rendimiento rigurosas de extremo a extremo (tiempo de ejecución polinomial con alta probabilidad de encontrar un óptimo) bajo condiciones de ruido realistas.

El artículo aborda la pregunta: ¿Cuándo un muestreador cuántico ruidoso permite un algoritmo de tiempo polinomial de extremo a extremo con garantías de rendimiento?

Metodología
Los autores proponen el algoritmo Noisy Polytime Hybrid Quantum-Classical (NP-HQ), un pipeline completo que integra el muestreo cuántico con el postprocesamiento clásico determinista. La metodología se basa en tres pilares:

1. El Kernel OFM y CE-QAOA:
   El enfoque utiliza el kernel Onah–Firt–Michielsen (OFM), que define una codificación específica para problemas como el Problema del Viajante (TSP) y el Problema de Asignación Cuadrática (QAP).

   • Codificación: Utiliza una codificación one-hot donde cada bloque lógico tiene exactamente una excitación.
   • Dinámica: Emplea CE-QAOA (Constraint-Enhanced QAOA) con un mezclador XY local de bloque que preserva el subespacio one-hot.
   • Garantías: Basándose en el trabajo previo [1], se demuestra que el muestreador CE-QAOA ideal asigna una masa de probabilidad de orden inverso-polinomial ($p_0 = \Omega(n^{-k})$) al conjunto de soluciones óptimas, siempre que se cumplan condiciones geométricas específicas (separación de fase).

2. Reparación y Calificación Determinista:
   Para manejar el ruido y las muestras infactibles, el pipeline incluye un postprocesador clásico:

   • Verificación de Factibilidad: Verifica las restricciones one-hot.
   • Reparación: Utiliza algoritmos deterministas de tiempo polinomial (específicamente el algoritmo húngaro para problemas de asignación o heurísticas basadas en intercambios/swaps) para proyectar las cadenas de bits ruidosas e infactibles hacia la solución factible más cercana (por ejemplo, una permutación válida).
   • Calificación (Scoring): Evalúa la función objetivo exacta sobre los candidatos reparados.
   • Base Teórica: Se demuestra que el mapa de reparación es una contracción en la distancia de variación total y no disminuye la masa de probabilidad del conjunto óptimo.

3. Análisis de Robustez al Ruido:
   Los autores derivan un límite de tipo Lipschitz que relaciona el ruido del dispositivo con la degradación de la masa de muestreo óptimo. Establecen una "ventana de ruido" donde, si el error efectivo por capa es suficientemente bajo, la masa óptima ruidosa permanece como un inverso-polinomial. Esto permite el cálculo del presupuesto de disparos (shots) polinomial requerido para recuperar un óptimo con alta probabilidad.

Contribuciones Clave

1. FPRAS$_q$ (Exact-Hit):
   En el régimen de bajo ruido, donde el muestreador ideal asigna una masa inverso-polinomial al óptimo, el pipeline NP-HQ constituye un Esquema de Aproximación Aleatorizada Completamente Polinomial (FPRAS$_q$). Garantiza encontrar el óptimo global con una probabilidad de $1-\delta$ en tiempo polinomial (llamadas a circuitos cuánticos + postprocesamiento clásico).

2. $\varepsilon$-PTQAS (Aproximación):
   Más allá del régimen de impacto exacto, el pipeline proporciona un Esquema de Aproximación Cuántica de Tiempo Polinomial $\varepsilon$ ($\varepsilon$-PTQAS). Si la inflación del objetivo inducida por la reparación está controlada, el algoritmo produce una aproximación de $(1+\varepsilon)$ con tiempo de ejecución polinomial.

3. Separación Cuántico-Clásica:
   El artículo establece una separación condicional entre el pipeline NP-HQ y las estrategias puramente clásicas. Incluso si un muestreador clásico tuviera acceso a:

   • Los mismos mapas de reparación eficientes (proyección húngara).
   • Acceso perfecto a las estructuras de restricción (por ejemplo, muestrear uniformemente de cadenas con one-hot por fila).
   • Tiempo polinomial.
     No puede reproducir el solapamiento óptimo inverso-polinomial de las familias admisibles al kernel de NP, a menos que NP $\subseteq$ BPP. La ventaja cuántica reside estrictamente en la generación de la distribución de muestreo, no en el procesamiento clásico.

4. Heavy-Hitter QAOA (HH-QAOA):
   Un refinamiento que reduce los costos de postprocesamiento clásico. Al aprovechar la geometría de la distribución cuántica, el algoritmo identifica "heavy hitters" (muestras de alta frecuencia) y filtra el conjunto de candidatos. Esto reduce la complejidad del postprocesamiento clásico de $O(n^{k+4})$ a $O(n^{k+3})$ (o menor con mayor compresión) sin sacrificar las garantías de aproximación.

5. Demostración en Hardware:
   El pipeline completo se ejecutó en dos procesadores distintos IBM Eagle-r3 de 127 qubits (ibm_brisbane e ibm_sherbrooke) utilizando instancias de QOptlib TSP con hasta 100 variables lógicas.

   • Resultados: A pesar del fuerte ruido (tasas de error de dos qubits $\sim 10^{-3}$ a $10^{-2}$), la reparación determinista restauró la factibilidad para todas las muestras.
   • Desempeño: Las soluciones reparadas igualaron o mejoraron los recorridos de referencia publicados en cada caso probado, demostrando la viabilidad del enfoque en el hardware actual.

Significancia y Reivindicaciones
El artículo afirma proporcionar la primera garantía de optimización de extremo a extremo para un pipeline híbrido cuántico-clásico bajo ruido de dispositivo que combina:

• Recuperación de impacto exacto con disparos finitos.
• Restauración de factibilidad determinista.
• Límites explícitos de ruido finito sobre la masa óptima recuperada.
• Complejidad de disparos polinomial y tiempo de postprocesamiento polinomial.

Los autores argumentan que la optimización cuántica con restricciones debe verse como un pipeline unificado donde la estructura del problema se explota tanto en la dinámica cuántica (vía el kernel OFM) como en los mapas de reparación clásicos. El trabajo demuestra que, incluso en la era NISQ, los circuitos restringidos de poca profundidad combinados con un postprocesamiento clásico riguroso pueden producir esquemas de aproximación probables y resultados competitivos en hardware real.

Limitaciones y Alcance

• Las garantías son dependientes de la instancia, dependiendo de la existencia de una separación de fase positiva ($\delta > 0$) y un peso de envolvente del mezclador suficiente.
• La garantía de "impacto exacto" solo se mantiene dentro de una ventana de ruido específica; fuera de ella, el esquema se degrada a un esquema de aproximación.
• La separación cuántico-clásica es condicional a la suposición de que NP $\not\subseteq$ BPP.
• Los experimentos de hardware utilizaron parámetros de inicio en caliente (warm-start) fijos de una optimización genérica de QAOA en lugar de una re-optimización nativa del hardware, probando la transferibilidad de los parámetros a dispositivos ruidosos.