A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

Resumen Técnico: Una Heurística de Configuración de Parámetros para el Ansatz de Operadores Alternantes Cuánticos

Planteamiento del Problema
El Ansatz de Operadores Alternantes Cuánticos (QAOA) es un destacado algoritmo cuántico parametrizado para resolver problemas de optimización combinatoria. Sin embargo, encontrar parámetros ($\vec{\gamma}, \vec{\beta}$) de alta calidad de manera eficiente sigue siendo un desafío práctico significativo. El proceso de configuración de parámetros implica típicamente un bucle variacional cuántico-clásico donde un optimizador clásico actualiza los parámetros basándose en el valor de la esperanza del valor de una función de costo evaluada en hardware cuántico o mediante una costosa simulación clásica. Este proceso enfrenta dificultades tales como mesetas estériles (barren plateaus), numerosos óptimos locales y la escala exponencial de los recursos requeridos para la evaluación exacta de los valores de esperanza de las funciones de costo a medida que aumenta el número de cúbits ($n$) o la profundidad del circuito ($p$). Además, los dispositivos actuales de escala intermedia con ruido (NISQ) exacerban estos desafíos debido al ruido y a los errores de muestreo finito.

Metodología
Los autores proponen una "Heurística Homogénea para la Configuración de Parámetros", una estrategia clásica diseñada para reemplazar la costosa evaluación cuántica o clásica del valor de esperanza de la función de costo con un modelo clásico eficiente. El núcleo de este enfoque se basa en el concepto de Homogeneidad Perfecta.

1. Homogeneidad Perfecta: Se define como una propiedad del estado donde todas las cadenas de bits $x$ que comparten el mismo valor de costo $c(x)$ poseen amplitudes cuánticas idénticas. Si bien esta propiedad se cumple exactamente solo para problemas simétricos específicos o en el límite de parámetros pequeños, las observaciones empíricas sugieren altos solapamientos entre los estados QAOA y los estados perfectamente homogéneos en diversos entornos.
2. Proxy Homogéneo Clásico: Los autores construyen un modelo clásico, denominado "Proxy Homogéneo Clásico", que impone la Homogeneidad Perfecta por suposición. En este proxy, el estado no se describe mediante $2^n$ amplitudes, sino por un conjunto de amplitudes $Q(c)$ correspondientes a cada valor de costo único $c$.
   • La evolución se modela utilizando una perspectiva de "suma de caminos". Los autores reemplazan el conteo exacto de cadenas de bits en una distancia de Hamming específica con una distribución $N(c'; d, c)$ derivada analíticamente que depende únicamente de las clases de costo.
   • Esto permite el cálculo recursivo de las amplitudes $Q_\ell(c)$ para cada capa $\ell$ utilizando la Ec. (5), lo cual escala polinómicamente con el tamaño del problema $n$ y el número de valores de costo distintos $|C|$, siempre que $|C|$ crezca polinómicamente con $n$.
3. El Bucle Heurístico: El procedimiento de configuración de parámetros (Algoritmo 3) utiliza este proxy como la subrutina interna. Un optimizador clásico busca parámetros $(\vec{\gamma}, \vec{\beta})$ que minimicen la "función objetivo de parámetros homogéneos" (una estimación del valor de esperanza del costo derivada del proxy). Una vez que se encuentran los parámetros óptimos para el proxy, estos se aplican directamente al circuito QAOA real.

El artículo demuestra cómo computar las distribuciones necesarias ($N(c'; d, c)$ y probabilidades de costo $P(c')$) para clases específicas de Problemas de Satisfacción de Restricciones (CSP) con cláusulas extraídas aleatoriamente, incluyendo k-SAT aleatorio, MaxCut en grafos de Erdős-Rényi y Max-k-XOR.

Contribuciones Clave

• Definición de la Homogeneidad Perfecta y del Proxy: Los autores formalizan la condición de Homogeneidad Perfecta y definen un Proxy Homogéneo Clásico que proporciona tanto descripciones de estado como valores de esperanza de manera eficiente.
• Escalabilidad Polinómica: El método propuesto permite la computación clásica de los parámetros del proxy en un tiempo que escala polinómicamente con respecto tanto al número de variables $n$ como a la profundidad $p$, evitando el crecimiento exponencial de recursos asociado con la simulación exacta del vector de estado.
• Generalización a Clases de CSP: El artículo proporciona derivaciones explícitas para las distribuciones del proxy para cuatro clases de CSP aleatorios, mostrando que el proxy puede describir toda una clase de problemas en lugar de una única instancia.
• Marco Heurístico: Los autores introducen un flujo de trabajo completo (Algoritmo 3) que integra este proxy en los bucles estándar de optimización de parámetros, manteniendo la flexibilidad en la elección de los esquemas de actualización de parámetros.

Resultados
Los autores evaluaron numéricamente la heurística en problemas MaxCut sobre grafos aleatorios de Erdős-Rényi no ponderados ($G(n, p_e)$):

• Baja Profundidad ($p \leq 3$): Para grafos con $n=20$, la heurística encontró parámetros que produjeron ratios de aproximación comparables a los obtenidos mediante la estrategia de "transferencia de parámetros" (transferir parámetros optimizados globalmente desde instancias más pequeñas). La diferencia en el rendimiento no fue estadísticamente significativa, aunque la heurística mostró un rendimiento promedio ligeramente superior en algunos casos.
• Alta Profundidad ($p \leq 20$): Para profundidades de hasta $p=20$, la heurística identificó con éxito parámetros que producen ratios de aproximación que aumentan monótonamente a medida que la profundidad aumenta. En contraste, una estrategia utilizando la transferencia de parámetros con recursos clásicos idénticos falló en converger.
• Precisión del Proxy: El análisis numérico mostró que el proxy mantiene grandes solapamientos con las simulaciones completas de vectores de estado, particularmente para programas de parámetros de rampa lineal y en regímenes donde el parámetro $\gamma$ es pequeño. Se encontró que las distribuciones analíticas utilizadas en el proxy correlacionan altamente con los promedios empíricos sobre instancias de grafos aleatorios.

Significancia y Reivindicaciones
El artículo afirma que la Heurística Homogénea ofrece una vía práctica para la configuración de parámetros en regímenes que son actualmente intratables para los dispositivos NISQ debido al ruido y para los métodos clásicos debido a la escala exponencial. Al reemplazar la costosa evaluación del valor de esperanza por un proxy clásico de tiempo polinómico, el método permite la exploración de circuitos QAOA más profundos (por ejemplo, $p=20$) donde las estrategias previas fallan en converger.

Los autores enfatizan que, si bien la heurística no garantiza parámetros óptimos para cada instancia específica, proporciona una estrategia robusta y de clase general que rinde competitivamente con métodos establecidos a profundidades bajas y los supera a profundidades altas. El trabajo sugiere que el supuesto de la Homogeneidad Perfecta, aunque no es universalmente exacto, sirve como una aproximación suficientemente precisa para guiar la optimización de parámetros en muchos entornos de optimización combinatoria, particularmente aquellos que involucran restricciones aleatorias. Los autores concluyen delineando direcciones futuras, como la incorporación de información específica de la instancia en el proxy y la extensión del enfoque a otros algoritmos cuánticos variacionales como el Eigensolver Cuántico Variacional (VQE).