QAOA explicado: resolviendo Max-Cut paso a paso

QAOA (Quantum Approximate Optimization Algorithm) es uno de los algoritmos cuánticos de corto plazo con más expectación — y con razón. Es un candidato genuino a la ventaja cuántica en problemas de optimización combinatoria, se ejecuta en el hardware NISQ actual y es lo bastante accesible como para implementarlo en una tarde.

Esta guía construye la canalización completa de QAOA desde cero, usando Max-Cut como problema de ejemplo. Al final entenderás qué hace realmente QAOA, cómo implementarlo y cuándo vale la pena usarlo.

¿Qué es Max-Cut?

Max-Cut es un problema de partición de grafos: dado un grafo, se dividen los nodos en dos grupos (0 y 1) para maximizar el número de aristas que cruzan entre grupos. Es NP-difícil en general, aparece en el diseño de chips VLSI, en la agrupación (clustering) y en el análisis de redes, y se mapea limpiamente sobre el hardware cuántico.

Aquí tienes un grafo sencillo de 4 nodos:

0 --- 1
|   \ |
3 --- 2

El corte máximo de este grafo es 4 (las aristas 0-1, 1-2, 2-3, 3-0 cruzan todas). Nuestro objetivo: encontrar la cadena de bits 0101 o 1010 que logra esto.

La idea de QAOA

QAOA es un algoritmo híbrido variacional. Alterna dos operaciones parametrizadas:

1. Unitaria del problema U_C(γ) — codifica la función de coste (cruces de aristas) como retorno de fase (phase kickback)
2. Unitaria mezcladora U_B(β) — mezcla entre soluciones (rotaciones X)

Con p capas de estas unitarias alternadas, QAOA prepara un estado cuántico cuya medición probablemente sea una buena solución. Un optimizador clásico ajusta los 2p ángulos (γ, β) para maximizar el valor de corte esperado.

Construyendo QAOA con PennyLane

import pennylane as qml
import numpy as np
from scipy.optimize import minimize

# Graph edges
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
n_qubits = 4

dev = qml.device("default.qubit", wires=n_qubits)

def cost_unitary(gamma):
    """Encode the Max-Cut cost into phases."""
    for u, v in edges:
        qml.CNOT(wires=[u, v])
        qml.RZ(2 * gamma, wires=v)
        qml.CNOT(wires=[u, v])

def mixer_unitary(beta):
    """Apply X-rotation mixer to all qubits."""
    for i in range(n_qubits):
        qml.RX(2 * beta, wires=i)

@qml.qnode(dev)
def qaoa_circuit(params, p=1):
    gammas = params[:p]
    betas = params[p:]
    # Start in uniform superposition
    for i in range(n_qubits):
        qml.Hadamard(wires=i)
    # Alternate p layers
    for layer in range(p):
        cost_unitary(gammas[layer])
        mixer_unitary(betas[layer])
    return qml.probs(wires=range(n_qubits))

def expected_cut(params, p=1):
    """Classical cost function: expected number of cut edges."""
    probs = qaoa_circuit(params, p)
    total = 0.0
    for bitstring_idx, prob in enumerate(probs):
        bits = format(bitstring_idx, f'0{n_qubits}b')
        cut = sum(1 for u, v in edges if bits[u] != bits[v])
        total += prob * cut
    return -total  # Minimize negative cut

# Optimize p=1 QAOA
p = 1
init_params = np.random.uniform(0, np.pi, 2 * p)
result = minimize(expected_cut, init_params, method='COBYLA',
                  options={'maxiter': 200})

print(f"Optimized params: {result.x}")
print(f"Expected cut: {-result.fun:.3f} / 4.0 maximum")

Ejecutar esto normalmente alcanza expected_cut ≈ 3.5 con p=1 — el 87,5 % del corte máximo.

Muestreando la mejor solución

Después de la optimización, muestrea el circuito para encontrar las soluciones buenas más probables:

@qml.qnode(dev)
def sample_circuit(params, p=1, shots=1000):
    gammas = params[:p]
    betas = params[p:]
    for i in range(n_qubits):
        qml.Hadamard(wires=i)
    for layer in range(p):
        cost_unitary(gammas[layer])
        mixer_unitary(betas[layer])
    return qml.sample(wires=range(n_qubits))

samples = sample_circuit(result.x, shots=1000)

# Count cut values for each bitstring
from collections import Counter
cut_counts = Counter()
for bits in samples:
    key = ''.join(str(b) for b in bits)
    cut = sum(1 for u, v in edges if bits[u] != bits[v])
    cut_counts[(key, cut)] += 1

# Show top 5 most frequent bitstrings
for (bits, cut), count in sorted(cut_counts.items(), key=lambda x: -x[1])[:5]:
    print(f"{bits}  cut={cut}  frequency={count/10:.1f}%")

Salida esperada:

0101  cut=4  frequency=28.3%
1010  cut=4  frequency=27.1%
0110  cut=3  frequency=8.4%
...

Las soluciones óptimas (0101 y 1010) dominan — QAOA amplificó su probabilidad.

El mismo problema con HLQuantum

El QAOA integrado de HLQuantum te permite saltarte por completo la construcción del circuito:

import hlquantum as hlq

graph = [(0, 1), (1, 2), (2, 3), (3, 0)]

result = hlq.algorithms.qaoa(
    graph=graph,
    problem='max_cut',
    p=2,
    backend='pennylane',
    shots=2000,
)

print(result.best_solution)   # '0101' or '1010'
print(result.cut_value)       # 4
print(result.approximation_ratio)  # ~0.96 for p=2

Cambia de backend con un solo indicador:

# Run on Qiskit Aer
result_qiskit = hlq.algorithms.qaoa(graph=graph, problem='max_cut', p=2, backend='qiskit')

# Run on real IonQ hardware (if you have credits)
result_ionq = hlq.algorithms.qaoa(graph=graph, problem='max_cut', p=2,
                                   backend='ionq', device='aria-1')

Aumentando p para obtener mejores resultados

La razón de aproximación de QAOA mejora con la profundidad p. En p→∞, QAOA resuelve el problema exactamente. En la práctica:

El compromiso: los circuitos más profundos acumulan más ruido en el hardware real. En simuladores, usa p=3 o más. En QPU NISQ, p=1 o p=2 suele ser el límite práctico.

¿Cuándo vale la pena usar QAOA?

Actualmente útil para:

• Evaluar el rendimiento de dispositivos NISQ (QAOA es un circuito de benchmark estándar)
• Investigación académica sobre algoritmos cuánticos variacionales
• Grafos pequeños (menos de 20 nodos) en simuladores

Aún no útil para:

• Optimización en producción sobre hardware real a escala — las heurísticas clásicas (recocido simulado, búsqueda tabú) todavía superan a QAOA en problemas prácticos
• Grafos grandes — la profundidad del circuito escala con la densidad del grafo

La promesa: En el futuro hardware tolerante a fallos con circuitos de gran profundidad, QAOA con un p grande podría proporcionar aceleraciones genuinas para la optimización NP-difícil densa. Los fundamentos teóricos son sólidos; el hardware aún no está a la altura.

Próximos pasos

• Guía del SDK PennyLane — configura PennyLane para más algoritmos variacionales
• Guía de VQE — el algoritmo hermano para química cuántica
• HLQuantum — ejecuta QAOA en cualquier backend con una sola API