¿Qué es QAOA y para qué se usa (y para qué no)?
Estado a: 1 de agosto de 2026. QAOA es el algoritmo más citado en el marketing de optimización cuántica y el más medido en la investigación de optimización cuántica. Esos dos hechos apuntan en direcciones opuestas. Aquí va la definición, para qué sirve de verdad hoy, y qué dice el registro medido.
¿Qué es exactamente QAOA?
El Quantum Approximate Optimization Algorithm (Farhi, Goldstone y Gutmann, arXiv:1411.4028, nov 2014) es una receta híbrida cuántico-clásica para optimización combinatoria — problemas como MaxCut, scheduling o selección de portafolios, donde hay que elegir la mejor configuración entre exponencialmente muchas.
La mecánica, sin mística: se codifica la función de costo como un Hamiltoniano; se prepara una superposición uniforme sobre todos los bitstrings; y se alternan dos operaciones p veces — una capa de costo (ángulo γ) que fasea los estados según qué tan buenos son, y una capa mezcladora (ángulo β) que mueve amplitud entre estados. Se mide y sale un bitstring candidato. Un optimizador clásico fuera del chip ajusta los 2p ángulos para bajar el costo promedio; después se muestrea el circuito ajustado y se guarda el mejor sorteo.
Dos propiedades lo hicieron famoso: corre en circuitos cortos (amigable con NISQ) y tiene un piso demostrable — a p=1 en MaxCut 3-regular garantiza al menos 0,6924× el corte óptimo, y con p→∞ converge al óptimo exacto. La trampa: la garantía que impresiona es asintótica en una profundidad que nadie puede correr, y la profundidad que sí se puede correr tiene una garantía que un algoritmo clásico superó hace décadas.
¿Para qué se usa legítimamente hoy?
Tres usos reales, ninguno es "resolver tu logística":
- Investigación de algoritmos. QAOA es el banco de pruebas estándar para las preguntas sobre circuitos variacionales: fijación de parámetros, paisajes de optimización, respuesta al ruido. Buena parte de lo que el campo sabe de optimización con circuitos cortos se aprendió sobre él.
- Benchmark de hardware. Un circuito QAOA es una carga estructurada, escalable y con salida puntuable — un stress test común para máquinas nuevas. Un uso más cercano a "dinamómetro" que a "camión de reparto".
- Candidato a ventaja futura. Si (y solo si) su escalamiento empírico se sostiene y llega el hardware tolerante a fallos, algunas familias de problemas podrían favorecerlo. Eso es una apuesta de investigación, no una capacidad.
Para lo que no se usa, a agosto de 2026: optimización de producción. No encontramos ningún head-to-head publicado donde QAOA le gane a un solver clásico fuerte y afinado en la misma instancia a escala práctica — ni en portafolios, ni en ruteo, ni en scheduling. Un benchmark de 2025 de optimización de portafolios (arXiv:2509.17876) encontró variantes de QAOA y annealing sin alcanzar a Gurobi, y en varias instancias con desempeño cercano al muestreo aleatorio.
¿Qué dice la mejor evidencia a su favor?
El mejor resultado pro-QAOA publicado es Shaydulin et al., Science Advances (2024): el problema LABS (secuencias binarias de baja autocorrelación — genuinamente duro, con uso real en ingeniería de radar). En simulación sin ruido hasta 40 qubits con parámetros fijos, el tiempo-a-solución escaló así:
| Algoritmo | Escalamiento TTS empírico | Estado |
|---|---|---|
| QAOA (p=12) + quantum minimum finding | 1,21^N | necesita hardware tolerante a fallos que no existe |
| Memetic Tabu (mejor heurística clásica) | 1,34^N | corre hoy en un laptop |
| QAOA solo (p=12) | 1,46^N | pierde contra Memetic Tabu a cualquier N |
| Branch-and-bound (clásico exacto) | 1,73^N | baseline exacto |
Lee la tabla dos veces. En la evidencia publicada más fuerte a favor de QAOA, el QAOA a secas escala peor que la mejor heurística clásica. La ventaja solo aparece al atornillarle quantum minimum finding — una subrutina que exige hardware con corrección de errores que nadie tiene. Los autores son explícitos con todo esto en el paper; hay que leer esas salvedades antes de citar el titular.
¿Por qué todavía no gana?
Cuatro muros independientes, apilados:
- Estructura. A profundidad constante, QAOA es local — cada qubit solo "ve" un vecindario. Bravyi, Kliesch, König y Tang (PRL 2020) probaron que el algoritmo clásico de Goemans-Williamson supera a QAOA a cualquier profundidad constante en ciertas instancias de MaxCut: la localidad más la simetría acotan lo que un circuito corto puede alcanzar.
- Entrenabilidad. Ajustar los ángulos es duro en sí mismo. A profundidades útiles el paisaje se llena de mínimos locales de baja calidad en cantidad superpolinomial; la inicialización aleatoria "está condenada a fallar más allá de n pequeño" (arXiv:2402.10188, 2024). Se necesitan buenas conjeturas de parámetros solo para empezar.
- Caudal. Aun donde la calidad de solución pudiera competir, el reloj manda. Para MaxCut en grafos 3-regulares, Lykov et al. (npj QI 2023) estiman que QAOA necesita p>11 y un muestreo de ~10 kHz para rozar a heurísticas clásicas que ya devuelven soluciones de alta calidad en tiempo lineal — mientras las máquinas típicas muestrean por debajo, y la tasa requerida crece con el tamaño del problema.
- El registro medido. Donde alguien corre el head-to-head en las mismas instancias, gana el clásico — ver el benchmark de portafolios de arriba y nuestro veredicto de ruteo.
¿Qué muestran nuestras propias corridas?
Nuestro veredicto sellado V-0012 (selección de portafolios): QAOA a p=2 contra CP-SAT de Google, 20 corridas a n=12/16/20 activos, mismas instancias, mismas reglas de presupuesto. CP-SAT devolvió el óptimo probado 20/20; QAOA quedó 25–48% lejos del óptimo, sin tendencia de mejora al crecer n. Nota de honestidad que juega en nuestra contra: nuestras corridas cuánticas fueron simulaciones sin ruido — un escenario que favorece al lado cuántico — y aun así perdió todas. Es una clase de problema chica a escala de juguete; es un dato, no un veredicto universal. Pero está medido — que es más de lo que ofrece la mayoría de los claims sobre QAOA. Método: por qué un baseline clásico débil arruina un benchmark cuántico.
Qué no sabemos
- Si el escalamiento de LABS (1,21^N con QMF) sobrevive al ruido, al sobrecosto de corrección de errores y a N más grandes — se midió en simulación sin ruido hasta 40 qubits con parámetros fijos.
- Si mejores esquemas de transferencia de parámetros o variantes no-locales de QAOA cambian materialmente el panorama de entrenabilidad a escala.
- Dónde quedaría el punto de cruce N* para algún caso de uso de QAOA — nadie ha publicado uno con evidencia, nosotros incluidos.
- Si p puede subirse lo suficiente en hardware real para que la garantía de p→∞ importe alguna vez en la práctica.
Rosetta Q publica veredictos con datos crudos reproducibles. Esto es contenido educativo, no un claim de producto.