QUBO and Ising: how to write an optimisation problem for quantum annealing and QAOA, and how to choose a solver
Quantum annealing solves one kind of problem: find the bitstring that minimises a quadratic function of binary variables, written as a QUBO or, equivalently, as an Ising model. Most of the work is in writing that function, with every constraint turned into a penalty term. The same QUBO can then go to a quantum annealer, to QAOA on a gate-based computer or to a classical heuristic. On today's evidence the classical heuristic is often as good or better, so start with your own instances solved classically, and set any quantum solver against that baseline.
Updated
At a glance
- QUBO
- Minimise over bitstrings . The diagonal of holds the linear terms, because .
- Ising model
- The same problem in spins : minimise . A change of variable, , turns one into the other.
- What a quantum annealer does
- Starts in the ground state of a transverse field and slowly turns on the Ising problem, so that the state ends near the problem's lowest-energy bitstring
- Where constraints go
- Into the cost, as penalty terms that are zero when a constraint holds and positive when it does not
- What it costs in variables
- A travelling salesman tour of N cities needs [1] binary variables
- What the evidence says
- No general speed-up of quantum annealing over classical methods has been shown; one scaling advantage has been reported for approximate solutions on one family of spin glasses
- In eigenkit
- QUBO and Ising classes, energy(), to_ising(), brute_force() and a QAOA solver. No annealer, no simulated annealing and no D-Wave connection.
What a QUBO is, and why annealers take one
QUBO stands for quadratic unconstrained binary optimisation. The variables are bits, the cost is a sum of terms that involve at most two bits each, and nothing else is allowed: no constraints, no integers, no terms in three variables. That is a narrow format, but it is exactly the energy of an Ising model, the physics model of interacting spins, and an Ising energy is what a quantum annealer's hardware is built to minimise.
A surprising range of problems fits. Lucas wrote Ising formulations for all of Karp's 21 NP-complete problems, among them graph colouring, set cover and the Hamiltonian cycle, and for others such as the travelling salesman, with a number of spins at most cubic in the size of the problem[1]. Some problems are native: in MaxCut every edge already is a two-spin term. Most real problems are not. Their constraints become penalties, their integers become several bits, and the variable count grows, often quadratically. The tutorial by Glover, Kochenberger and Du is the standard reference for these tricks[2].
Writing the QUBO is solver-independent. The same matrix Q, or the same h and J of its Ising form, is the input of a quantum annealer, of QAOA, of simulated annealing and of quantum-inspired machines such as simulated bifurcation. That makes the formulation the part worth getting right first, and the part you can test without any quantum hardware.
How to write a problem as a QUBO
The same six moves apply to scheduling, selection, routing and partitioning problems. The example below them follows the moves on a four-item selection.
Choose the binary variables
One bit per yes or no decision: is item selected, is job at time slot , is city visited at position . An integer variable of range 0 to needs about bits in a binary expansion.
Write the objective with terms of at most two variables
Linear terms go on the diagonal of Q, pairwise terms above it. A term in three or more variables has to be reduced with extra variables and penalties, and that reduction has a cost in size and difficulty[7].
Turn each constraint into a penalty
An equality becomes , which is zero exactly when it holds. An inequality first gets slack bits that turn it into an equality[2]. Expanding the square gives linear and pairwise terms, because .
Choose the penalty weights
Too small, and an infeasible bitstring has a lower cost than every feasible one, so the solver returns it. Too large, and the objective's differences shrink next to the penalties; on analog hardware, which rescales every coefficient into a fixed range, they can drop below the noise. For the travelling salesman Lucas gives the condition 0 < B max(Wᵤᵥ) < A[1], where A weighs the constraints and B the distances.
Check the formulation on a small instance
On ten to twenty variables, try every bitstring. If the exact minimum is not the answer you expect, the QUBO is wrong, and no solver will fix it.
Solve, then check the answer
Send Q, or the Ising h and J, to the solver. Heuristics return low-energy bitstrings, not guaranteed optima, and a returned bitstring can still break a constraint, so decode it and check feasibility before you use it.
A selection problem as a QUBO, checked and solved in eigenkit
import numpy as np
from eigenkit.optimization import QAOA, QUBO
def pick_two(penalty):
value = np.array([5.0, 4.0, 3.0, 6.0]) # what each item is worth
clash = {(0, 3): 4.0, (1, 2): 1.0} # lost when both items of a pair are taken
k = 2 # take exactly two items
# minimise −value + clash + penalty * (sum(x) − k)², with x_i² = x_i
Q = np.diag(-value + penalty * (1 - 2 * k))
for i in range(4):
for j in range(i + 1, 4):
Q[i, j] = clash.get((i, j), 0.0) + 2 * penalty
return QUBO(Q, constant=penalty * k**2)
qubo = pick_two(penalty=10.0)
print(qubo.energy([1, 0, 0, 1])) # -7.0 the two most valuable items, which clash
print(qubo.brute_force()) # ((0, 1, 0, 1), -10.0) exact, from all 16 bitstrings
print(qubo.to_ising().energy([0, 1, 0, 1])) # -10.0 the same energy in the Ising form
result = QAOA(layers=2, random_state=0).solve(qubo)
print(result.best_bitstring, result.best_energy) # (0, 1, 0, 1) -10.0
print(pick_two(penalty=0.5).brute_force()) # ((0, 1, 1, 1), -11.5) three items: the penalty is too weakTaking the two most valuable items (0 and 3) costs a clash of 4, so the best pair is items 1 and 3. With a penalty of 0.5 the minimum takes three items: the constraint was written correctly and still lost to the objective. QAOA here runs on eigenkit's exact NumPy simulator.
How a quantum annealer solves the QUBO
Quantum annealing, proposed by Kadowaki and Nishimori, replaces the heat of simulated annealing with a transverse magnetic field[3]. The machine starts with the transverse field at full strength, whose ground state is the equal superposition of every bitstring, and slowly hands over to the Ising problem. If the change is slow enough, the state stays in the ground state throughout and ends in the problem's lowest-energy bitstring. How slow is slow enough depends on the smallest energy gap along the way, which is not known in advance and can shrink exponentially with problem size on hard instances[4].
Real annealers depart from that ideal. They are open systems, so heat and noise excite the state; their couplings are analog, with limited precision; and their qubits sit on a sparse graph. On D-Wave's Pegasus graph each qubit couples to at most 15[5] others, so a variable that needs more neighbours is spread over a chain of physical qubits forced to agree. In a 2022 benchmark, a D-Wave Advantage1.1 with 5,436[7] working qubits could take a fully connected problem of at most 128[7] variables, and its analog couplings had a precision of about 5 bits[7]. A dense QUBO therefore fits far fewer variables than the qubit count suggests, and coefficients that differ by less than the precision look the same.
QAOA is the gate-based counterpart. It applies the same two ingredients, the problem's cost and a transverse-field mixer, as alternating layers of gates with tuned angles rather than as a continuous schedule[9]. It runs on general-purpose quantum computers and on simulators, which is how eigenkit offers it. On hardware it faces the same connectivity issue in another form: on a Google processor, QAOA on problems that did not match the chip's graph got worse as the problems grew[10]. How connectivity differs between superconducting chips, ion traps and neutral atoms is on the qubit types comparison.
Choosing a solver for a QUBO
Every solver below takes the same matrix. Start from the top: the cheap classical options set the bar that the specialised ones have to clear on your instances.
| Solver | Good for | Watch for |
|---|---|---|
| Brute force | Checking a formulation on a small instance, about 20 variables at most | Time doubles with every variable |
| Mixed-integer solver on the original, constrained model | A proven optimum, or a bound on how far from one you are | The QUBO detour is not needed; run time can grow fast on dense quadratic costs |
| Simulated annealing or parallel tempering | The default heuristic baseline: free, on any CPU | The temperature schedule and the number of sweeps need tuning |
| Quantum annealer | Problems that fit its sparse graph; many low-energy samples per call | Embedding chains, analog noise, cloud-only access, and no general speed-up shown |
| Quantum-inspired Ising machines | Dense, large problems under a time limit: simulated bifurcation, digital annealers, coherent Ising machines | Results depend on the problem class; see the benchmark comparison |
| QAOA | Research and learning on gate-based hardware and simulators | Exact simulation stops at a few dozen qubits; hardware noise grows with depth |
Run it on a real QPU with EigenOrbit RouterThe QAOA circuit built from your QUBO, run on a gate-based QPU. Quantum annealers are a different kind of machine and are not part of it.In eigenkit: pip install "eigenkit[router]", then provider=RouterConfig(device=...) (docs).
Questions
What is QUBO?
QUBO, quadratic unconstrained binary optimisation, is the problem of finding the bitstring x that minimises xᵀQx, a sum of linear and pairwise terms over binary variables. It has no constraints of its own, so constraints are written into the cost as penalties. It is the input format of quantum annealers and of most quantum-inspired Ising machines.
What is quantum annealing?
Quantum annealing is a heuristic optimisation method that prepares a quantum system in the easy ground state of a transverse field and slowly changes the system's energy into that of an Ising problem. If the change is slow enough, the system ends near the problem's lowest-energy state, which is read out as a bitstring. Commercial quantum annealers are built by D-Wave.
What is the difference between QUBO and Ising?
They are the same problem in different variables. QUBO uses bits that are 0 or 1; the Ising model uses spins that are +1 or −1, with linear fields h and couplings J. The substitution x = (1 − s)/2 converts one into the other exactly, with a constant offset. In eigenkit, QUBO.to_ising() does the conversion.
How do you add constraints to a QUBO?
As penalty terms. An equality constraint such as choosing exactly k items becomes a penalty weight times the square of (sum of x minus k), which is zero only when the constraint holds. Inequalities need extra slack bits first. The weight has to be large enough that breaking a constraint never pays, but not so large that it swamps the objective.
Is quantum annealing better than classical optimisation?
Not in general. Benchmarks since 2014 have found no general speed-up, and on some problem classes a quantum annealer scaled worse than classical heuristics. A 2025 study reported a scaling advantage for approximate solutions on one family of 2D spin glasses. For a real problem, compare against simulated annealing and a mixed-integer solver on your own instances.
Can eigenkit run quantum annealing?
No. eigenkit has no quantum annealer, no simulated annealing and no D-Wave connection. It builds and checks QUBO and Ising problems, converts between them, finds the exact answer by brute force for small problems and solves them with QAOA, which uses the same formulation on gate-based simulators and hardware.
Sources
- A. Lucas. Ising formulations of many NP problems. Frontiers in Physics 2, 5, 2014. arXiv:1302.5843.
- F. Glover, G. Kochenberger, Y. Du. Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models. 4OR 17, 335–371, 2019. arXiv:1811.11538.
- T. Kadowaki, H. Nishimori. Quantum annealing in the transverse Ising model. Physical Review E 58, 5355, 1998. arXiv:cond-mat/9804280.
- E. Farhi, J. Goldstone, S. Gutmann, M. Sipser. Quantum computation by adiabatic evolution. arXiv preprint, 2000. arXiv:quant-ph/0001106.
- K. Boothby, P. Bunyk, J. Raymond, A. Roy. Next-generation topology of D-Wave quantum processors. arXiv preprint, 2020. arXiv:2003.00133.
- T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, M. Troyer. Defining and detecting quantum speedup. Science 345, 420, 2014. arXiv:1401.2910.
- M. Kowalsky, T. Albash, I. Hen, D. A. Lidar. 3-regular 3-XORSAT planted solutions benchmark of classical and quantum heuristic optimizers. Quantum Science and Technology 7, 025008, 2022. arXiv:2103.08464.
- H. Munoz-Bauza, D. A. Lidar. Scaling advantage in approximate optimization with quantum annealing. Physical Review Letters 134, 160601, 2025. arXiv:2401.07184.
- E. Farhi, J. Goldstone, S. Gutmann. A quantum approximate optimization algorithm. arXiv preprint, 2014. arXiv:1411.4028.
- M. P. Harrigan, K. J. Sung, M. Neeley, et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics 17, 332–336, 2021. arXiv:2004.04197.
Run it yourself with eigenkit
eigenkit is EigenOrbit's open-source Python library: write a circuit once, run it on any simulator or QPU, and test it against a classical baseline on your own data before you invest in it or rule it out.
$ pip install eigenkit