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ó de cost quadràtica binària que defineix un problema QUBO s’escriu com

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

amb variables de decisió \(x_i \in \{0, 1\}\) i coeficients simètrics \(q_{ij} = q_{ji} \in \mathbb{R}\). Separar els termes diagonals posa de manifest els pesos lineals efectius:

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

Afegir restriccions com a penalitzacions

Com que QUBO no té restriccions, cada restricció es converteix en l’objectiu mitjançant un terme de penalització. Les restriccions d’igualtat lineal es poden descriure com,

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

on \(c_i\) són coeficients enters i \(C\) és una constant entera.

Incorporades com a penalitzacions, aquestes restriccions donen l’objectiu penalitzat

\[\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),\]

on \(\lambda_0 > 0\) és un paràmetre de força de la penalització.

Les restriccions d’inequació es poden definir com:

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

Per convertir-les en penalitzacions, s’admeten dues estratègies:

  • Penalització per variable de relaxació (per defecte):

    S’introdueixen variables de relaxació binàries addicionals per convertir les inequacions en igualtats i, a continuació, s’eleva al quadrat el residu. Per tant, el terme de penalització passa a ser:

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

    on \(s_k\) són variables binàries de relaxació introduïdes per codificar la restricció d’inequació (amb el nombre de bits \(N\) escollit de manera que la seva expansió binària cobreixi el rang de relaxació admissible) i \(\lambda_{1}\) controla la força de la penalització.

  • Penalització no equilibrada:

    Penalitza directament la violació sense variables de relaxació, fent servir dos pesos (a, b) per escalar de forma diferent les desviacions positives i negatives [1]. Definim \(h(x) = B - \sum_{i=1}^{n} \ell_i x_i\) com el residu signat de la restricció, i el terme de penalització passa a ser:

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

    on \(a, b > 0\) són paràmetres que controlen la força de la penalització per a violacions per sobre i per sota del límit, respectivament.

Per què QUBO?

  • Forma no restringida: molts annealers quàntics i solucionadors especialitzats accepten únicament formes quadràtiques binàries no restringides, cosa que fa del QUBO la lingua franca de l’optimització quàntica.

  • Codificació de penalitzacions: en lloc de descartar l’estructura de les restriccions, cada restricció es transforma en una penalització quadràtica, preservant la fidelitat del problema.

  • Mapatge directe: un cop en forma QUBO, podeu traduir directament el problema a termes Ising/Hamiltonian per a l’execució en maquinari.

Definir un QUBO

  1. Creació del model

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

  1. Objectiu

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

Avís

  • Si transform_to_qubo=True, la restricció ha de ser lineal (sense termes quadràtics), perquè es rescriurà com a (lhs-rhs)^2.

  • Si transform_to_qubo=False, s’assumeix que la restricció ja és una penalització quadràtica vàlida i s’afegirà tal qual.

Exemple: penalització per variable de relaxació

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)

Sortida:

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)

Exemple: penalització no equilibrada

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)

Sortida:

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

Linealització de termes de grau alt

Per definició, un objectiu QUBO és com a màxim quadràtic. Tanmateix, tant els objectius definits per l’usuari com els residus al quadrat produïts en penalitzar restriccions poden introduir monomis de grau tres o superior (per exemple, en elevar al quadrat una restricció amb un costat esquerre quadràtic). Per acceptar aquestes entrades, to_qubo() linealitza automàticament qualsevol monomi pseudo-booleà de grau més gran que dos introduint variables binàries auxiliars.

Per a cada parell de factors binaris \(a, b\) que cal col·lapsar, es crea una nova variable auxiliar \(w\) i la igualtat \(w = a \cdot b\) s’imposa mitjançant la penalització de Rosenberg

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

que és quadràtica, no negativa per a \(a, b, w \in \{0, 1\}\) i zero si i només si \(w = a \cdot b\). A continuació, en el monomi original el factor \(a \cdot b\) se substitueix per \(w\), reduint-ne el grau en un. La reducció s’itera fins que tot monomi és com a màxim quadràtic. Les variables auxiliars es memoritzen en memòria cau per parell no ordenat, de manera que els subproductes compartits (per exemple, \(x \cdot y \cdot z\) i \(x \cdot y \cdot w\), que reutilitzen tots dos \(x \cdot y\)) introdueixen una única variable auxiliar i una única penalització de Rosenberg.

Dos arguments per paraula clau de to_qubo() controlen aquest comportament:

  • linearize (per defecte True): activa o desactiva la reducció. Establiu linearize=False per mantenir el comportament estricte anterior, en què exportar un model amb termes de grau tres o superior llança un ValueError.

  • linearization_lagrange_multiplier (per defecte 100): el multiplicador de Lagrange aplicat a cada restricció de penalització de Rosenberg. Ha de ser prou gran per dominar qualsevol incentiu a violar les igualtats auxiliars \(w = a \cdot b\).

Exemple: objectiu i restricció cúbics

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()

Després d’executar to_qubo, el QUBO resultant conté una única variable binària auxiliar que substitueix \(x \cdot y\) (compartida entre l’objectiu i la penalització de la restricció), juntament amb una restricció d’igualtat que codifica la corresponent penalització de Rosenberg. Tant l’objectiu cúbic com la restricció cúbica al quadrat es redueixen a forma quadràtica, de manera que to_hamiltonian() es pot invocar directament.

Interoperabilitat

  • Convertir qualsevol model a QUBO

    Qualsevol Model genèric es pot convertir en un QUBO. Els monomis de grau superior es redueixen a forma quadràtica mitjançant la linealització amb penalització de Rosenberg descrita anteriorment (establiu linearize=False per desactivar-la):

    qubo_model = model.to_qubo()
  • Exportar a Hamiltonian

    Un cop en forma QUBO, traduïu directament a un Hamiltonian Ising analògic per a simulació o maquinari:

    h = qubo_model.to_hamiltonian()