QUBO Formulation Guide

What is a QUBO?

A QUBO (Quadratic Unconstrained Binary Optimization) problem is defined by a symmetric matrix Q and a binary vector x. The goal is to find x ∈ {0,1}ⁿ that minimizes f(x) = xᵀQx. Every coefficient Qᵢⱼ encodes a relationship between binary variables xᵢ and xⱼ — diagonal entries represent linear terms, off-diagonal entries represent quadratic interactions.

Why QUBO? Because simulated annealing, QAOA, and most quantum-inspired algorithms operate natively on Ising / QUBO energy landscapes. Expressing your problem in this form gives you access to the full NEROX solver stack.

Minimal example

python

import numpy as np
import nerox

# Minimize x0 + x1 - 2*x0*x1   (answer: x0=1, x1=1, energy=-1)
Q = np.array([
    [ 1, -2],
    [-2,  1],
], dtype=float)
Q = (Q + Q.T) / 2   # always symmetrize

job = nerox.optimize.qubo(Q=Q, solver="gpu")
result = job.wait()
print(result.solution)    # [1, 1]
print(result.objective)   # -1.0

Constraint encoding via penalties

QUBO is unconstrained — constraints must be encoded as penalty terms added to the objective. For an equality constraint h(x) = 0, add λ·h(x)² to the objective. The penalty weight λ must be large enough that violating the constraint costs more than any feasible solution saves.

python

# Example: exactly one variable must be 1 (one-hot constraint)
# Constraint: sum(x) = 1  =>  penalty: lambda * (sum(x) - 1)^2
# Expanded: lambda * (sum_i x_i^2 + 2*sum_{i<j} x_i*x_j - 2*sum_i x_i + 1)
# Since x_i^2 = x_i for binary x:

n = 5
lam = 10.0   # penalty weight — must exceed max gain from objective

Q_penalty = np.zeros((n, n))
for i in range(n):
    Q_penalty[i, i] += lam * (1 - 2)      # x_i term: lambda*(1 - 2)*x_i
    for j in range(i + 1, n):
        Q_penalty[i, j] += 2 * lam        # x_i*x_j cross term
Q_penalty = (Q_penalty + Q_penalty.T) / 2

Choosing the penalty weight λ

A common rule of thumb: λ should be at least (1 + max|objective coefficient|). Too small and the solver ignores constraints. Too large and the objective signal drowns in noise. Start with λ = 5× the max absolute value of your objective Q matrix and adjust based on solution feasibility.

Variable encoding for integers

python

# Integer variable x ∈ {0, ..., K} using binary expansion:
# x = sum_{k=0}^{ceil(log2(K+1))-1} 2^k * b_k

# For x ∈ {0, ..., 7} (3 binary variables):
def int_to_binary(k_bits):
    return [2**k for k in range(k_bits)]

# x = b0 + 2*b1 + 4*b2
# Substitute into your objective and expand

Scaling tips

Normalize your Q matrix so coefficients are in [-1, 1]. GPU annealing cooling schedules are calibrated for this range — oversized coefficients cause premature freezing. Use Q = Q / np.abs(Q).max() before submitting, then scale your result back.

For sparse problems (most real-world instances), only populate non-zero entries. NEROX automatically detects sparsity and uses sparse memory layouts on the GPU for problems over 2,000 variables.