Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models

Resumen Técnico: Ajuste de Parámetros Casi Óptimo de QAOA de Nivel 1 para Modelos de Ising

Planteamiento del Problema
El Algoritmo de Optimización Cuántica Aproximada (QAOA) es un algoritmo híbrido cuántico-clásico diseñado para resolver problemas de optimización combinatoria, como la Optimización Binaria Cuadrática Sin Restricciones (QUBO), mediante la codificación de soluciones en el estado fundamental de un Hamiltoniano. Si bien aumentar la profundidad del circuito ($p$) mejora teóricamente la calidad de la solución, las implementaciones prácticas en dispositivos de Escala Intermedia de Ruido Cuántico (NISQ) están limitadas a profundidades bajas ($p=1$, o QAOA1) debido al ruido de las puertas, las limitaciones de conectividad y los errores de preparación del estado.

Un cuello de botella crítico en QAOA1 es la optimización de sus dos parámetros variacionales, $\gamma$ y $\beta$. A pesar de su baja dimensionalidad, el paisaje de costos es altamente oscilatorio, con tasas de oscilación que aumentan con el tamaño, la densidad y la variabilidad de los pesos del problema. La sabiduría convencional sugiere que las búsquedas de cuadrícula gruesas seguidas de una minimización local son suficientes; sin embargo, este trabajo demuestra que tales enfoques a menudo fallan en capturar el verdadero óptimo global debido a la distorsión del paisaje y el aliasing, lo que conduce a estimaciones de parámetros subóptimas. Además, los métodos heurísticos existentes para la inicialización de parámetros carecen de garantías de rendimiento o dependen de estructuras de grafos específicas (por ejemplo, grafos regulares no ponderados) que no se generalizan a instancias reales complejas y ponderadas.

Metodología
Los autores proponen una estrategia rigurosa y agnóstica al problema para optimizar los parámetros de QAOA1 para modelos de Ising (el equivalente cuántico de QUBO) en tiempo polinomial. La metodología avanza a través de cuatro pasos teóricos y algorítmicos principales:

1. Análisis de Fourier y Requisitos de Muestreo:
   El artículo modela el valor esperado de QAOA1 como una serie de Fourier parcial. Al derivar expresiones de forma cerrada para el valor esperado (Teorema 1 y Corolario 1), los autores determinan analíticamente la frecuencia máxima ($\omega_{\max}$) del paisaje de costos a lo largo de la dimensión $\gamma$. Esta frecuencia depende de las intensidades de acoplamiento ($J_{uv}$) y los campos externos ($h_i$) de la instancia específica del problema. Aplicando el Teorema de Muestreo de Nyquist-Shannon, establecen la resolución de muestreo mínima ($\Delta\gamma$) requerida para reconstruir con precisión el paisaje de costos sin distorsión. Esto resuelve el problema del submuestreo en las búsquedas de cuadrícula gruesas.

2. Reducción de Dimensionalidad:
   Una contribución teórica clave es la reducción del problema de optimización bidimensional sobre $(\gamma, \beta)$ a una búsqueda unidimensional sobre $\gamma$.

• Para modelos de Ising sin campos externos, el $\beta^*$ óptimo se deriva analíticamente como una función de $\gamma$ (Teorema 5).
• Para modelos con campos externos, el $\beta^*$ óptimo se encuentra resolviendo un polinomio de cuarto grado derivado de las condiciones de optimalidad de primer orden (Teorema 6).
  Esta transformación permite que el algoritmo realice una búsqueda de línea sobre $\gamma$ mientras calcula el $\beta^*$ óptimo en cada punto, reduciendo significativamente la complejidad computacional.

3. Algoritmo de Optimización:
   Para encontrar el óptimo global de la función univariante resultante, los autores emplean un algoritmo de subdivisión (Algoritmo 1) basado en el análisis de intervalos (algoritmo de Green). Este método estima eficientemente el módulo máximo del polinomio trigonométrico, asegurando la identificación del $\gamma^*$ casi óptimo sin necesidad de búsquedas exhaustivas de cuadrícula.

4. Concentración de Óptimos:
   El artículo demuestra rigurosamente que, para grafos regulares densos y grandes, el $\gamma^*$ globalmente óptimo $\in \mathbb{R}^+$ se concentra muy cerca de cero y coincide con el primer óptimo local (Teorema 7). El análisis empírico en grafos de tamaño finito confirma que las instancias "adversarias" (donde el primer óptimo local difiere del óptimo global) son raras, ocurriendo principalmente en grafos pequeños y dispersos. Esta visión permite una simplificación adicional: en lugar de una búsqueda de línea completa, se puede utilizar un descenso de gradiente inicializado cerca de $\gamma \approx 0$, siempre que el tamaño del paso respete el límite de muestreo derivado de la frecuencia máxima.

Resultados Clave
La estrategia propuesta fue validada utilizando QAOA Recursivo (RQAOA), un método que utiliza QAOA1 como una subrutina para reducir recursivamente el tamaño del problema. Los autores compararon su enfoque en grafos de Erdős-Rényi densos y ponderados de gran tamaño (128 y 256 vértices) con diversas probabilidades de arista y distribuciones de peso.

• Sin Campos Externos: El método propuesto (RQAOA1 con parámetros casi óptimos) superó consistentemente tanto al RQAOA1 optimizado groseramente como a la Programación Semidefinida (SDP) clásica en todas las instancias probadas. En contraste, el RQAOA1 optimizado groseramente generalmente falló en superar a la SDP.
• Con Campos Externos: Los autores observaron que el RQAOA1 estándar exhibía un rendimiento inconsistente en modelos con campos. Para abordar esto, introdujeron "Iter-QAOA", una variante que utiliza un procedimiento de redondeo iterativo simplificado. Iter-QAOA, combinado con la estrategia de ajuste de parámetros propuesta, superó consistentemente a la SDP y a las variantes estándar de RQAOA1, demostando robustez a través de diferentes densidades de grafos.
• Instancias Adversarias: Las pruebas empíricas mostraron que la probabilidad de encontrar un grafo adversario (donde el primer óptimo local no es el global) se estabiliza en aproximadamente un 1% para grafos con $n > 14$ nodos, validando la estrategia de usar descenso de gradiente cerca de cero para la mayoría de los casos prácticos.

Significancia y Reivindicaciones
El artículo afirma resolver el desafío de encontrar eficientemente parámetros globalmente casi óptimos para QAOA1 en problemas QUBO arbitrarios. La importancia del trabajo radica en:

• Garantías Rigurosas: A diferencia de otros enfoques heurísticos previos, este método proporciona algoritmos de tiempo polinomial con casi-optimalidad demostrable para pesos conmensurables que no escalan exponencialmente con el tamaño del sistema.
• Agnóstico al Problema: La estrategia no depende de supuestos sobre la simetría, estructura o distribución de pesos del grafo, lo que la hace aplicable a modelos de Ising ponderados generales.
• Eficiencia Práctica: Al reducir el espacio de búsqueda y aprovechar las soluciones analíticas para $\beta^*$, el método evita la inviabilidad computacional de las búsquedas de cuadrícula 2D de alta resolución, evitando al mismo tiempo los problemas del muestreo grueso.
• Mejora de Rendimiento: Los resultados demuestran que, con un ajuste de parámetros adecuado, los algoritmos cuánticos de profundidad superficial (QAOA1) pueden superar a las heurísticas clásicas de vanguardia (SDP) en instancias densas y ponderadas, resaltando el papel crítico de la optimización de parámetros en los algoritmos cuánticos variacionales.

Los autores concluyen que su enfoque aborda eficazmente el cuello de botella del ajuste de parámetros para QAOA1, permitiendo aproximaciones más fiables y de alta calidad para problemas de optimización combinatoria en el hardware cuántico actual y cercano.