⚛️ quantum physics

Optimized QUBO formulation methods for quantum computing

Este trabajo presenta métodos de formulación QUBO optimizados, denominados "iterative quadratic polynomial" y "master-satellite", que reducen drásticamente el número de variables necesarias para resolver problemas de optimización combinatoria NP-duros en dispositivos NISQ, demostrando su eficacia superior frente a métodos estándar mediante la resolución del problema financiero Max-Profit Balance Settlement en los annealers cuánticos D-Wave Advantage y Advantage2.

Autores originales: Dario De Santis, Salvatore Tirone, Stefano Marmi, Vittorio Giovannetti

Publicado 2026-02-25

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Dario De Santis, Salvatore Tirone, Stefano Marmi, Vittorio Giovannetti

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

¡Claro que sí! Imagina que tienes un rompecabezas gigante y muy complicado. El objetivo es encontrar la pieza perfecta que resuelva un problema de dinero (como quién le debe a quién en una gran red de bancos). Este tipo de problemas se llaman optimización combinatoria.

Ahora, imagina que quieres usar una computadora cuántica (una máquina súper potente pero muy delicada y pequeña) para resolver este rompecabezas. El problema es que estas máquinas cuánticas actuales, llamadas NISQ, son como niños pequeños con una caja de juguetes limitada: tienen muy pocas "piezas" (qubits) para trabajar.

Aquí es donde entra este artículo. Los autores, Dario De Santis y su equipo, han inventado una nueva forma de empaquetar el problema para que quepa en esa caja de juguetes pequeña, sin perder la solución.

Aquí te explico cómo lo hacen, usando analogías sencillas:

1. El Problema: Demasiado "Relleno"

Para que una computadora cuántica entienda un problema de dinero, primero hay que traducirlo a un lenguaje especial llamado QUBO. Piensa en el QUBO como una receta de cocina.

La receta original: Tiene los ingredientes principales (las transacciones de dinero).
Las reglas: "No puedes gastar más de lo que tienes" o "Si recibes dinero, también debes dar algo".
El problema: Para que la computadora entienda las reglas, los métodos antiguos añadían mucho "relleno" (variables de holgura o slack variables). Era como intentar cocinar un pastel pequeño pero tener que usar 100 huevos extra solo para medir la harina. Esto llenaba la caja de juguetes de la computadora cuántica y no le dejaba espacio para el pastel real.

2. La Solución: Dos Nuevas Herramientas Mágicas

Los autores proponen dos técnicas nuevas para reducir ese "relleno" en un 90%. Imagina que en lugar de usar 100 huevos, solo necesitas 10.

A. El Método del "Polinomio Iterativo Cuadrático" (IQP)

Imagina que tienes una regla simple: "Si tienes una entrada, debes tener una salida".

El método antiguo: Intentaba cubrir todas las posibilidades imaginables, incluso las absurdas, usando muchas variables extra.
El método IQP: Es como un detective muy inteligente. En lugar de revisar todo el mundo, solo mira las combinaciones que realmente importan. Construye una fórmula matemática (un polinomio) que es perfecta para esas pocas combinaciones. Si la regla se cumple, la fórmula dice "0" (bien). Si se rompe, dice "-1" (mal).
La ventaja: Funciona increíblemente bien cuando las reglas son simples y solo involucran a pocas personas (nodos) a la vez.

B. El Método "Maestro-Satélite" (MS)

Imagina que tienes dos reglas para un grupo de amigos:

Regla Maestra: "Todos deben estar de acuerdo en ir a la fiesta".
Regla Satélite: "Si van a la fiesta, deben llevar un regalo".

El método antiguo: Verificaba la regla del regalo para todos, incluso para los que no iban a la fiesta. ¡Desperdicio de energía!
El método Maestro-Satélite: Primero verifica la regla Maestra. Si alguien no cumple con "ir a la fiesta", ¡la computadora ignora la regla del regalo para esa persona! Solo verifica el regalo si ya pasaron la primera prueba.
La magia: Al no tener que verificar el regalo para los que no van, necesitas muchas menos "variables de relleno". Además, si la regla del satélite da un "premio accidental" a alguien que no debería tenerlo (porque no cumplió la regla maestra), simplemente se aumenta el castigo de la regla maestra para que el premio no valga la pena.

3. El Caso Real: El Problema de "Pago Equilibrado" (MPBS)

Para probar sus ideas, usaron un problema del mundo real: Max-Profit Balance Settlement.

La situación: Imagina una red de empresas que se deben dinero entre sí. Algunas deben mucho, otras deben poco. El objetivo es cancelar la mayor cantidad de deudas posible sin que nadie se quede en números rojos (que su saldo no baje de cierto límite).
El desafío: Es un problema muy difícil (NP-duro) y con muchas reglas estrictas.

4. Los Resultados: ¡Un Salto Cuántico!

Los autores probaron sus métodos en dos computadoras cuánticas reales de D-Wave (llamadas Advantage y Advantage2).

Ahorro de espacio: Sus métodos necesitaron un 90% menos de "relleno" (variables de holgura) que los métodos tradicionales.
Mejores resultados: Cuando usaron sus métodos, la computadora cuántica encontró la solución correcta muchas más veces (hasta 184 veces más en los casos más grandes) que cuando usaron los métodos viejos.
Escalabilidad: Con los métodos viejos, a medida que el problema crecía, la computadora fallaba casi siempre. Con sus métodos, la computadora siguió funcionando bien incluso con problemas más grandes.

En Resumen

Imagina que quieres enviar un mensaje secreto a través de un túnel muy estrecho.

Antes: Intentabas meter un camión entero (el problema) con mucho aire comprimido (las variables de relleno) para que no se aplastara, pero el camión era tan grande que no pasaba por el túnel.
Ahora: Los autores han diseñado un vehículo plegable y ligero (sus nuevas técnicas) que se ajusta perfectamente al túnel, eliminando todo el aire innecesario.

¿Por qué importa?
Esto es crucial porque las computadoras cuánticas actuales son pequeñas. Si podemos reducir el tamaño de los problemas que les damos, podemos resolver problemas financieros reales, de logística o de descubrimiento de medicamentos que antes eran imposibles para estas máquinas. Es como aprender a doblar la ropa de forma que quepa en una maleta de mano, permitiéndote viajar a lugares lejanos sin necesidad de un camión de mudanzas.

Resumen Técnico: Métodos Optimizados de Formulación QUBO para Computación Cuántica

1. El Problema

Los dispositivos cuánticos de escala intermedia ruidosa (NISQ), como los recocedores cuánticos de D-Wave, tienen limitaciones estrictas en el número de qubits y la conectividad disponible. Muchos problemas de optimización combinatoria (NP-duros) se formulan como Optimización Binaria Cuadrática sin Restricciones (QUBO) para ser resueltos en estas máquinas.

El principal cuello de botella en la reformulación de problemas con restricciones a QUBO es la necesidad de introducir variables de holgura (slack variables).

Método Estándar: Para convertir restricciones lineales o no lineales en formas cuadráticas, el método convencional requiere un número de variables de holgura que escala logarítmicamente con el rango de los valores de las restricciones. En escenarios reales (como finanzas), esto puede requerir decenas de variables de holgura por nodo, superando rápidamente la capacidad de los qubits actuales.
Consecuencia: Un exceso de variables de holgura aumenta la complejidad del problema, la conectividad requerida y reduce drásticamente la tasa de éxito de los algoritmos cuánticos, especialmente a medida que crece el tamaño de la entrada.

2. Metodología Propuesta

Los autores introducen dos técnicas novedosas e independientes para reducir drásticamente el número de variables de holgura necesarias, permitiendo reformular problemas sin aproximar las restricciones originales:

A. Método del Polinomio Cuadrático Iterativo (IQP - Iterative Quadratic Polynomial)

Concepto: En lugar de usar la expansión binaria estándar para las variables de holgura, el IQP busca construir un polinomio cuadrático $P(x, s)$ que penalice directamente las combinaciones de variables binarias que violan una restricción.
Proceso Iterativo: El algoritmo comienza intentando encontrar un polinomio sin variables de holgura ( $M=0$ ). Si no es posible (debido a que hay más condiciones de sub-restricción que parámetros libres), añade iterativamente una variable de holgura ( $M=1, 2, \dots$ ) hasta encontrar una solución factible.
Ventaja: Aprovecha que las condiciones de desigualdad ( $P \leq -1$ ) son menos restrictivas que las de igualdad, permitiendo a menudo soluciones sin holguras o con muy pocas, incluso para restricciones no lineales o con parámetros no enteros.

B. Método Maestro-Satélite (MS - Master-Satellite)

Concepto: Diseñado para problemas donde múltiples restricciones comparten el mismo subconjunto de variables binarias.
Mecanismo:
- Se selecciona una restricción como Maestra (Master) y se impone estrictamente para todas las combinaciones de variables.
- Las restricciones restantes se tratan como Satélites (Satellite). Estas solo se imponen (se penalizan) para aquellas combinaciones que ya satisfacen la restricción maestra.
Beneficio: Al ignorar las combinaciones que violan la restricción maestra, se reduce el número de sub-restricciones que el polinomio satélite debe satisfacer, lo que disminuye la necesidad de variables de holgura.
Ajuste de Multiplicadores: Para evitar que las restricciones satélites generen "incentivos accidentales" (valores positivos) en combinaciones que violan la restricción maestra, se introduce un multiplicador relativo $\lambda_{MC} > 1$ que amplifica la penalización de la restricción maestra, asegurando que la penalización neta sea negativa incluso si el satélite ofrece un incentivo.

C. Problemas Localmente Restringidos
Los autores aplican estas técnicas a una clase de problemas donde las restricciones se definen nodo a nodo en un grafo (problemas localmente restringidos). Esto permite aplicar el método IQPMS (combinación de IQP y MS) de manera eficiente, ya que las restricciones de cada nodo dependen solo de las aristas incidentes a ese nodo.

3. Caso de Estudio: Max-Profit Balance Settlement (MPBS)

Para validar sus métodos, los autores aplican la técnica a un problema NP-duro inspirado en un escenario financiero real: el Max-Profit Balance Settlement (MPBS).

Objetivo: Maximizar el valor de las transacciones de cobro pendientes que pueden resolverse autónomamente entre usuarios sin intervención externa.
Restricciones:
1. CAP/FLOOR: El saldo neto de cada usuario debe permanecer dentro de un rango predefinido.
2. IN/OUT: Si un usuario realiza al menos un pago (es deudor), debe recibir al menos un pago (es acreedor), y viceversa.
Datos: Se utilizaron instancias basadas en datos reales de UniCredit, caracterizadas por grafos con un bajo número de aristas por nodo (promedio entre 2 y 5).

4. Resultados Experimentales

Los autores probaron sus formulaciones en dos recocedores cuánticos de D-Wave: el Advantage_system4.1 (Adv1) y el prototipo de nueva generación Advantage2_prototype1.1 (Adv2).

Reducción de Variables:
- Comparado con el método estándar, la técnica IQPMS redujo el número de variables de holgura en aproximadamente un 90%.
- Para nodos con 2, 3 o 4 aristas, el método IQPMS no requirió ninguna variable de holgura para las restricciones IN/OUT y CAP/FLOOR, mientras que el método estándar requería entre 2 y 4 variables por nodo.
- El número de variables totales (lógicas + holgura) por arista añadida bajó de ~4.88 (estándar) a ~1.30 (IQPMS).
Rendimiento en Recocedores Cuánticos:
- Tasa de Éxito: La adopción de IQPMS resultó en tasas de éxito significativamente mayores. El factor de mejora (ganancia) osciló entre 7 veces (para instancias pequeñas en Adv1) hasta 184 veces (para instancias grandes en Adv2) en comparación con el método estándar.
- Escalabilidad: Mientras que la calidad de la solución del método estándar caía rápidamente al aumentar el tamaño de la entrada, el método IQPMS mantuvo altas tasas de éxito incluso para instancias más grandes.
- Comparación de Hardware: El recocedor Advantage2 (Adv2), con mayor conectividad (topología Zephyr) y menor ruido, superó consistentemente al Advantage_system4.1 (topología Pegasus), demostrando la importancia de la conectividad para problemas con formulaciones más eficientes.

5. Contribuciones Clave

Nuevos Paradigmas de Reformulación: Introducción de los métodos IQP y MS que permiten formular restricciones sin necesidad de aproximar el problema original ni resolver QUBOs preliminares (a diferencia de métodos como ADMM o Lagrangianos aumentados).
Reducción Masiva de Recursos: Logro de una reducción del ~90% en variables de holgura, lo que permite resolver problemas más grandes en hardware NISQ actual.
Generalidad: Los métodos son aplicables a restricciones lineales y no lineales, con parámetros enteros o no enteros, y no requieren que todas las variables estén completamente conectadas (fomentando la dispersidad o sparsity del QUBO).
Validación Empírica: Demostración práctica en un problema financiero real, comparando dos generaciones de hardware cuántico y estableciendo un nuevo estándar de referencia para la eficiencia en la codificación de problemas.

6. Significado e Impacto

Este trabajo es fundamental para la computación cuántica aplicada en el corto y mediano plazo (era NISQ). Al reducir la sobrecarga de variables de holgura, los autores "desbloquean" la capacidad de los recocedores cuánticos actuales para abordar problemas de optimización combinatoria de tamaño realista que antes eran inabordables debido a la falta de qubits.

La investigación sugiere que el refinamiento de las formulaciones QUBO (pre-procesamiento) es tan crucial como el desarrollo de hardware. Al hacer que los problemas sean más "ligeros" y menos conectados, se mejora directamente la calidad de la salida de los dispositivos cuánticos, acercando la ventaja cuántica práctica en sectores como las finanzas, la logística y la optimización de redes.