QAOA 2026: Optimización Cuántica Aproximada Explicada

📅 Articulo actualizado en dos mil veintiseis

📑 Índice de contenidos

📅 Articulo actualizado en dos mil veintiseis

📑 Índice de contenidos

📅 Última actualización: marzo de 2026. Contenido revisado y verificado.

La optimización combinatoria: un problema universal

Los problemas de optimización combinatoria están por todas partes. Una empresa de logística necesita encontrar las rutas más eficientes para su flota de camiones. Un banco quiere construir la cartera de inversión que maximice el rendimiento ajustado al riesgo. Una aerolínea debe asignar tripulaciones a vuelos cumpliendo docenas de restricciones laborales. Un fabricante de semiconductores tiene que planificar la secuencia óptima de fabricación de miles de chips diferentes.

Lo que todos estos problemas tienen en común es que el número de soluciones posibles crece exponencialmente con el tamaño del problema. Para una ruta con veinte ciudades, hay más de un trillón de recorridos posibles. Para una cartera con cien activos donde cada uno puede incluirse o no, hay 2^100 combinaciones, más que átomos en el universo observable.

Los algoritmos clásicos han desarrollado heurísticas poderosas para estos problemas, como el recocido simulado, los algoritmos genéticos y la programación lineal entera. Estos métodos funcionan bien en la práctica para muchos problemas, pero no garantizan encontrar la solución óptima y pueden quedar atrapados en mínimos locales.

La computación cuántica ofrece una vía alternativa para explorar estos espacios exponenciales. QAOA utiliza la superposición cuántica para evaluar muchas soluciones simultáneamente y el entrelazamiento para crear correlaciones entre variables que guían la búsqueda hacia soluciones de alta calidad.

La idea central de QAOA: alternar y optimizar

QAOA fue propuesto por Edward Farhi, Jeffrey Goldstone y Sam Gutmann del MIT en 2014. La idea central es elegantemente simple: construir un circuito cuántico que alterna entre dos tipos de operaciones, una que codifica la función objetivo del problema y otra que mezcla las amplitudes entre soluciones, y luego usar un optimizador clásico para encontrar la mejor combinación de parámetros.

El primer operador, llamado operador de problema u operador de fase, aplica una fase a cada estado proporcional al valor de la función objetivo para esa solución. Las soluciones buenas, con valores bajos de la función de coste, reciben fases diferentes a las soluciones malas. Este operador codifica toda la información del problema en las amplitudes del estado cuántico.

El segundo operador, llamado operador de mezcla o mixer, redistribuye las amplitudes entre los diferentes estados. Típicamente se implementa como una rotación X sobre cada qubit, lo que permite que la amplitud fluya entre soluciones vecinas en el espacio de Hamming. El ángulo de esta rotación es un parámetro libre que el optimizador clásico ajustará.

La alternancia de estos operadores crea un efecto de interferencia constructiva donde las soluciones buenas acumulan amplitud gradualmente, similar al mecanismo de amplificación de amplitud del algoritmo de Grover pero adaptado a problemas de optimización con estructura.

El problema MaxCut como ejemplo canónico

MaxCut es el problema de referencia para QAOA. Dado un grafo con nodos y aristas, el objetivo es dividir los nodos en dos grupos de manera que el número de aristas que cruzan entre los dos grupos sea máximo. Es un problema NP-difícil que aparece en aplicaciones tan diversas como el diseño de circuitos VLSI, la física estadística y las redes sociales.

Para formular MaxCut como QAOA, se asigna un qubit a cada nodo del grafo. El estado cero indica que el nodo está en el grupo A y el estado uno indica que está en el grupo B. La función de coste cuenta el número de aristas que conectan nodos en grupos diferentes, lo que se traduce en un hamiltoniano diagonal que puede implementarse directamente como puertas cuánticas ZZ entre los qubits correspondientes a los extremos de cada arista.

Para un grafo con veinte nodos, el espacio de soluciones tiene 2^20 = un millón de particiones posibles. Un procesador cuántico con veinte qubits puede preparar una superposición de todas ellas simultáneamente y usar QAOA para amplificar las particiones con más aristas cortadas.

El circuito QAOA paso a paso

El circuito QAOA de profundidad p tiene la siguiente estructura. Primero se aplica una puerta Hadamard a cada qubit, creando una superposición uniforme de todas las 2^n soluciones. Luego se repiten p veces los siguientes dos pasos.

En el primer paso de cada capa, se aplica el operador de problema con un ángulo gamma_k, donde k es el índice de la capa. Para MaxCut, esto consiste en aplicar puertas ZZ con ángulo gamma_k entre cada par de qubits conectados por una arista del grafo. El efecto es que cada solución acumula una fase proporcional al número de aristas cortadas multiplicado por gamma_k.

En el segundo paso, se aplica el operador de mezcla con un ángulo beta_k. Esto consiste en aplicar una rotación X con ángulo beta_k a cada qubit. Esta operación redistribuye la amplitud entre soluciones que difieren en el estado de un solo qubit.

Finalmente, se miden todos los qubits para obtener una solución candidata. El proceso se repite muchas veces para estimar la calidad media de las soluciones producidas. El optimizador clásico ajusta los 2p parámetros (gamma_1 a gamma_p y beta_1 a beta_p) para maximizar la calidad media.

El papel de la profundidad p: más capas, mejores soluciones

La profundidad p es el hiperparámetro más importante de QAOA. Con p=1, el circuito tiene solo una capa de operadores y dos parámetros libres. Las soluciones que produce son limitadas: para MaxCut en grafos regulares, QAOA con p=1 garantiza un ratio de aproximación de al menos 0,6924, es decir, corta al menos el 69,24% de las aristas que corta la solución óptima.

A medida que p crece, la calidad de las soluciones mejora. Con p=2 o p=3, QAOA puede superar heurísticas clásicas simples para instancias pequeñas de MaxCut. Con p tendiendo a infinito, QAOA converge al resultado del annealing adiabático, que a su vez converge a la solución óptima. El problema es que cada incremento de p añade profundidad al circuito y más parámetros al optimizador.

En la era NISQ actual, la profundidad de circuito ejecutable está limitada por la decoherencia y los errores de puerta. Los procesadores actuales pueden ejecutar QAOA con p entre tres y diez de forma fiable, dependiendo del número de qubits y la fidelidad del hardware. Para muchos problemas prácticos, esto no es suficiente para superar las mejores heurísticas clásicas.

Tabla: QAOA vs VQE vs annealing cuántico

Aplicaciones industriales de QAOA

Las aplicaciones industriales de QAOA se centran en problemas donde la optimización combinatoria tiene un impacto directo en el resultado empresarial. La logística es quizás el sector más prometedor: optimizar las rutas de una flota de vehículos, la asignación de productos a almacenes o la secuencia de operaciones en una cadena de producción son problemas que cuestan millones de euros cuando se resuelven subóptimamente.

En finanzas, la optimización de carteras bajo restricciones realistas es un problema NP-difícil que se aborda típicamente con relajaciones y heurísticas. QAOA podría encontrar carteras óptimas que los métodos clásicos no alcanzan, mejorando los rendimientos ajustados al riesgo. Empresas como JP Morgan, Goldman Sachs y Multiverse Computing están explorando activamente esta aplicación.

Las telecomunicaciones ofrecen otro campo rico: la asignación de frecuencias a antenas de telefonía móvil, el enrutamiento de tráfico de red y la planificación de recursos en redes 5G son problemas de optimización combinatoria de gran escala donde mejoras del uno o dos por ciento se traducen en millones de euros de ahorro o aumento de capacidad.

La industria farmacéutica puede usar QAOA para optimizar el diseño de ensayos clínicos, la planificación de la producción de medicamentos y la selección de candidatos a fármacos de entre bibliotecas combinatorias masivas. Estas aplicaciones complementan el uso de VQE para la simulación molecular directa.

El debate sobre la ventaja cuántica de QAOA

La cuestión de si QAOA puede ofrecer ventaja cuántica sobre los mejores algoritmos clásicos es uno de los debates más activos en informática cuántica. Los argumentos a favor y en contra son sofisticados y la respuesta depende crucialmente del tipo de problema y la profundidad del circuito.

A favor de QAOA, hay resultados teóricos que muestran que para ciertos problemas en grafos aleatorios, QAOA con p suficientemente alto puede superar las mejores heurísticas clásicas conocidas. Además, la estructura de QAOA tiene conexiones profundas con la física de sistemas cuánticos de muchos cuerpos, sugiriendo que podría explotar efectos cuánticos que los algoritmos clásicos no pueden replicar eficientemente.

En contra, estudios numéricos a gran escala han mostrado que para p bajo (uno a tres) y problemas de tamaño moderado, QAOA a menudo es igualado o superado por heurísticas clásicas como el recocido simulado con schedule optimizado o los algoritmos de Goemans-Williamson para MaxCut. Además, el overhead cuántico, incluyendo el ruido del hardware, la necesidad de múltiples ejecuciones y la optimización clásica de parámetros, reduce la ventaja efectiva.

La posición de consenso actual es que QAOA con profundidad baja en hardware NISQ probablemente no ofrecerá ventaja práctica sobre los mejores algoritmos clásicos. Pero QAOA con profundidad alta en hardware con corrección de errores podría ser una historia diferente, y la investigación teórica sigue avanzando.

Variantes y mejoras: QAOA+ y Warm-Start QAOA

La comunidad ha desarrollado numerosas variantes de QAOA que intentan mejorar su rendimiento en hardware NISQ. QAOA+ permite que los parámetros gamma y beta varíen por qubit o por arista en lugar de ser uniformes, aumentando la expresividad del circuito a costa de más parámetros a optimizar.

Warm-Start QAOA inicializa el estado cuántico usando la solución de una relajación clásica del problema en lugar de la superposición uniforme. Esto coloca el punto de partida de la búsqueda cuántica más cerca de la solución óptima, reduciendo la profundidad necesaria para encontrar buenas soluciones.

Recursive QAOA aplica el algoritmo en capas: ejecuta QAOA, fija las variables de mayor confianza a sus valores más probables, y repite con el problema reducido. Esta estrategia reduce progresivamente el tamaño del problema, permitiendo abordar instancias más grandes que las que el procesador cuántico podría manejar directamente.

Multi-angle QAOA y Grover-enhanced QAOA combinan las ideas de QAOA con la amplificación de amplitud de Grover para obtener mejores garantías de aproximación. Estas variantes son teóricamente más potentes pero requieren circuitos más profundos.

Estado actual y perspectivas futuras

QAOA ha sido ejecutado en hardware real de todos los principales fabricantes. IBM ha demostrado QAOA para MaxCut con hasta 127 qubits en su procesador Eagle, aunque con fidelidades limitadas. Google ha explorado QAOA en Sycamore con optimización de paisajes de energía. IonQ ha demostrado QAOA aprovechando la conectividad completa de sus iones para eliminar los SWAPs que penalizan a los superconductores.

El estado actual es que QAOA funciona como se espera teóricamente en hardware real, pero no ha demostrado ventaja práctica sobre los algoritmos clásicos para ningún problema real. Los resultados experimentales son consistentes con las simulaciones clásicas, lo que valida la implementación pero no prueba utilidad superior.

Las perspectivas futuras dependen de dos factores. Primero, la mejora del hardware para permitir circuitos más profundos con mayor fidelidad, lo que permitirá ejecutar QAOA con p más alto. Segundo, los avances teóricos en la comprensión de qué tipos de problemas y qué estructuras de grafo son más favorables para QAOA.

Para quienes se forman en computación cuántica, QAOA es un algoritmo fundamental que conecta la teoría de la complejidad computacional con la física cuántica y las aplicaciones prácticas. Dominarlo abre puertas tanto en la investigación académica como en la consultoría para empresas que exploran la optimización cuántica.

Preguntas frecuentes

¿Qué es QAOA?

Un algoritmo híbrido cuántico-clásico para optimización combinatoria que alterna operadores de problema y de mezcla, con parámetros ajustados por un optimizador clásico.

¿Para qué problemas sirve?

MaxCut, planificación de rutas, asignación de recursos, scheduling, optimización de carteras y cualquier problema formulable como minimización de una función de coste binaria.

¿Cuál es la diferencia con VQE?

VQE resuelve problemas de estado fundamental molecular; QAOA resuelve optimización combinatoria clásica. VQE tiene ansätze flexibles; QAOA tiene estructura fija basada en el problema.

¿Ofrece ventaja cuántica?

No demostrada en la práctica. Para profundidad baja, las heurísticas clásicas igualan a QAOA. Para profundidad alta con corrección de errores, la cuestión sigue abierta.

¿Cómo se relaciona con D-Wave?

Ambos resuelven optimización pero con enfoques diferentes: D-Wave usa annealing analógico, QAOA usa puertas cuánticas digitales. QAOA es más flexible y ejecutable en cualquier procesador universal.

Continúa con nuestras guías sobre programar con Qiskit, el quantum machine learning y el futuro de la IA cuántica.

<\!-- wp:html -->

<\!-- /wp:html -->

Otros algoritmos cuánticos clave

• VQE — la otra cara del binomio variacional, especializada en química.
• Grover — algoritmo histórico relacionado con QAOA en cuanto a búsqueda.
• Shor — el algoritmo cuántico más conocido del ecosistema.