QUBO

QUBO is the standard input format for quantum annealing processors. A QUBO problem asks: given a matrix Q of real-valued coefficients and binary variables x_i in {0, 1}, find the assignment that minimizes:

f(x) = sum_{i} Q_{ii} * x_i + sum_{i<j} Q_{ij} * x_i * x_j

This can be written compactly as f(x) = x^T Q x, where x is a vector of binary variables and Q is an upper-triangular real matrix.

Why QUBO Matters

Almost every NP-hard combinatorial optimization problem can be expressed as a QUBO. This includes:

• Max-Cut: partition graph vertices to maximize crossing edges
• Portfolio optimization: binary selection of assets under budget constraints
• Vehicle routing: minimize total travel distance for a fleet
• Scheduling: assign tasks to time slots without conflicts
• Protein folding: find minimum energy configurations of amino acid chains

The significance of QUBO for quantum computing is that D-Wave’s quantum annealing hardware physically minimizes a QUBO objective. The binary variables map to qubit spin states (0 = spin down, 1 = spin up), and the Q matrix entries map to qubit biases and coupler strengths on the quantum annealing chip.

Relationship to the Ising Model

QUBO is mathematically equivalent to the Ising model. Substituting x_i = (1 - s_i) / 2 where s_i in {-1, +1} transforms a QUBO into an Ising Hamiltonian. D-Wave’s hardware is natively an Ising machine; the Ocean SDK handles the QUBO-to-Ising conversion transparently.

QUBO in D-Wave Ocean

from dimod import BinaryQuadraticModel

# Simple QUBO: minimize x1 + x2 - 2*x1*x2
Q = {(0, 0): 1, (1, 1): 1, (0, 1): -2}
bqm = BinaryQuadraticModel.from_qubo(Q)

# Run on D-Wave sampler
from dwave.system import EmbeddingComposite, DWaveSampler
sampler = EmbeddingComposite(DWaveSampler())
sampleset = sampler.sample(bqm, num_reads=100)
print(sampleset.first.sample)  # optimal binary assignment

See also

• Quantum Annealing
• Ising Model
• Adiabatic Quantum Computing