Improving the efficiency of QAOA using efficient parameter transfer initialization and targeted-single-layer regularized optimization with minimal performance degradation

Resumen Técnico: Mejora de la Eficiencia de QAOA mediante la Transferencia de Parámetros y la Optimización con Regularización Dirigida

Planteamiento del Problema
El Algoritmo de Optimización Aproximada Cuántica (QAOA) es un candidato principal para resolver Problemas de Optimización Combinatoria (COPs), específicamente el problema de Máximo Corte (MaxCut), en dispositivos cuánticos de corto alcance. Sin embargo, el QAOA enfrenta desafíos significativos a medida que el tamaño del problema ($n$) y la profundidad del circuito ($p$) aumentan. El paisaje de optimización se vuelve altamente no convexo, caracterizado por un espacio de soluciones que crece exponencialmente ($2^n$) y un número de parámetros que aumenta linealmente ($2p$). Esta complejidad suele atrapar a los optimizadores clásicos en mínimos locales subóptimos, particularmente para familias de grafos ponderados, lo que conduce a ratios de aproximación ($r$) deficientes. Además, la optimización completa de todos los $2p$ parámetros es computacionalmente costosa, requiriendo una cantidad sustancial de tiempo y recursos, lo que dificulta la demostración práctica de la ventaja cuántica.

Metodología
Los autores proponen una estrategia híbrida que combina la inicialización por transferencia de parámetros con la optimización de capa única dirigida y la regularización L2 para mejorar la eficiencia de QAOA minimizando la degradación del rendimiento.

1. Inicialización por Transferencia de Parámetros:

   • El enfoque aprovecha la observación de que los parámetros optimizados para instancias de problemas similares tienden a agruparse.
   • Un grafo "donante" ($G_1$) con un pequeño número de nodos ($n_d = 8$) se optimiza completamente. La inicialización de este donante utiliza el Recocido Cuántico Trotterizado (TQA) con $t=0.75$, seguido de una optimización completa usando el optimizador Adagrad.
   • Estos parámetros optimizados $\{\gamma^*_i, \beta^*_i\}$ se transfieren a un grafo "receptor" ($G_2$) con $n_a \ge n_d$ nodos dentro de la misma familia de grafos.

2. Optimización de Capa Única Dirigida:

   • En lugar de re-optimizar todos los $2p$ parámetros para el grafo receptor, el método identifica una capa "dirigida" específica ($p_k$) que produce el mejor ratio de aproximación cuando se optimiza individualmente.
   • Para una profundidad fija de $p=15$, los autores probaron sistemáticamente cada capa $p_k \in [1, 15]$ para determinar la capa óptima más probable para diferentes familias de grafos (3-Regular, Erdős–Rényi, Barabási–Albert).
   • Solo los parámetros de esta capa única se optimizan utilizando el optimizador COBYLA (Optimización por Aproximación Lineal Restringida), mientras que todas las demás capas permanecen fijas en sus valores transferidos.

3. Regularización (L2/Ridge):

   • Para abordar la inconsistencia donde la optimización de capa única dirigida ($r_s$) ocasionalmente supera a la optimización completa ($r_f$) debido a que el optimizador queda atrapado en mínimos locales durante el proceso de optimización completa, los autores introducen la regularización L2 (Ridge).
   • Se añade un término de penalización $\lambda \sum (\gamma_k^2 + \beta_k^2)$ a la función de costo. Esto suaviza el paisaje de la solución, ayudando al optimizador a escapar de los mínimos locales y mejorando la fiabilidad de la optimización completa ($r_f$).

Contribuciones Clave y Resultados
El estudio se llevó a cabo a través de tres familias de grafos no ponderados (3-Regular, Erdős–Rényi, Barabási–Albert) y tres familias ponderadas, utilizando grafos con conteos de nodos que oscilan entre 8 y 24.

• Rendimiento en Grafos No Ponderados:

  • Para grafos 3-Regulares no ponderados (u3R), el enfoque de transferencia de parámetros logró un ratio de aproximación medio de 0.9443 para la optimización de capa única dirigida ($r_s$), en comparación con 0.9551 para la optimización completa ($r_f$). Esto representa el 98.88% del rendimiento óptimo.
  • Crucialmente, este enfoque produjo una aceleración computacional de 8.06× en comparación con la optimización completa.
  • Se observaron tendencias similares para los grafos Erdős–Rényi no ponderados (uER) y Barabási–Albert no ponderados (uBA), donde $r_s$ se mantuvo consistentemente cerca de $r_f$ mientras reducía significativamente el tiempo de optimización ($\tau$).

• Rendimiento en Grafos Ponderados:

  • 3-Regular Ponderado (w3R): El método funcionó bien, siendo que la inicialización por sí sola ($r_n$) a menudo superó el umbral clásico de Goemans-Williamson ($r_{GW} \ge 0.878$). La optimización dirigida mejoró aún más estos resultados.
  • Erdős–Rényi Ponderado (wER): El enfoque tuvo dificultades con un mayor número de nodos ($n_a \ge 14$), donde $r_s$ cayó por debajo del umbral $r_{GW}$. Para estas familias ponderadas complejas, la optimización completa siguió siendo necesaria para lograr soluciones de alta calidad.
  • Barabási–Albert Ponderado (wBA): Esta familia mostró un comportamiento híbrido; si bien la optimización completa fue ligeramente más eficiente, la optimización dirigida siguió siendo una alternativa viable.

• Impacto de la Regularización:

  • Sin regularización, la optimización de capa única dirigida superó a la optimización completa en el 8.92% de los casos de prueba (indicando que la optimización completa quedó atrapada en mínimos locales).
  • La aplicación de la regularización L2 redujo esta inconsistencia al 3.81%, mejorando significativamente la robustez de la optimización completa.

• Comparación de Optimizadores e Inicialización:

  • Entre varios optimizadores (COBYLA, POWELL, GSLS, NELDER-MEAD, SPSA), se identificó a COBYLA como el más adecuado, ofreciendo una precisión comparable con el menor tiempo de optimización.
  • La inicialización por transferencia de parámetros superó consistentemente a TQA e inicialización aleatoria tanto en el ratio de aproximación como en el número de pasos de optimización requeridos.

Significancia y Reivindicaciones
El artículo demuestra que una inicialización de parámetros eficiente combinada con la optimización de capa única dirigida puede mejorar significativamente la eficiencia de QAOA con una degradación mínima del rendimiento.

Los autores afirman que esta estrategia equilibra eficazmente el compromiso entre precisión y costo computacional. Al transferir parámetros de instancias pequeñas totalmente optimizadas a otras más grandes y complejas, el método proporciona un punto de partida "casi óptimo" que reduce el espacio de búsqueda. La optimización posterior de una sola capa estratégicamente elegida refina la solución sin el costo exponencial de la re-optimización completa.

El trabajo destaca que, si bien este enfoque es altamente efectivo para familias de grafos no ponderados y de ciertas topologías ponderadas (como w3R), no es una solución universal para todas las topologías ponderadas (específicamente wER), donde la complejidad del paisaje de costos aún requiere la optimización completa. La introducción de la regularización L2 se presenta como una estrategia de mitigación crítica para estabilizar el paisaje de optimización, asegurando que la optimización completa no tenga un rendimiento inferior en relación con los métodos selectivos. En última instancia, el estudio sugiere una vía para hacer que el QAOA sea más práctico para problemas combinatorios a gran escala al reducir la carga computacional clásica asociada con el ajuste de parámetros.