QUBO

La subclasse QUBO s’especialitza en models d”Optimització Binària Quadràtica No Restringida (Quadratic Unconstrained Binary Optimization), on cada variable de decisió és binària i la funció objectiu és com a màxim quadràtica. A diferència dels models generals, les restriccions «dures» no es mantenen per separat sinó que es codifiquen directament a l’objectiu com a termes de penalització. La força de cada penalització és controlada pel seu multiplicador de Lagrange associat.

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ó.

Ineqaulity constraints can be defined as:

\[\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}\]

  where \(s_k\) are slack binary variables introduced to encode the inequality constraint (with the number of bits \(N\) chosen so that their binary expansion spans the admissible slack range) and \(\lambda_{1}\) control the penalty strength.

• Penalització no equilibrada:

  Directly penalize violation without slack variables using two weights (a, b) to scale positive and negative deviations differently [1]. we define \(h(x) = B - \sum_{i=1}^{n} \ell_i x_i\) as the signed residual of the constraint, and the penalty term becomes:

  \[- 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")

2. 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)

[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.

High-degree Term Linearization

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