El quantum annealing es un modelo de computación cuántica diferente a todo lo demás en este sitio. No hay circuito, no hay puertas, no hay Grover ni algoritmo de Shor corriendo en el hardware. Un annealer resuelve exactamente un tipo de problema, optimización, codificando el problema directamente en la física del hardware y dejando que el sistema se asiente en una respuesta de baja energía.
Esta guía formula el mismo problema de Max-Cut de nuestro tutorial de QAOA como un problema de annealing, lo resuelve gratis con el Ocean SDK de D-Wave, y cubre el error práctico que casi todo el mundo comete al pasar de un ejemplo de juguete a hardware real.
La idea física
Un problema de optimización se mapea sobre un sistema de qubits de modo que la configuración de menor energía del sistema, su estado fundamental, corresponda a la mejor solución. Los qubits comienzan en un estado fácil de preparar y evolucionan lentamente hacia el perfil energético del problema. El teorema adiabático es lo que hace que esto funcione: un sistema cuántico que empieza en su estado fundamental permanece en el estado fundamental a lo largo de la evolución, siempre que la evolución sea suficientemente lenta en relación con las brechas de energía del sistema. Al leer los qubits al final, se obtiene una solución de baja energía, con suerte óptima.
Esto difiere de la computación basada en puertas de una forma fundamental. Una QPU basada en puertas ejecuta una secuencia arbitraria de operaciones que tú especificas. Un annealer ejecuta un único proceso fijo, relajándose físicamente hacia un mínimo, y tu única influencia es cómo se codifica el problema en ese perfil energético.
Formulando Max-Cut como un QUBO
Los annealers resuelven problemas expresados como un QUBO (Quadratic Unconstrained Binary Optimization): minimizar una expresión de variables binarias x_i ∈ {0, 1} con solo términos lineales y cuadráticos por pares, sin interacciones de orden superior.
Para Max-Cut, cada arista (i, j) contribuye 2·x_i·x_j − x_i − x_j al objetivo. Repasa los cuatro casos: cuando x_i y x_j coinciden (ambos en el mismo lado), este término es 0. Cuando difieren (la arista está cortada), el término es −1. Minimizar la suma sobre todas las aristas maximiza por tanto el número de aristas cortadas, exactamente el objetivo de Max-Cut, reformulado como una minimización.
Usando el mismo grafo cíclico de cuatro nodos que la guía de QAOA:
import dimod
from neal import SimulatedAnnealingSampler
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
Q = {}
for i, j in edges:
Q[(i, i)] = Q.get((i, i), 0) - 1
Q[(j, j)] = Q.get((j, j), 0) - 1
Q[(i, j)] = Q.get((i, j), 0) + 2
bqm = dimod.BinaryQuadraticModel.from_qubo(Q)
Cada arista de este grafo se corta simultáneamente, el grafo es bipartito: {0, 2} contra {1, 3}, así que la energía del estado fundamental resulta ser exactamente −4, una contribución de −1 por arista. Este número surge directamente de la construcción del QUBO, no de haber ejecutado nada todavía, y este es el objetivo que el sampler de abajo intenta alcanzar.
Resolviendo esto gratis con simulated annealing
El Ocean SDK de D-Wave incluye neal, un sampler clásico de simulated annealing que corre enteramente en tu propia máquina, sin cuenta QPU, sin cola, sin coste. Este es también el primer paso estándar para desarrollar un problema de annealing antes de tocar hardware real, el mismo papel que AerSimulator juega para los circuitos basados en puertas en otras partes de este sitio.
sampler = SimulatedAnnealingSampler()
sampleset = sampler.sample(bqm, num_reads=1000)
best = sampleset.first
print(best.sample, best.energy)
num_reads=1000 ejecuta el proceso de annealing 1.000 veces de forma independiente y guarda cada resultado, ya que tanto el annealing simulado como el cuántico son heurísticos: ninguna ejecución individual garantiza aterrizar en el estado fundamental, así que un lote de lecturas y el resultado de menor energía entre ellas es el patrón estándar. Para este grafo, se espera que best.energy se sitúe en −4, con best.sample mostrando una de las dos biparticiones equivalentes, {0, 2} en un lado y {1, 3} en el otro, o al revés. Ambas son válidas: Max-Cut no tiene noción de qué lado va "primero", así que esto es una simetría genuina del problema, no un error del sampler.
El error: ignorar el embedding
Todo lo anterior corre sobre un annealer simulado clásico, que no tiene límites de conectividad: cualquier variable interactúa libremente con cualquier otra. El hardware real de D-Wave funciona de forma distinta. Los qubits físicos se sitúan sobre una topología fija y dispersa (Pegasus o Zephyr, según la generación), y la mayoría de los pares de qubits simplemente no están conectados directamente.
Para colocar un problema donde la variable i necesita interactuar con la variable j pero ningún par de qubits físicos ofrece esta conexión, el paso de minor embedding de Ocean encadena varios qubits físicos para que actúen como una sola variable lógica. Esto es automático, EmbeddingComposite de dwave-system se encarga del proceso, pero el proceso no es gratuito: las cadenas necesitan qubits adicionales, y una cadena a veces "se rompe", los qubits físicos que deberían coincidir terminan en desacuerdo tras el annealing, corrompiendo silenciosamente la lectura de esa variable. Los problemas más grandes o densos necesitan cadenas más largas, que se rompen con más frecuencia, y los problemas suficientemente densos eventualmente dejan de poder incrustarse en un chip dado. Esta es la sorpresa más común para cualquiera que traslada por primera vez un problema de simulated annealing que funcionaba a hardware real: el algoritmo no empeoró, la conectividad física del chip se convirtió en el cuello de botella.
Lo que el annealing no hace
Un annealer no ejecuta la búsqueda de Grover, no ejecuta la factorización de Shor, y no tiene ninguna noción general de circuito. Sus qubits no son directamente comparables a los qubits basados en puertas: los sistemas de D-Wave superan los 5.000 qubits, muchos más que cualquier QPU basada en puertas, pero esta cifra describe la capacidad de optimización sobre la clase de problemas QUBO/Ising específicamente, no potencia computacional general. Si el annealing ofrece una ventaja real de velocidad frente a las mejores heurísticas de optimización clásicas en problemas prácticos sigue siendo genuinamente objeto de debate en la literatura y parece depender mucho de la estructura específica del problema, no algo que se deba asumir por defecto.
Ejecutar en hardware real de D-Wave
Cambia el sampler y el resto del código se mantiene idéntico:
from dwave.system import DWaveSampler, EmbeddingComposite
sampler = EmbeddingComposite(DWaveSampler())
sampleset = sampler.sample(bqm, num_reads=1000)
El servicio en la nube Leap de D-Wave ofrece una cuota mensual gratuita de tiempo de QPU exactamente para este tipo de experimentación, el equivalente en annealing al nivel gratuito de IBM Quantum para hardware basado en puertas. EmbeddingComposite maneja el paso de minor embedding automáticamente, pero revisa el sampleset.info devuelto para ver estadísticas de rotura de cadenas antes de confiar en un resultado más allá de un problema de juguete modesto.
Próximos pasos
- Tutorial de QAOA: el enfoque basado en puertas para el mismo problema de Max-Cut
- Entrada del glosario sobre Quantum Annealing: el concepto en breve
- La puerta de qubit de erasure de doble raíl de D-Wave: el movimiento de D-Wave hacia hardware basado en puertas junto a su línea de annealing
- Glosario: QAOA, ventaja cuántica y el resto del vocabulario