QUBO

The QUBO subclass specializes in Quadratic Unconstrained Binary Optimization models, where every decision variable is binary and the objective function is at most quadratic. Unlike general models, “hard” constraints are not maintained separately but are encoded directly into the objective as penalty terms. The strength of each penalty is controlled by its associated Lagrange multiplier.

La función de coste cuadrática binaria que define un problema QUBO se escribe como

\[f(x) = \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} q_{ij} x_i x_j,\]

con variables de decisión \(x_i \in \{0, 1\}\) y coeficientes simétricos \(q_{ij} = q_{ji} \in \mathbb{R}\). Separar los términos diagonales pone de manifiesto los pesos lineales efectivos:

\[f(x) = \sum_{i=1}^{n-1} \sum_{j>i} q_{ij} x_i x_j + \sum_{i=1}^{n} q_{ii} x_i.\]

Añadir Restricciones como Penalizaciones

Dado que QUBO es sin restricciones, cada restricción se convierte en el objetivo mediante un término de penalización. Las restricciones de igualdad lineales se pueden describir como,

\[\sum_{i=1}^{n} c_i x_i = C, \quad c_i \in \mathbb{Z},\]

donde \(c_i\) son coeficientes enteros y \(C\) es una constante entera.

Incrustadas como penalizaciones, estas restricciones dan el objetivo penalizado

\[\min_{x,\,s} \left( \sum_{i=1}^{n-1} \sum_{j>i} c_{ij} x_i x_j + \sum_{i=1}^{n} h_i x_i + \lambda_0 \left( \sum_{i=1}^{n} q_i x_i - C \right)^{2} \right),\]

donde \(\lambda_0 > 0\) es un parámetro de intensidad de penalización.

Las restricciones de desigualdad se pueden definir como:

\[\sum_{i=1}^{n} \ell_i x_i \leq B, \quad \ell_i \in \mathbb{Z}.\]

Para convertirlas en penalizaciones, se admiten dos estrategias:

• Penalización con variables de holgura (Slack penalization, predeterminada):

  Se introducen variables de holgura binarias adicionales para convertir las desigualdades en igualdades y luego se eleva al cuadrado el residuo. Por lo tanto, el término de penalización se convierte en:

  \[\lambda_1 \left( B - \sum_{i=1}^{n} \ell_i x_i - \sum_{k=0}^{N-1} 2^{k} s_k \right)^{2}\]

  donde \(s_k\) son variables binarias de holgura introducidas para codificar la restricción de desigualdad (con el número de bits \(N\) elegido de modo que su expansión binaria abarque el rango de holgura admisible) y \(\lambda_{1}\) controla la intensidad de la penalización.

• Penalización desequilibrada (Unbalanced penalization):

  Se penaliza directamente la violación sin variables de holgura usando dos pesos (a, b) para escalar de forma diferente las desviaciones positivas y negativas [1]. Se define \(h(x) = B - \sum_{i=1}^{n} \ell_i x_i\) como el residuo con signo de la restricción, y el término de penalización se convierte en:

  \[- a h(x) + b h(x)^2,\]

  donde \(a, b > 0\) son parámetros que controlan la intensidad de la penalización para violaciones por encima y por debajo del límite, respectivamente.

¿Por qué QUBO?

• Forma sin restricciones: Muchos recocedores cuánticos (quantum annealers) y solvers especializados aceptan únicamente formas cuadráticas binarias sin restricciones, lo que convierte al QUBO en la lingua franca de la optimización cuántica.

• Codificación por penalización: En lugar de descartar la estructura de restricciones, cada restricción se transforma en una penalización cuadrática, preservando la fidelidad del problema.

• Mapeo directo: Una vez en forma QUBO, el problema se puede traducir directamente a términos Ising/Hamiltonian para su ejecución en hardware.

Definir un QUBO

1. Creación del modelo

from qilisdk.core.model import QUBO, ObjectiveSense
model = QUBO("qubo_example")

2. Objetivo

# sum of weights x minus risk penalty
model.set_objective(5 * x1 + 3 * x2 - 2 * x1 * x2,
                    label="return_minus_risk",
                    sense=ObjectiveSense.MAXIMIZE)

Advertencia

• Si transform_to_qubo=True, la restricción debe ser lineal (sin términos cuadráticos), ya que se reescribirá como (lhs-rhs)^2.

• Si transform_to_qubo=False, se asume que la restricción ya es una penalización cuadrática válida y se añadirá textualmente.

Ejemplo: Penalización con Variables de Holgura

from qilisdk.core.model import QUBO, ObjectiveSense
from qilisdk.core.variables import BinaryVariable, LEQ

b, b2 = BinaryVariable("b"), BinaryVariable("b2")
model = QUBO("slack_example")
model.set_objective(b2 + 2 * b + 1, label="obj", sense=ObjectiveSense.MINIMIZE)

# Enforce b <= 0.5 via slack, squared penalty in objective
model.add_constraint("c1", LEQ(b + 2 * b2, 1), lagrange_multiplier=10, penalization="slack", transform_to_qubo=True)

print(model.qubo_objective)

Salida:

obj: (-8.0) * b + b2 + (11.0) + (40.0) * (b2 * b) + (40.0) * (b2 * c1_slack(0)) + (20.0) * (b * c1_slack(0)) + (-10.0) * c1_slack(0)

Ejemplo: Penalización Desequilibrada

from qilisdk.core.model import QUBO, ObjectiveSense
from qilisdk.core.variables import BinaryVariable, LEQ

b, b2 = BinaryVariable("b"), BinaryVariable("b2")
model = QUBO("unbalanced_penalization_example")
model.set_objective(b2 + 2 * b + 1, label="obj", sense=ObjectiveSense.MINIMIZE)

# Enforce b <= 0.5 via slack, squared penalty in objective
model.add_constraint("c1", LEQ(b + 2 * b2, 1), lagrange_multiplier=1, penalization="unbalanced", transform_to_qubo=True)

print(model.qubo_objective)

Salida:

obj: (2) * b + (3.0) * b2 + (1) + (4.0) * (b2 * b)

[1]

Montañez-Barrera, Jhon Alejandro, et al. «Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms.» Quantum Science and Technology 9.2 (2024): 025022.

Linealización de Términos de Grado Alto

Por definición, un objetivo QUBO es como mucho cuadrático. Sin embargo, tanto los objetivos definidos por el usuario como los residuos al cuadrado generados al penalizar restricciones pueden introducir monomios de grado tres o superior (por ejemplo, al elevar al cuadrado una restricción con un lado izquierdo cuadrático). Para aceptar estas entradas, to_qubo() linealiza automáticamente cualquier monomio pseudo-booleano de grado mayor que dos introduciendo variables binarias auxiliares.

Para cada par de factores binarios \(a, b\) que se debe colapsar, se crea una nueva variable auxiliar \(w\) y la igualdad \(w = a \cdot b\) se impone mediante la penalización de Rosenberg

\[P(a, b, w) = a \cdot b - 2 \cdot a \cdot w - 2 \cdot b \cdot w + 3 \cdot w,\]

que es cuadrática, no negativa para \(a, b, w \in \{0, 1\}\) y cero si y solo si \(w = a \cdot b\). A continuación, en el monomio original el factor \(a \cdot b\) se sustituye por \(w\), reduciendo su grado en uno. La reducción se itera hasta que todo monomio es como mucho cuadrático. Las variables auxiliares se almacenan en caché por par no ordenado, de modo que los subproductos compartidos (por ejemplo, \(x \cdot y \cdot z\) y \(x \cdot y \cdot w\), que reutilizan ambos \(x \cdot y\)) introducen una única variable auxiliar y una única penalización de Rosenberg.

Dos argumentos por palabra clave de to_qubo() controlan este comportamiento:

• linearize (predeterminado True): activa o desactiva la reducción. Establezca linearize=False para mantener el comportamiento estricto anterior, en el que exportar un modelo con términos de grado tres o superior lanza un ValueError.

• linearization_lagrange_multiplier (predeterminado 100): el multiplicador de Lagrange aplicado a cada restricción de penalización de Rosenberg. Debe ser lo bastante grande como para dominar cualquier incentivo a violar las igualdades auxiliares \(w = a \cdot b\).

Ejemplo: Objetivo y Restricción Cúbicos

from qilisdk.core import BinaryVariable, EQ, Model, ObjectiveSense

x, y, z = BinaryVariable("x"), BinaryVariable("y"), BinaryVariable("z")

model = Model("cubic")
model.set_objective(x * y * z, sense=ObjectiveSense.MAXIMIZE)
model.add_constraint("forbid_triple", EQ(x * y * z, 0), lagrange_multiplier=10)

qubo = model.to_qubo(linearization_lagrange_multiplier=50)
ham = qubo.to_hamiltonian()

Tras ejecutar to_qubo, el QUBO resultante contiene una única variable binaria auxiliar que sustituye a \(x \cdot y\) (compartida entre el objetivo y la penalización de la restricción), junto con una restricción de igualdad que codifica la correspondiente penalización de Rosenberg. Tanto el objetivo cúbico como la restricción cúbica al cuadrado se reducen a forma cuadrática, de modo que to_hamiltonian() se puede invocar directamente.

Interoperabilidad

• Convertir cualquier Modelo a QUBO

  Cualquier Model genérico se puede convertir en un QUBO. Los monomios de grado superior se reducen a forma cuadrática mediante la linealización con penalización de Rosenberg descrita arriba (establezca linearize=False para desactivarla):

  qubo_model = model.to_qubo()
  

• Exportar a Hamiltonian

  Una vez en forma QUBO, se puede traducir directamente a un Hamiltonian Ising analógico para simulación o hardware:

  h = qubo_model.to_hamiltonian()