Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

Resumen Técnico: Coste de tolerancia a fallos de QAOA de baja profundidad en problemas de optimización casi simétricos

Planteamiento del problema
Montanaro y Zhou [1] demostraron que los circuitos de Algoritmo de Optimización Aproximada Cuántica (QAOA) de profundidad uno pueden hallar la solución plantada de ciertos Problemas de Satisfacción de Restricciones (CSP) casi simétricos con una probabilidad constante $\Omega(1)$. En contraste, las realizaciones explícitas de estos problemas exhiben un aparente escalamiento de tiempo exponencial para algoritmos clásicos robustos. Si bien esto sugiere una aceleración exponencial empírica, los requisitos de recursos para implementar estos circuitos en computadoras cuánticas de tolerancia a fallos tempranas siguen siendo inciertos. Los Hamiltonianos de coste para estos problemas contienen $\Theta(n^\ell)$ cláusulas (donde $\ell \ge 5$), lo que implica un conteo de puertas no-Clifford que escala como $\tilde{O}(n^\ell)$ al ser compilados mediante la síntesis estándar de Clifford+$T$. Este escalamiento sitúa a los tamaños de problema relevantes fuera del alcance del hardware de tolerancia a fallos de corto plazo.

Metodología
Los autores analizan el coste de recursos de tolerancia a fallos de los circuitos QAOA de profundidad uno aplicados a estas instancias casi simétricas, centrándose específicamente en la síntesis de la capa del separador de fase. El análisis procede a través de tres pasos principales:

1. Emparejamiento de fase y escalamiento del ángulo: Los autores revisan la condición de emparejamiento de fase requerida para una probabilidad de éxito constante. Para funciones de coste simétricas bajo permutaciones de variables respecto a una solución plantada, el ángulo del separador de fase $\gamma$ debe escalar como $\gamma = \Theta(n^{1-\ell})$ para asegurar la interferencia constructiva de las capas Hamming dominantes.
2. Síntesis de ángulos pequeños: Aprovechando el hecho de que $\gamma$ se reduce con el tamaño del sistema, los autores aplican técnicas de síntesis de rotación Clifford+$T$ de ángulos pequeños (específicamente las de Bothe et al. [9]). Utilizan formulaciones de cuasiprobabilidad y mezcla de probabilidad donde las rotaciones de ángulos pequeños se aproximan por la identidad con alta probabilidad, y solo una pequeña fracción de las rotaciones requiere síntesis no-Clifford.
3. Compilación explícita de cláusulas y análisis de fuga: Los autores transicionan del modelo de oráculo de valor (donde solo se consultan los valores de coste $C(x)$) a un modelo de lista de cláusulas explícitas requerido para la compilación del circuito. Analizan los coeficientes de Fourier de la función de coste derivada de la lista de cláusulas explícita para determinar si el proceso de compilación revela inadvertidamente la solución.
4. Construcción de instancias engañosas: Para probar la robustez de la aceleración frente a ataques clásicos que explotan la estructura explícita, los autores construyen instancias casi simétricas "no plantadas". Estas instancias presentan una capa Hamming óptima exponencialmente grande que contiene un subproblema NP-duro, con un paisaje de coste diseñado para atrapar a los algoritmos de búsqueda local.

Contribuciones clave y resultados

• Escalamiento no-Clifford cuadrático: El resultado principal es que el coste no-Clifford por circuito para QAOA de profundidad uno en estas instancias se reduce a $\tilde{O}(n^2)$, independiente de la localidad de la cláusula $\ell$ y de la tasa de dispersión. Esta reducción ocurre porque la masa de fase total ($m\gamma$, donde $m$ es el número de cláusulas) escala linealmente con $n$, y los costes de la síntesis de ángulos pequeños dependen del cuadrado de esta masa de fase. En consecuencia, los tamaños de problema que antes se consideraban inviables debido al escalamiento $\tilde{O}(n^\ell)$ se vuelven viables en dispositivos tempranos de tolerancia a fallos (ver Fig. 2).
• Fuga clásica en familias plantadas: Para las familias plantadas estudiadas en la Ref. [1], los autores muestran que la lista de cláusulas explícita requerida para la compilación expone la solución plantada. La condición de emparejamiento de fase ($F'(1/2) \neq 0$) fija los signos de los coeficientes de grado uno (campos locales) de la función de coste. Estos signos revelan directamente la solución plantada $s$ mediante un simple escaneo lineal de tiempo clásico de la lista de cláusulas. Por lo tanto, mientras que QAOA tiene éxito con probabilidad constante, la implementación explícita hace que el problema sea clásicamente trivial.
• Existencia de instancias no plantadas duras: Los autores demuestran que el régimen de ángulos pequeños y el escalamiento de coste $\tilde{O}(n^2)$ no dependen de la existencia de una solución plantada. Construyen instancias casi simétricas sin solución plantada donde:
  • El óptimo global reside dentro de una capa Hamming exponencialmente grande.
  • Hallar el óptimo exacto dentro de esa capa es NP-duro.
  • El paisaje de coste es "engañoso", atrapando a los algoritmos de búsqueda local y a los solvers de MaxSAT de propósito general en sectores subóptimos separados por altas barreras de energía.
  • El QAOA de profundidad uno en el ángulo pequeño concentra su salida en la capa óptima con el mismo coste no-Clifford de $\tilde{O}(n^2)$.
  • En estos casos no plantados, los coeficientes de grado uno son uniformes y no revelan la solución, preservando la dureza para los algoritmos clásicos que no explotan la estructura de simetría específica.

Significación
El artículo establece que la aceleración empírica de QAOA de baja profundidad en problemas casi simétricos puede realizarse con significativamente menores recursos de tolerancia a fallos de lo que se suponía anteriormente, específicamente $\tilde{O}(n^2)$ puertas no-Clifford en lugar de $\tilde{O}(n^\ell)$. Esto convierte a estos circuitos de baja profundidad y ángulos pequeños en un objetivo realista para el hardware temprano de tolerancia a fallos.

Sin embargo, los autores señalan modestamente un compromiso crítico: el mecanismo que permite la síntesis de ángulos pequeños (campos locales coherentes) expone simultáneamente la solución a los ataques clásicos en escenarios plantados. La importancia del trabajo radica en identificar un régimen donde QAOA de baja profundidad ofrece una vía eficiente en recursos para la optimización, al tiempo que destaca que las propiedades estructurales específicas que permiten esta eficiencia pueden ser un arma de doble filo. Los autores concluyen que la cuestión central es si este régimen "barato" de ángulos pequeños puede extenderse a circuitos más profundos o estructuras de problemas diferentes donde la solución permanezca oculta para los ataques clásicos de bajo grado, logrando así una verdadera ventaja cuántica que sea tanto tolerante a fallos en costes como resistente a ataques clásicos.