Optimización cuántica · QAP10

Optimización cuántica · Reto QAP10

NTT DATA · Qiskit Fall Fest Lima — asignación cuadrática con métodos clásicos, QAOA (Qiskit) e híbridos.

Crux Q · motor quantum/

Pregunta del reto: ¿hasta dónde ayudan los métodos cuánticos o híbridos a encontrar buenas asignaciones con tiempo y cómputo limitados? Aquí no afirmamos ventaja cuántica: medimos qué funciona, qué no y por qué. Todos los circuitos se simulan en CPU con Qiskit Aer; no se usó hardware cuántico.

Óptimo verificado (N=10)

340

Enumeración de 10! en 4,24 s

Mejor híbrido LNS + QAOA

350

gap 2,9 % · sub-QAP de 9 qubits

Muestras factibles N=4

19 %

QAOA-XY vs 0,45 % con QAOA estándar

Recocido simulado (clásico)

340

media 349,0 en 10 semillas

Contexto · Track abierto: distribución de planta en un CMMS

Crux A.I gestiona el mantenimiento de una planta. Cada orden de trabajo mueve técnicos, herramientas y repuestos entre activos. Proponemos usar QAP10 para decidir en qué bahía de la planta se instala cada uno de 10 activos (por ejemplo, al rediseñar el layout tras una ampliación).

F_ik: traslados de técnicos o repuestos entre los activos i y k por semana (en Crux saldría del historial de órdenes de trabajo).
D_jl: distancia por pasillos entre las bahías j y l. En qap10, D coincide exactamente con la distancia Manhattan en una rejilla de 4 + 4 + 2 bahías (verificado), lo que hace natural esta lectura.
Decisión: una bahía por activo para reducir la distancia total ponderada que recorren los equipos de mantenimiento.

Los datos de qap10 son un benchmark matemático, no mediciones de una planta. Los nombres de activos son ilustrativos. La misma matemática vale para el Track A (vuelos → puertas) o el Track B (rutas eléctricas → estaciones).

Estimación de impacto (supuestos, no mediciones)

Costo esperado de un layout al azar	511,7
Costo óptimo	340
Reducción	171,7 (34 %)
Supuestos: 1 u. de D = 15 m · 48 semanas/año · $0.05/m
Ahorro anual estimado	≈ $6.182

Cálculo: (C_azar − C*) × m/u × semanas × $/m, donde F se lee en traslados por semana. El costo al azar es Σ_i<kF_ik · media(D_j≠l). Validarlo exigiría datos reales de órdenes de trabajo y planos.

Modelo y lectura de datos

Del archivo qap10.mps.gz (linealización tipo Adams-Johnson) se leen 100 variables x_ij y 4.050 variables y = x_ijx_kl. Cada y se enlaza con sus dos x siguiendo sus filas de restricción; el coeficiente de NOBJ da c_ijkl. La matriz c[(i,k),(j,l)] es de rango 1, así que c_ijkl = F_ik·D_jl (escala: min D = 1).

Error de la factorización F·D 0,000
C(perm*) con F, D = suma directa de coeficientes MPS 340 = 340
Óptimo enumerado = C* de referencia 340 = 340
Subinstancia N=3: óptimo = control 24 = 24
Subinstancia N=4: óptimo = control 32 = 32
D simétrica, pares contados una vez (i<k) sí

Asignación óptima en la rejilla de la planta (C = 340) líneas = flujo F entre activos

perm* = [2, 6, 3, 0, 8, 4, 5, 1, 7, 9] (elemento i → ubicación perm[i], índices desde 0).

Etapa 1 · Subinstancias N = 3 y N = 4 (primeras N filas/columnas)

N	Método	Qubits	Mejor costo factible	Fracción factible	P(óptimo)	Puertas 2q	Tiempo
N = 3 · 9 variables QUBO · 6 permutaciones · 2 asignaciones óptimas · control 24 · λ = 33
3	Enumeración exacta (clásico)	—	24	100 %	—	—	0,2 ms
3	Recocido simulado (5 semillas)	—	24 (media 24,0)	100 %	—	—	0,03 s
3	QAOA estándar (RX) p=1 (3 semillas)	9	24	5,6 %	2,10 %	36	0,80 s
3	QAOA estándar (RX) p=2 (3 semillas)	9	24	4,2 %	1,37 %	72	1,60 s
3	QAOA estándar (RX) p=3 (3 semillas)	9	24	4,3 %	1,39 %	108	2,33 s
3	QAOA mezclador XY p=1 (3 semillas)	9	24	39,9 %	17,43 %	48	1,11 s
3	QAOA mezclador XY p=2 (3 semillas)	9	24	43,6 %	23,44 %	84	1,37 s
3	QAOA mezclador XY p=3 (3 semillas)	9	24	35,7 %	21,07 %	120	3,31 s
	Referencia: muestrear al azar (bits uniformes / un 1 por fila)			1,17 % / 22,2 %	0,39 % / 7,41 %
N = 4 · 16 variables QUBO · 24 permutaciones · 2 asignaciones óptimas · control 32 · λ = 67
4	Enumeración exacta (clásico)	—	32	100 %	—	—	0,1 ms
4	Recocido simulado (5 semillas)	—	32 (media 32,0)	100 %	—	—	0,04 s
4	QAOA estándar (RX) p=1 (3 semillas)	16	32	1,0 %	0,10 %	96	4,46 s
4	QAOA estándar (RX) p=2 (3 semillas)	16	38	0,1 %	0,00 %	192	9,66 s
4	QAOA estándar (RX) p=3 (3 semillas)	16	32	0,2 %	0,04 %	288	20,64 s
4	QAOA mezclador XY p=1 (3 semillas)	16	32	19,7 %	0,50 %	140	6,43 s
4	QAOA mezclador XY p=2 (3 semillas)	16	32	18,8 %	0,82 %	236	12,35 s
4	QAOA mezclador XY p=3 (3 semillas)	16	32	18,5 %	1,33 %	332	27,99 s
	Referencia: muestrear al azar (bits uniformes / un 1 por fila)			0,04 % / 9,4 %	0,00 % / 0,78 %

Fracción factible y P(óptimo) se miden en 8 192 disparos finales con los parámetros optimizados. «Mejor costo factible» es el mejor costo real C(x) entre las muestras válidas, no la energía penalizada del QUBO. El mezclador XY parte de estados W por fila y conserva «un 1 por fila», así que solo la restricción de columnas queda penalizada.

Elección de λ (penalización)

λ por defecto = max_i Σ_kF_ik · max D + 1: mover o quitar una asignación no puede ahorrar más que eso, así que con este valor ninguna violación de restricción compensa. El barrido comprueba, enumerando los 2^N² estados, si el mínimo del QUBO sigue siendo factible:

N	λ / λ_def	λ	E_min QUBO	Mínimo factible	Margen infactible
3	0,10	3,3	10,6	no	-13,4
3	0,25	8,3	20,5	no	-3,5
3	0,50	16,5	24,0	sí (C=24)	13,0
3	1,00	33,0	24,0	sí (C=24)	46,0
3	2,00	66,0	24,0	sí (C=24)	112,0
4	0,10	6,7	19,4	no	-12,6
4	0,25	16,8	32,0	sí (C=32)	7,5
4	0,50	33,5	32,0	sí (C=32)	41,0
4	1,00	67,0	32,0	sí (C=32)	108,0
4	2,00	134,0	32,0	sí (C=32)	242,0

«Margen infactible» = energía del mejor estado inválido − energía del mejor válido; si es negativo, el QUBO premia soluciones inválidas.

QAOA-XY (p=2) con λ reducido

N	λ / λ_def	Costo	Factible	P(óptimo)
3	0,25	24	24,5 %	23,27 %
3	0,50	24	26,3 %	22,19 %
3	1,00	24	33,1 %	27,92 %
4	0,25	32	36,3 %	3,74 %
4	0,50	32	18,4 %	0,31 %
4	1,00	32	18,3 %	0,22 %

Un λ menor suaviza el paisaje de energía pero puede dejar de garantizar que el mínimo sea factible: por eso se reporta siempre la fracción factible y el costo real.

Instancia completa N = 10 (100 variables binarias)

Método	Corridas	Mejor	Media	Gap mejor	Tiempo medio
Enumeración exacta (10! = 3 628 800)	1	340	—	0,0 %	4,24 s
Recocido simulado (20 000 iter.)	10	340	349,0	0,0 %	0,50 s
Búsqueda local 2-swap, 1 arranque(s)	10	364	374,2	7,1 %	1,2 ms
Búsqueda local 2-swap, 5 arranque(s)	10	358	366,2	5,3 %	5,6 ms
Búsqueda local 2-swap, 20 arranque(s)	10	340	351,6	0,0 %	0,02 s
LNS k=3 · sub-solver exacto (clásico)	5	352	370,8	3,5 %	6,2 ms
LNS k=4 · sub-solver exacto (clásico)	5	362	366,0	6,5 %	0,01 s
LNS k=3 · sub-solver QAOA-XY (Qiskit, 9 qubits)	5	350	366,0	2,9 %	80,84 s
LNS k=4 · sub-solver QAOA-XY (Qiskit, 16 qubits)	2	368	373,0	8,2 %	134,31 s

LNS + QAOA k=3: QAOA encontró el óptimo del subproblema en 300 de 300 subproblemas (100 %), con 32 % de muestras factibles en promedio.

LNS + QAOA k=4: QAOA encontró el óptimo del subproblema en 60 de 60 subproblemas (100 %), con 14 % de muestras factibles en promedio.

Presupuesto: LNS exacto y LNS+QAOA k=3 hacen 60 iteraciones. LNS+QAOA k=4 hace solo 30 (p=1), por el costo de simular 16 qubits, así que no es directamente comparable.

Gap = 100·(C − 340)/340, solo sobre asignaciones válidas. Todas las filas reportan costos reales C(x), no energías penalizadas.

Convergencia del LNS (costo por iteración)

exacto k=3 (final 366) exacto k=4 (final 364) QAOA k=3 (final 364) QAOA k=4 (final 378)

Etapa 3 · Escalamiento

N	Variables QUBO	Términos Ising	Permutaciones	Fracción factible de 2^N²	Memoria statevector	Puertas 2q (p=1, XY)	Óptimo exacto	Tiempo exacto	Recocido
3	9	46	6	1.2e-2	8 KiB	90	24	0,1 ms	24
4	16	113	24	3.7e-4	1 MiB	224	32	0,1 ms	32
5	25	266	120	3.6e-6	512 MiB	530	58	0,2 ms	58
6	36	517	720	1.0e-8	1 TiB	1.032	94	0,7 ms	94
7	49	890	5.040	9.0e-12	8 PiB	1.778	112	9,0 ms	112
8	64	1.521	40.320	2.2e-15	256 EiB	3.040	214	0,06 s	214
9	81	2.386	362.880	1.5e-19	3.4e+7 EiB	4.770	264	0,79 s	264
10	100	3.611	3.628.800	2.9e-24	1.8e+13 EiB	7.220	340	7,10 s	350

El QUBO completo pide 100 qubits y 2¹⁰⁰ amplitudes; la fracción de estados válidos cae a ~10⁻²⁴. Por eso, para N=10, el componente cuántico trabaja solo sobre vecindarios de k elementos (k² qubits) dentro de un LNS clásico, en vez de simular un único circuito de 100 qubits.

Qué hace Qiskit y qué es clásico

Qiskit (circuitos, simulados en Aer)	Hamiltoniano de Ising (`SparsePauliOp`, x = (1 − Z)/2); circuito QAOA con capas RZ/RZZ de costo y mezcladores RX o XY (`XXPlusYYGate`); estados W (`StatePreparation`); transpilación y muestreo con `SamplerV2` de Aer.
Clásico	Lectura del MPS y factorización F·D; armado del QUBO y λ; optimización de (γ, β) con COBYLA sobre el CVaR_0,2 de las energías muestreadas; decodificación y verificación de factibilidad; LNS (elegir vecindario, término lineal con los fijos, aceptar); todos los baselines.
No usado	Hardware cuántico real. Los tiempos son de simulación clásica y no anticipan tiempos en un QPU.

Conclusiones

Con N=3 y N=4, el óptimo de control (24 y 32) aparece en las muestras de casi todas las configuraciones. La diferencia está en cuánta probabilidad pone QAOA en las buenas asignaciones.
El QAOA estándar con penalizaciones apenas supera al azar: con N=4 solo el 0,5 % de las muestras es válido. El mezclador XY, que respeta la estructura del problema, sube esa cifra al 19 %.
Hay que compararlo con el azar «justo» (un 1 por fila). Con N=3, QAOA-XY concentra P(óptimo) en 21 % frente a 7,4 % al azar. Con N=4 duplica la factibilidad (19 % vs 9,4 %), pero P(óptimo) queda en el nivel del azar (0,88 % vs 0,78 %). Con p ≤ 3, el paisaje de N=4 ya es difícil para QAOA.
Con N=10, el LNS con QAOA (k=3) obtiene 350 (media 366,0), frente a 352 (media 370,8) con sub-solver exacto. Eso no es ventaja cuántica: QAOA resolvió el 100 % de los subproblemas, y la diferencia viene de cómo se rompen los empates entre sub-asignaciones igual de buenas. Con k=3 hay solo 6 sub-asignaciones, que el muestreo encuentra casi seguro.
A esta escala, lo clásico es muy superior: la búsqueda local multiarranque y el recocido encuentran 340 en milisegundos o décimas de segundo, y la enumeración lo certifica en segundos. QAOA es útil como componente de vecindario y para estudiar ansätze que respeten restricciones. Para que aporte de verdad haría falta k grande, donde k! ya no se puede enumerar, y eso hoy no se puede simular con statevector.

Reproducibilidad

Generado 2026-10-24T03:15:27+00:00 (modo completo, 1.045 s) · Python 3.12.13 · Qiskit 2.6.1 · Qiskit Aer 0.18.0 · NumPy 2.5.4 · SciPy 1.18.1

cd quantum
uv venv --python 3.12 .venv && uv pip install --python .venv/bin/python -r requirements.txt
.venv/bin/python run_experiments.py      # escribe results/results.json

Semillas: recocido 0–9, QAOA Etapa 1 {11, 23, 37}, LNS 0–4. Las semillas de los subproblemas QAOA del LNS se derivan del generador del LNS. Configuración y parámetros (γ, β) optimizados de cada corrida: en quantum/results/results.json.