Getting Started with QUBO in Python

A QUBO is a quadratic function of binary variables, and its simplest examples can be solved without quantum hardware or a specialist library. Its ingredients, however, are surprisingly modest: a collection of binary decisions, a score for each decision, and an additional score for choosing particular pairs together. The goal is to find the combination that minimizes the total score. QUBO is a mathematical model, not a claim about the hardware used to solve it. Both classical algorithms and quantum-oriented approaches can work with QUBO instances.

The easiest way to understand the format is to make one small enough to solve completely. Suppose we have two binary variables, x and y. We want to minimize the expression below:

E(x, y) = −3x − 2y + 4xy,    x, y ∈ {0, 1}.

The first two terms reward selecting either variable, because they lower the score. The final term adds a cost when both are selected. As a miniature model, it resembles a choice between two attractive activities that compete for the same resource. It is not yet a full scheduling problem, but it shows the defining interaction in a quadratic binary model.

Four combinations, no mystery

It is not yet a full scheduling problem, but it shows the defining interaction in a quadratic binary model.

The best choice is x=1, y=0, with an energy of -3. We can confirm it using a few lines of ordinary Python. This gives us a transparent baseline against which any later solver call can be checked.

from itertools import product

def energy(x, y):
    return -3 * x - 2 * y + 4 * x * y

results = [((x, y), energy(x, y)) for x, y in product((0, 1), repeat=2)]
for assignment, value in results:
    print(assignment, value)

best_assignment, best_value = min(results, key=lambda result: result[1])
assert best_assignment == (1, 0)
assert best_value == -3

From an expression to a QUBO matrix

QUBO is often written as xᵀQx, where the vector contains binary variables and Q specifies their linear and pairwise coefficients. Because a binary variable satisfies x²=x, diagonal entries can encode the linear terms. One upper-triangular matrix for our example is:

Q = ( −3   4 )
    (  0  −2 ).

Using the convention xᵀQx, the off-diagonal coefficient of 4 contributes exactly 4xy. Another convention stores half that coefficient in both symmetric positions. Both are valid, but mixing conventions can double interaction strengths accidentally. Always check which form a library or API expects before submitting a model.

Exhaustive enumeration becomes a useful reference implementation for small instances, not a practical production method for every size.

The example deliberately has no explicit constraints. Many practical problems do, and translating their rules into penalty terms can be difficult. A penalty must be strong enough to discourage prohibited combinations without overwhelming the meaningful differences between otherwise valid choices. It is not sufficient merely to write a quadratic expression and assume that its minimum represents a practical solution.

Why start with exhaustive enumeration?

For two variables, an external solver would be excessive. For ten variables, there are 1,024 possible assignments, still manageable for testing. But the number grows exponentially, and finding high-quality assignments to general QUBO instances can become computationally challenging. Exhaustive enumeration becomes a useful reference implementation for small instances, not a practical production method for every size.

This is particularly important for quantum benchmarking. If an experiment claims that a new method improves an optimization workflow, the comparison should include strong classical methods, realistic time or resource budgets, and checks that the returned assignments actually optimize the intended model. The existence of a QUBO formulation does not imply that quantum hardware will solve it more efficiently.

4colors Optimizer for QUBO is a classical solver intended in part for quantum optimization research and comparison. To assess any QUBO solver, start with a small instance whose optimum is known, then check the submitted coefficient convention, returned assignment, calculated objective and the meaning of the solver status.