⚛️ quantum physics

Evaluating QAOA expectation values can be as hard as counting optimal solutions

Este artículo establece que evaluar los valores de expectativa exactos o exponencialmente precisos para el problema MaxCut en el QAOA a una profundidad $p \geq 2$ es #P-duro, demostrando que la dificultad computacional transiciona de la tractabilidad al conteo de soluciones óptimas en lugar de meramente a la optimización.

Autores originales: Stuart Hadfield

Publicado 2026-08-13

📖 8 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Stuart Hadfield

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina un mundo donde las computadoras no solo procesan números, sino que bailan con las probabilidades. Este es el reino de la computación cuántica, un campo que promete resolver problemas tan enredados y complejos que las supercomputadoras actuales tardarían más que la edad del universo en descifrarlos. En el corazón de este baile se encuentra una rutina popular llamada Algoritmo de Optimización Cuántica Aproximada, o QAOA. Piensa en el QAOA como una búsqueda del tesoro de alta tecnología. Tienes un mapa (un problema) con muchos caminos posibles, y quieres encontrar el camino que te lleve a la mayor cantidad de oro (la mejor solución). La computadora cuántica prepara un estado especial de "superposición" —una mezcla mágica de todos los caminos posibles a la vez— y luego, a través de una serie de pasos llamados "capas" o "profundidad", intenta inclinar las probabilidades para que el mejor camino brille con más fuerza cuando finalmente lo mires.

Para saber si la búsqueda del tesoro va por buen camino, los científicos necesitan verificar el "valor de la esperanza". En lenguaje sencillo, esto es como echar un vistazo rápido al baile de la computadora cuántica para ver qué tan cerca está de encontrar el oro, sin tener que detener realmente el baile para contar cada una de las monedas. Durante mucho tiempo, los investigadores supieron que si el baile tenía un solo paso (profundidad $p=1$ ), verificar este puntaje era fácil, como leer una receta sencilla. Pero, ¿qué sucede cuando el baile se vuelve más complicado, con dos o más pasos? Un estudio reciente de Wang y sus colegas mostró que verificar el puntaje para estos bailes más profundos es increíblemente difícil; tan difícil como resolver la búsqueda del tesoro original misma. Pero, ¿es solo tan difícil como encontrar un buen camino, o es incluso más difícil?

Este artículo, escrito por Stuart Hadfield, se sumerge profundamente en esa pregunta. El autor demuestra que para el QAOA con dos o más capas, verificar el puntaje no es solo tan difícil como encontrar una única mejor solución; es tan difícil como contar cada una de las mejores soluciones que existen. En el mundo de la informática, encontrar una solución es un desafío duro, pero contarlas todas es un monstruo de un tamaño diferente, a menudo considerado incluso más imposible de manejar para las computadoras clásicas. Hadfield muestra que este "monstruo de la cuenta" aparece en el momento en que se añade una segunda capa al algoritmo. El artículo no solo sugiere esto; proporciona una prueba matemática rigurosa, construyendo un tipo específico de grafo de problema que obliga a cualquier computadora que intente calcular el puntaje del QAOA a resolver, esencialmente, el problema de conteo imposible. Esto significa que para estos algoritmos cuánticos más profundos, el acto mismo de verificar qué tan bien lo están haciendo es, en el peor de los casos, una tarea que podría estar fundamentalmente fuera del alcance de las computadoras clásicas, incluso si tenemos una máquina cuántica perfecta para ejecutar el baile.

La búsqueda del tesoro se complica

Desglosemos el truco de magia. El algoritmo QAOA está diseñado para resolver el problema "MaxCut". Imagina un grupo de amigos en una fiesta, y quieres dividir a los amigos en dos equipos (Equipo Rojo y Equipo Azul) para jugar un juego. El objetivo es organizar los equipos de modo que el número máximo de amistades se rompa entre ambos lados. Este es el "MaxCut". Algunas disposiciones son mejores que otras, y encontrar la disposición absoluta es un rompecabezas clásico que se vuelve más difícil a medida que añades más amigos.

El algoritmo QAOA intenta encontrar esta mejor disposición haciendo girar una moneda cuántica. Comienza con todos en una superposición (tanto Rojo como Azul al mismo tiempo) y luego aplica una serie de "giros" (las capas). Cuantos más giros añades, más sofisticado se vuelve el baile. Para ver si el baile está funcionando, los científicos calculan un "valor de la esperanza". Piensa en esto como un "puntaje" que te dice, en promedio, cuántas amistades se rompen en el baile cuántico.

Para un solo giro ( $p=1$ ), calcular este puntaje es fácil. Puedes escribirlo en una servilleta. Pero cuando añades un segundo giro ( $p=2$ ), las cosas se vuelven extrañas. Investigaciones previas mostraron que calcular este puntaje era "NP-duro", lo que significa que era tan difícil como encontrar una sola mejor disposición de equipos. Pero el artículo de Hadfield dice: "Espera, es en realidad peor que eso".

El Monstruo de la Cuenta

El principal descubrimiento de Hadfield es una mejora drástica en nuestra comprensión de la dificultad. Él demuestra que calcular el puntaje para $p \ge 2$ no es solo "NP-duro" (encontrar una solución); es #P-duro.

Para entender la diferencia, imagina que eres un detective.

NP-duro es como si te preguntaran: "¿Puedes encontrar a un sospechoso que cometió el crimen?". Es difícil, pero si tienes suerte o te esfuerzas lo suficiente, podrías encontrar uno.
#P-duro es como si te preguntaran: "¿Cuántos sospechosos en total cometieron el crimen?". Tienes que encontrar a cada uno de ellos y contarlos.

En el mundo de la informática, contar es generalmente considerado mucho más difícil que simplemente encontrar uno. Hadfield muestra que para el QAOA con dos o más capas, las matemáticas necesarias para calcular el puntaje te obligan a contar el número de soluciones perfectas.

El Gadget Mágico

¿Cómo lo demostró? Hadfield construyó un "gadget" ingenioso, que es como una trampa diseñada para atrapar a la computadora. Tomó un problema MaxCut estándar y construyó un grafo gigante y complejo alrededor de él. Este grafo tiene puntos de "anclaje" especiales y bloques de "variables".

El truco está en el diseño. Cuando la computadora cuántica ejecuta su baile en este grafo específico, el puntaje final (el valor de la esperanza) se convierte en una expresión matemática gigante llamada "polinomio de Laurent". Esta expresión es como una larga cadena de términos, cada uno con una potencia diferente de una variable (como $z^1, z^2, z^3...$ ).

Hadfield demostoró que la potencia más alta en esta cadena (el "coeficiente extremo") guarda un secreto. Si puedes calcular el puntaje perfectamente, puedes extraer esta potencia más alta. Y aquí está la clave: el tamaño de ese número específico es directamente proporcional al número total de soluciones perfectas al problema original.

Así que, si pudieras calcular fácilmente el puntaje de QAOA para este grafo, conocerías instantáneamente la respuesta al problema del "monstruo de la cuenta". Dado que se cree que contar es imposible para las computadoras clásicas de manera eficiente, calcular el puntaje de QAOA también debe ser imposible para ellas.

La sorpresa de "Un Solo Borde"

El artículo se vuelve aún más sorprendente. Podrías pensar: "Está bien, calcular el puntaje total es difícil, ¿pero tal vez calcular el puntaje para solo un vínculo específico (un solo borde) sea fácil?".

Hadfield dice que no. Él demuestra que incluso si solo le pides a la computadora cuántica que te diga la correlación entre dos personas específicas (un "correlador de dos cúbits" como $\langle Z_r Z_s \rangle$ ), el problema sigue siendo #P-duro. La dificultad no está solo en el panorama general; está integrada en los detalles más pequeños del algoritmo.

Qué significa esto para el futuro

El artículo traza una línea clara en la arena:

Profundidad $p=1$ : Fácil. Podemos calcular el puntaje de manera eficiente.
Profundidad $p \ge 2$ : Difícil. Calcular el puntaje es tan difícil como contar todas las soluciones óptimas.

Esto tiene enormes implicaciones. Muchos algoritmos modernos utilizan QAOA para entrenar a la máquina, ajustando los "giros" (parámetros) para obtener un mejor puntaje. Si calcular el puntaje es así de difícil, entonces entrenar estos algoritmos en una computadora clásica (para ver cómo lo está haciendo la máquina cuántica) podría ser imposible para circuitos profundos.

El autor también señala que esto no significa que las computadoras cuánticas sean inútiles. De hecho, podría significar que son más útiles. Si una computadora clásica ni siquiera puede verificar el puntaje, tal vez la computadora cuántica sea la única que pueda hacerlo. Sin embargo, el artículo también advierte que esta "dureza" es un escenario del peor de los casos. No significa que cada grafo sea imposible de resolver; solo significa que existen grafos específicos y complicados donde las matemáticas fallan para las computadoras clásicas.

La conclusión

El artículo de Stuart Hadfield es una llamada de atención para la comunidad cuántica. Nos dice que a medida que hacemos el QAOA más poderoso añadiendo más capas, no solo estamos haciendo el problema más difícil de resolver, sino que estamos haciendo que el problema de verificar nuestro trabajo sea exponencialmente más difícil. Hemos pasado de un mundo donde podíamos verificar fácilmente el baile cuántico a un mundo donde verificar el baile requiere resolver un rompecabezas de conteo que podría ser lo más difícil en la informática. Es un recordatorio de que en el reino cuántico, cuanto más profundo vas, más misteriosas se vuelven las matemáticas.

Resumen Técnico: La evaluación de los valores de expectativa de QAOA es #P-hard

Planteamiento del problema
El artículo aborda la complejidad computacional de evaluar los valores de expectativa para el Algoritmo de Optimización Aproximada Cuántica (QAOA) aplicado al problema de MaxCut. Si bien se sabe que la evaluación del valor de expectativa del costo $F_p(G; \gamma, \beta) = \langle \psi_p | C_G | \psi_p \rangle$ es computable eficientemente para una profundidad $p=1$ en grafos arbitrarios, trabajos recientes establecieron que la evaluación exacta se vuelve NP-hard para cualquier profundidad fija $p \ge 2$ . La cuestión central investigada aquí es si la dificultad para $p \ge 2$ se limita a la optimización (encontrar una solución) o si se extiende al conteo (determinar el número de soluciones óptimas). Específicamente, el autor se pregunta si computar estos valores de expectativa es #P-hard, una clase de complejidad generalmente considerada más difícil que NP, que corresponde a la dificultad de contar el número de soluciones a un problema de satisfacción de restricciones.

Metodología
El autor refina el mecanismo de prueba de dureza introducido por Wang et al. [5], el cual utilizó polinomios de Laurent para recuperar el valor del corte máximo a partir del exponente más grande. El enfoque del autor implica los siguientes pasos:

Construcción de grafos (Gadget de conteo balanceado): En lugar de los gadgets asimétricos utilizados en trabajos previos, el autor construye un grafo específico $G(H)$ a partir de un grafo de entrada $H$ . Esta construcción emplea:
- Gadgets de variables: Para cada vértice en $H$ , se crea un grafo bipartito completo balanceado $K_{L,L}$ , donde $L = O(n)$ .
- Aristas sincrónicas: Aristas que conectan los vértices correspondientes en los gadgets $K_{L,L}$ de vértices adyacentes en $H$ para preservar la estructura original del grafo.
- Vértices ancla: Dos vértices universales, $r$ y $s$ , conectados a cada vértice en los gadgets de las variables y entre sí.
  Este proceso asegura que el grafo $G(H)$ tenga un diámetro de 2 y que sus cortes máximos estén rígidamente restringidos: los gadgets $K_{L,L}$ deben ser cortados completamente, y los anclas deben estar en lados opuestos.
Análisis de polinomios de Laurent: El valor de expectativa del costo (o un correlador específico de dos qubits $\langle Z_r Z_s \rangle$ ) se expresa como un polinomio de Laurent en una variable de fase $z = e^{i\phi}$ . El autor analiza los coeficientes de este polinomio.
- Identifica un "coeficiente extremo" correspondiente al exponente de grado máximo $D^*$ .
- A través de un análisis de "suma de caminos reducidos", demuestra que el coeficiente $a_{D^*}$ es no nulo y directamente proporcional al número de cortes máximos del grafo original $H$ , denotado como $|\# \text{MC}(H)|$ .
- Específicamente, $a_{D^*} = \kappa \cdot |\# \text{MC}(H)|$ , donde $\kappa$ es un factor algebraico conocido y no nulo que depende de los ángulos del mezclador (mixer) y el tamaño del grafo.
Reducción mediante interpolación: El autor demuestra que, al consultar el oráculo del valor de expectativa de QAOA en un número polinomial de valores de fase distintos (raíces de la unidad), se puede utilizar la transformada discreta de Fourier inversa para recuperar exactamente los coeficientes de Laurent. Dado que el coeficiente extremo codifica el conteo de cortes máximos, un oráculo capaz de la evaluación exacta (o de la evaluación con precisión exponencial) permite la recuperación de este conteo, estableciendo así una reducción de Turing determinista en tiempo polinomial desde el problema #P-hard de contar cortes máximos hacia el problema de evaluar el valor de expectativa de QAOA.

Contribuciones clave y resultados

Dicotomía de complejidad: El artículo establece una transición de complejidad nítida para los valores de expectativa de QAOA en grafos simples no ponderados:
- $p=1$ : El problema está en FP (computable en tiempo polinomial).
- $p \ge 2$ : El problema es #P-hard bajo reducciones de Turing deterministas de tiempo polinomial.
Conteo vs. Optimización: A diferencia del resultado anterior de NP-hardness que recuperaba el valor del corte máximo, este trabajo muestra que la evaluación del valor de expectativa permite recuperar el número de cortes máximos. Esto eleva la dificultad de la optimización al conteo.
Dureza restringida: La #P-hardness se mantiene incluso bajo restricciones significativas:
- Se aplica a la evaluación de un único correlador de dos qubits designado $\langle Z_r Z_s \rangle$ en lugar de la función de costo global.
- Se mantiene para un conjunto altamente restringido de parámetros del algoritmo (ángulos de mezclador fijos $\beta_1 = \arctan(1/2)$ , $\beta_2 = \pi/4$ , y ángulos de costo vinculados $\gamma_1 = \gamma_2 = \phi$ ).
- Se aplica a grafos con diámetro 2 (aunque estos grafos tienen un grado alto).
Derivadas y Hessianas: El autor extiende estos resultados para mostrar que computar gradientes y hessianas exactas de la función de costo de QAOA con respecto a los parámetros también es #P-hard.
Precisión exponencial: La dureza se extiende al problema de aproximar el valor de expectativa con un error aditivo exponencialmente pequeño ( $2^{-\alpha N}$ ), ya que esta precisión es suficiente para distinguir el coeficiente extremo y recuperar el conteo entero mediante redondeo.

Significancia y afirmaciones
El artículo afirma proporcionar una "clasificación de complejidad exacta y limpia" para los valores de expectativa de QAOA. La principal significancia radica en demostrar que la transición de $p=1$ a $p=2$ no es meramente un cambio de la tractabilidad a la dureza de optimización (NP-hard), sino un cambio a la dureza de conteo (#P-hard).

El autor enfatiza que sus resultados son declaraciones de peor caso respecto a familias específicas de grafos de alto grado y no implican que evaluar QAOA sea difícil para todos los grafos o instancias típicas. Señala que la dureza depende de la evaluación exacta o de precisión exponencial; no afirma dureza para regímenes de error aditivo constante o polinomialmente pequeño, que son más relevantes para los dispositivos actuales de escala intermedia con ruido (NISQ).

Además, el artículo distingue sus hallazgos de los resultados de supremacía cuántica relacionados con el muestreo. Mientras que el muestreo de las salidas de QAOA a $p=1$ ya es clásicamente difícil bajo ciertas condiciones, este trabajo muestra que evaluar el valor de expectativa a $p=2$ es suficiente para resolver problemas de conteo #P-hard. El autor concluye que sus resultados implican que, si se pudiera evaluar eficientemente los valores de expectativa de QAOA con precisión exponencial, la jerarquía polinomial colapsaría a su nivel más bajo ($P=PH$). Esto tiene implicaciones para los algoritmos híbridos que dependen del procesamiento clásico de valores de expectativa cuánticos, sugiriendo que tales enfoques pueden enfrentar barreras computacionales fundamentales en el peor de los casos si se requiere alta precisión.