Role of overparametrization in quantum approximate optimization

Resumen Técnico: El papel de la sobreparametrización en la optimización cuántica aproximada

Planteamiento del problema
Los Algoritmos de Optimización Cuántica Aproximada (VQA) son un enfoque líder para resolver problemas en dispositivos de Escala Intermedia con Ruido (NISQ), los cuales están limitados por tiempos de coherencia cortos y errores de puerta. Una cuestión crítica abierta en este campo es determinar los recursos cuánticos mínimos (específicamente la profundidad del circuito) requeridos para resolver problemas prácticos de manera eficiente. Si bien la sobreparametrización —el uso de un número de parámetros que excede cierto umbral— ha demostrado en el aprendizaje automático clásico y en algunos contextos cuánticos mejorar la convergencia y evitar los llanos estériles (barren plateaus), a menudo requiere profundidades de circuito que exceden las capacidades de NISQ. Este trabajo investiga si la sobreparametrización es tanto suficiente como necesaria para obtener soluciones de alta probabilidad para problemas de optimización combinatoria utilizando el Algoritmo de Optimización Cuántica Aproximada (QAOA).

Metodología
Los autores definen la sobreparametrización mediante el concepto de Dimensión Cuántica Efectiva (EQD), que cuantifica la expresividad de un circuito variacional basándose en el rango de la matriz de Información de Fisher Cuántica (QFI). Un circuito se considera sobreparametrizado cuando el aumento en el número de parámetros (profundidad) ya no incrementa la EQD.

El estudio se centra en dos problemas representativos de optimización combinatoria NP-duros:

1. MAX-CUT: Investigado en grafos 2-regulares (anillos de desacuerdos), grafos $k$-regulares y grafos aleatorios no ponderados.
2. MAX-2-SAT: Investigado en instancias aleatorias con densidades de cláusulas variables.

Para cada problema, los autores comparan la profundidad de sobreparametrización ($p_c$, donde la EQD se satura) frente a la profundidad óptima ($p^*$, la profundidad mínima requerida para alcanzar una solución dentro de una tolerancia de error de energía específica $\epsilon$). Emplean simulaciones numéricas con estrategias heurísticas por capas e inicializaciones aleatorias de parámetros para rastrear los errores de energía y las probabilidades de éxito a través de diferentes profundidades de circuito.

Contribuciones Claves y Resultados

• MAX-CUT en Grafos 2-Regulares:

  • Los autores proporcionan una prueba analítica de que para un número par de cúbits $n$, la profundidad óptima de QAOA escala como $p^* = \lfloor n/2 \rfloor$.
  • Los resultados numéricos confirman que la profundidad de sobreparametrización $p_c$ coincide exactamente con esta profundidad óptima ($p_c = p^*$) para sistemas de hasta $n=20$.
  • Conclusión: Para esta clase específica de problemas, la sobreparametrización es tanto suficiente como necesaria para encontrar soluciones con alta probabilidad.

• MAX-CUT en Grafos Generales (Regulares y Aleatorios):

  • El análisis numérico muestra que, para la mayoría de las instancias, la solución óptima se encuentra exactamente en o en las inmediaciones de la profundidad de sobreparametrización.
  • La probabilidad de éxito de encontrar una solución exhibe un aumento abrupto al transicionar del régimen subparametrizado al régimen sobreparametrizado.
  • Conclusión: La sobreparametrización es suficiente para el éxito de alta probabilidad. Aunque no es estrictamente necesaria para cada instancia individual, es estadísticamente necesaria para la fracción dominante de las instancias.

• MAX-2-SAT:

  • En marcado contraste con MAX-CUT, la mayoría de las instancias de MAX-2-SAT se resuelven bien dentro del régimen subparametrizado ($p/p_c \ll la 1$).
  • Para $n=7$, aproximadamente el 85% de las instancias se resolvieron con profundidades de circuito tan bajas como la mitad de la profundidad de sobreparametrización.
  • La profundidad óptima escala como $p^* \sim \sqrt{2^n}$, mientras que la profundidad de sobreparametrización escala como $p_c \sim 2^n$. Por consiguiente, la relación $p^*/p_c$ disminuye exponencialmente con el tamaño del problema.
  • Conclusión: La sobreparametrización no es necesaria para resolver instancias de MAX-2-SAT; se logran altas probabilidades de éxito con circuitos significativamente más superficiales.

Significancia y Reivindicaciones
El artículo sostiene que la relación entre la sobreparametrización y la profundidad óptima del circuito es dependiente del problema.

• Para MAX-CUT, la sobreparametrización actúa como un umbral crítico; la profundidad requerida para saturar la expresividad del circuito (EQD) se alinea con la profundidad requerida para resolver el problema.
• Para MAX-2-SAT, los resultados resaltan el potencial de QAOA en el régimen subparametrizado. Dado que estos problemas pueden resolverse con circuitos mucho más superficiales que la profundidad de sobreparametrización, el QAOA puede ser más viable para los dispositivos NISQ actuales de lo que se sugería anteriormente en estudios centrados únicamente en regímenes sobreparametrizados.

Los autores enfatizan que, si bien la sobreparametrización garantiza la convergencia en ciertos marcos teóricos, no es un requisito universal para todos los problemas combinatorios. Este hallazgo sugiere que, para clases de problemas específicas como MAX-2-SAT, se pueden encontrar soluciones eficientes en recursos sin necesidad de los circuitos profundos que típicamente inducen problemas de ruido y entrenabilidad (como los llanos estériles) en el hardware de corto plazo. Sin embargo, los autores también señalan que, incluso en el régimen subparametrizado, las limitaciones de entrenabilidad como los llanos estériles aún pueden persistir para tamaños de problema grandes.