Skip to content

Chapter 6: Quantum Optimisation & Annealing for ML

Many machine-learning problems hide a discrete optimisation inside — choosing features, clusters, weak learners or binary weights. This chapter shows how such tasks become QUBO and Ising models, how quantum annealers such as D-Wave's Advantage and Advantage2 attack them, and how gate-model algorithms like QAOA and its variants — and the VQE seen as a learning problem — do the same on today's processors. It ends with the habits that matter most: fair benchmarking against strong classical and quantum-inspired solvers, and realistic expectations based on published comparisons.

6.1 Optimisation in ML & Where Quantum Might Fit

Almost every machine-learning task is an optimisation problem: training minimises a loss, feature selection picks the best subset, clustering finds the best grouping, and tuning searches over settings. Most training is smooth (continuous) and handled superbly by gradient descent on GPUs. Quantum optimisers target the discrete, combinatorial parts — choosing subsets, assignments or binary weights — where problems can be NP-hard.

Two kinds of optimisation in ML

Continuous training Combinatorial ML tasks
Examples network weights, regression feature selection, clustering, binary nets
Landscape smooth, gradients available discrete, no gradients
Best classical tools SGD, Adam, L-BFGS on GPUs MIP solvers, annealing, tabu search
Complexity often tractable in practice NP-hard in general
Quantum candidates few (see fault-tolerant chapter) annealing, QAOA, Grover-type search

Quantum optimisers aim at the right-hand column, not at training large networks.

Think of it like…

Training a neural network is like rolling a ball downhill on a smooth landscape — easy when you can feel the slope. Combinatorial problems are like finding the best setting of thousands of on/off switches, where there is no slope to follow.

Real-world example

The fictional insurer Harbourline wants a fraud model using the best 20 of 300 features. There are about 7.5 × 10³⁰ possible subsets, so trying them all is impossible. Its team can use greedy selection, L1 regularisation, a mixed-integer solver, or write the task as a QUBO for a quantum annealer or QAOA — and must benchmark every option fairly.

How it works

  1. Identify the decision variables: continuous weights, or discrete choices such as bits, assignments and orderings.
  2. Classify the problem: convex or non-convex continuous, or combinatorial (NP-hard in general).
  3. Try strong classical tools first: gradient methods, mixed-integer solvers and metaheuristics.
  4. If the core is a binary quadratic problem, write it as a QUBO or Ising model for quantum or quantum-inspired solvers.
  5. Compare solution quality and time-to-solution against tuned classical baselines.

Who uses it

ML engineers, operations researchers, and quantum application scientists at banks, logistics firms, manufacturers and car makers who experiment with quantum optimisation.

Key takeaway

Remember: quantum computers are not expected to solve NP-hard problems efficiently in general; the hope is for better heuristics or polynomial speed-ups on specific problem families.

Going deeper

  • Training deep networks is non-convex continuous optimisation at a scale of 10⁹-10¹² parameters using first-order methods; no quantum optimiser comes anywhere near that scale.
  • Combinatorial ML sub-problems — feature selection, k-medoids clustering, L0-penalised sparse models, binary or quantised network training, graph partitioning, job scheduling — map naturally to binary variables.
  • NP-complete problems are not believed to lie in BQP, so quantum optimisers are heuristics or offer at most polynomial (often quadratic) speed-ups for generic search.
  • Approximation guarantees set the bar: Goemans-Williamson's 0.878 ratio for MaxCut (1995) is the best possible for efficient algorithms if the Unique Games Conjecture holds.
  • Useful metrics include gap to the optimum or best-known value, time-to-solution at a target success probability, and total cost including encoding, queueing and post-processing.
  • Abbas et al.'s 46-author perspective (Nature Reviews Physics, 2024) calls quantum optimisation promising but unproven, and urges rigorous benchmarks against state-of-the-art classical solvers.

Common mistakes & misconceptions

  • Thinking quantum computers solve NP-complete problems in polynomial time; there is no evidence they can.
  • Turning continuous training into a QUBO by discretising weights and then claiming a speed-up; gradient methods are usually far better.
  • Benchmarking against brute force or untuned heuristics instead of modern solvers such as Gurobi or well-tuned simulated annealing.

Try it: How fast feature-subset counts explode (plain Python)

from math import comb
for k in (5, 10, 20):
    print(f"choose {k} of 300 features: {comb(300, k):.2e} subsets")

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
Loss minimisation
Machine-learning basics · Concept · Current · Beginner
Training means finding parameters that minimise average error on data; usually smooth and solved with gradient methods. Fitting logistic regression to a million insurance claims with L-BFGS takes seconds on a laptop.
Combinatorial optimisation
Operations research · Concept · Current · Beginner
Choosing the best option from a finite but astronomically large set of discrete choices — subsets, orderings or assignments. Assigning 50 vans to 2,000 orders has more combinations than atoms in the universe, yet good heuristics find near-optimal plans.
NP-hardness
Complexity theory (Cook 1971; Karp 1972) · Concept · Current · Intermediate
Problems at least as hard as every problem in NP; no efficient exact algorithm is known for them, classical or quantum. MaxCut, the travelling salesperson problem and general QUBO are NP-hard, so no solver is expected to crack every instance.
Feature selection as subset optimisation
Machine-learning practice · Technique · Current · Beginner
Picking a small subset of input features that keeps predictive power while reducing noise, cost and overfitting. Choosing 20 of 300 fraud features with greedy forward selection, L1 regularisation, or a QUBO balancing relevance and redundancy.
Clustering as optimisation
Machine-learning practice · Technique · Current · Beginner
Grouping points to minimise within-cluster distances; k-means is continuous-ish, while k-medoids and balanced clustering are discrete. Choosing 10 warehouse sites (medoids) among 500 candidate towns is a binary decision problem.
Binary and quantised neural networks
Courbariaux et al. 2016; Rastegari et al. 2016 · Model · Current · Intermediate
Networks whose weights are restricted to ±1 or a few bits, cheaper on edge hardware; training them is a discrete problem. A ±1-weight keyword spotter runs on a microcontroller; straight-through gradient estimators are the usual classical training trick.
Hyperparameter optimisation
Bergstra & Bengio 2012; Optuna · Technique · Current · Beginner
Searching learning rates, depths and other settings; done with random search or Bayesian optimisation, not quantum hardware. Optuna tries 100 configurations of a gradient-boosting model overnight on a small cluster.
Approximation ratio
Approximation algorithms · Metric · Current · Intermediate
A heuristic's solution value divided by the optimum; the key quality metric for QAOA and other approximate optimisers. A cut of 87 edges when the maximum cut is 100 has approximation ratio 0.87.
Time-to-solution (TTS)
Rønnow et al. 2014 · Metric · Current · Intermediate
Expected time to find the optimum (or a target quality) with given confidence, accounting for repeated runs. If one 20-μs anneal succeeds with probability 0.01, reaching 99% confidence needs 459 anneals — about 9 ms.
Goemans-Williamson algorithm
Goemans & Williamson 1995 · Algorithm · Current · Intermediate
Classical SDP-based MaxCut algorithm with a guaranteed 0.878 approximation ratio — the bar quantum optimisers must beat. Solving the SDP for a 1,000-node graph and rounding with a random hyperplane guarantees at least 87.8% of the maximum cut in expectation.
'Challenges and opportunities in quantum optimization'
Abbas et al. 2024 (Nature Reviews Physics) · Paper · Current · Beginner
Large community review of quantum optimisation algorithms, hardware results and benchmarking needs, stressing fair classical comparisons. A good first reading: it surveys QAOA, annealing and variational methods and lists open problems for students.
Gradient-based optimisers
Robbins & Monro 1951; Kingma & Ba 2015 (Adam) · Optimiser · Current · Beginner
SGD, Adam and L-BFGS: first- or quasi-second-order methods that dominate continuous ML training. Adam trains a 100-million-parameter transformer on GPUs; no quantum optimiser competes at this scale.

6.2 QUBO & Ising Formulations

A QUBO (quadratic unconstrained binary optimisation) problem asks for binary variables xᵢ ∈ {0, 1} that minimise xᵀQx. The Ising model is the same thing written with spins sᵢ ∈ {−1, +1}, fields hᵢ and couplings Jᵢⱼ. These are the native language of quantum annealers and the usual input for QAOA, so a problem must be translated into this form first.

Nodes carry linear weights; edges carry pairwise couplings the solver must balance.
A QUBO is a weighted graph. Nodes carry linear weights; edges carry pairwise couplings the solver must balance.

Think of it like…

Picture a group of people each voting yes or no: each person has a personal preference (the linear term), and pairs of friends or rivals gain or lose points depending on whether they agree (the quadratic term).

Real-world example

Sofia at the fictional Verdant Logistics wants to split six depots into two balanced regions while minimising cross-region traffic. She gives each depot a binary variable, adds traffic between pairs as quadratic terms, and adds a penalty P·(Σxᵢ − 3)² to enforce three depots per region. The result is a 6×6 Q matrix ready for an annealer or QAOA.

How it works

  1. Choose binary decision variables xᵢ (or spins sᵢ = 2xᵢ − 1).
  2. Write the objective as linear plus pairwise terms.
  3. Turn constraints into quadratic penalties, for example P·(Σxᵢ − k)².
  4. Collect coefficients into an upper-triangular Q matrix, or into fields h and couplings J.
  5. Choose the penalty weight P: large enough to enforce constraints, small enough not to swamp the objective.
  6. Hand the model to a solver — annealer, QAOA, simulated annealing or a MIP solver.

Who uses it

Quantum application developers, operations researchers, and anyone preparing problems for D-Wave, QAOA or Ising-machine hardware.

Key takeaway

Memorise the mapping x = (1 + s)/2: it converts a QUBO into an Ising model and back, shifting linear terms and adding a constant offset.

Going deeper

  • QUBO energy is E(x) = Σᵢ Qᵢᵢxᵢ + Σᵢ<ⱼ Qᵢⱼxᵢxⱼ and Ising energy E(s) = Σhᵢsᵢ + ΣJᵢⱼsᵢsⱼ; finding Ising ground states on general graphs is NP-hard (Barahona, 1982).
  • Lucas (Frontiers in Physics, 2014) gave Ising formulations of Karp's NP-complete problems and many more, and Glover, Kochenberger & Du (4OR, 2019) wrote a practical QUBO modelling tutorial.
  • Inequality constraints need slack variables, usually binary-encoded integers: a constraint Σwᵢxᵢ ≤ C adds about log₂C extra bits, increasing qubit count.
  • Integer variables can be encoded one-hot (k bits plus a penalty) or in binary (fewer bits but uneven coefficients), and the choice changes the precision demanded from hardware.
  • Higher-order terms such as xᵢxⱼxₖ are reduced to quadratic form with auxiliary variables and penalties (Rosenberg, 1975), again adding qubits.
  • On D-Wave Advantage systems, fields and couplings must fit ranges such as h ∈ [−4, 4] and J ∈ [−1, 1], so badly scaled QUBOs lose detail in hardware noise.

Common mistakes & misconceptions

  • Picking penalty weights blindly: too small and constraints break; too large and the objective is flattened, hurting solution quality.
  • Forgetting that slack variables and one-hot encodings can multiply the number of qubits several times.
  • Mixing the QUBO {0, 1} and Ising {−1, +1} conventions in code, which silently flips signs and offsets.

Try it: Build a QUBO, view it as an Ising model and solve it with D-Wave's open-source Ocean tools

# pip install dimod dwave-samplers
import dimod
from dwave.samplers import SimulatedAnnealingSampler
Q = {(0, 0): -1, (1, 1): -1, (2, 2): -1, (0, 1): 2, (1, 2): 2, (0, 2): 2}   # 'pick exactly one of three'
bqm = dimod.BinaryQuadraticModel.from_qubo(Q)
print(bqm.to_ising())                    # the same problem as (h, J, offset)
best = SimulatedAnnealingSampler().sample(bqm, num_reads=50).first
print(best.sample, best.energy)          # one variable set to 1, energy -1

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
QUBO
Hammer & Rudeanu 1968; Kochenberger et al. 2014 (survey) · Math · Current · Beginner
Quadratic unconstrained binary optimisation: minimise xᵀQx over binary vectors; the input format for annealers and many quantum optimisers. A three-variable QUBO with diagonal −1 and off-diagonal +2 rewards switching on exactly one variable.
Ising model
Ising 1925 · Math · Current · Beginner
Spins sᵢ = ±1 with energy Σhᵢsᵢ + ΣJᵢⱼsᵢsⱼ; physically natural and mathematically equivalent to a QUBO. A positive J between two spins penalises them for agreeing, encouraging opposite values — the basis of the MaxCut encoding.
QUBO-Ising conversion
Standard substitution · Technique · Current · Beginner
Substituting x = (1 + s)/2 turns a QUBO into an Ising model plus a constant offset, and vice versa. dimod's bqm.to_ising() returns (h, J, offset), so Sofia can submit whichever form a solver expects.
Penalty method
Optimisation practice · Technique · Current · Beginner
Encodes constraints as squared penalty terms added to the objective, so violating solutions cost extra energy. 'Exactly one of x1, x2, x3' becomes P·(x1 + x2 + x3 − 1)², expanded into linear and quadratic terms.
Slack variables
Optimisation practice · Technique · Current · Intermediate
Extra binary variables that turn inequality constraints into equalities that penalties can enforce. A knapsack limit 'weight ≤ 15' needs four binary slack bits representing values 0-15.
One-hot encoding
Optimisation practice · Encoding · Current · Beginner
Represents a choice among k options with k bits, exactly one of which is 1, enforced by a penalty. Assigning each of 100 jobs to one of 4 machines needs 400 variables plus 100 one-hot penalty terms.
MaxCut
Karp 1972; Goemans & Williamson 1995 · Benchmark · Current · Beginner
Split a graph's nodes into two sets to maximise edges between them; the classic test problem for QAOA and annealers. In Ising form you minimise Σ sᵢsⱼ over edges; every edge that is cut contributes −1.
'Ising formulations of many NP problems'
Lucas 2014 (Frontiers in Physics) · Paper · Current · Intermediate
Influential catalogue showing how to write colouring, travelling salesperson, set cover, partitioning and more as Ising models. Its TSP encoding uses N² binary variables x_{v,t}, meaning 'city v is visited at step t'.
QUBO modelling tutorial
Glover, Kochenberger & Du 2019 (4OR) · Paper · Current · Intermediate
Practical tutorial on building QUBO models from real constraints, with advice on penalties and many worked examples. Shows how a set-packing problem becomes a QUBO with quadratic penalties between conflicting sets.
dimod
D-Wave (open source) · Library · Current · Intermediate
Python library for binary quadratic models, constrained quadratic models and sample sets; the foundation of D-Wave's Ocean SDK. BinaryQuadraticModel.from_qubo(Q) builds a model, and ExactSolver() brute-forces small ones (up to about 20 variables) for checking.
Higher-order reduction
Rosenberg 1975 · Technique · Current · Advanced
Replaces a cubic term such as x1x2x3 with an auxiliary bit y = x1x2 plus a penalty enforcing that equality. A 3-SAT clause produces cubic terms; each reduction adds one variable and some penalty couplings.
Constrained quadratic model (CQM)
D-Wave · Concept · Current · Intermediate
Model format holding an objective plus explicit constraints, so hybrid solvers handle constraints without hand-tuned penalties. Sofia writes 'number of depots in region A == 3' directly as a CQM constraint for D-Wave's hybrid CQM solver.
PyQUBO
Recruit Communications (open source) · Library · Current · Intermediate
Python library for writing QUBO and Ising models symbolically, with named constraints and tunable placeholders for penalty weights. Write H = (x1 + x2 − 1)**2 symbolically, compile it, and export a QUBO dictionary for any solver.

6.3 Writing ML Tasks as QUBOs

Several machine-learning tasks can be written as QUBOs: choosing a subset of features, assigning points to clusters, picking which weak classifiers to combine (boosting), or training models with binary weights. Once in QUBO form they can run on annealers, QAOA or classical QUBO solvers — though the quantum step is usually one small piece of a bigger, mostly classical workflow.

The QUBO is a common interface: any solver below can attack any task above.
From ML task to solver. The QUBO is a common interface: any solver below can attack any task above.

Think of it like…

Like translating a recipe into a universal cooking language: once it is written in 'QUBO', any compatible kitchen — quantum or classical — can cook it.

Real-world example

Ahmed at the fictional Meridian Health wants a compact, interpretable sepsis model. He builds a QUBO where each bit switches one of 40 simple decision stumps on or off; the objective rewards matching the labels and penalises using too many stumps. This is the QBoost idea first explored by Google and D-Wave researchers (Neven et al., 2008).

How it works

  1. Choose the binary decision: feature on/off, point-to-cluster, weak classifier on/off, or a weight bit.
  2. Write the ML loss — squared error, correlation or distance — as a quadratic function of those bits.
  3. Add regularisation (such as a sparsity term) as linear terms and constraints as penalties.
  4. Solve the QUBO with an annealer, QAOA or a classical solver.
  5. Decode the bits into a model and validate it on held-out data as usual.

Who uses it

Applied quantum scientists at consultancies, research institutes and industrial labs, and ML researchers exploring alternative training methods.

Key takeaway

Squared-error losses become QUBOs naturally: expanding (Σ wᵢhᵢ(x) − y)² over binary wᵢ gives exactly linear plus pairwise terms.

Going deeper

  • QBoost (Neven, Denchev, Rose & Macready, 2008; extended 2012) selects a sparse combination of weak classifiers by minimising squared loss plus an L0-style penalty — a direct QUBO tested on early D-Wave hardware.
  • Mott, Job, Vlimant, Lidar & Spiropulu (Nature, 2017) used a QBoost-style annealing approach for Higgs-boson classification; it held up well with small training sets but did not beat boosted trees or neural networks with more data.
  • Willsch, Willsch, De Raedt & Michielsen (Computer Physics Communications, 2020) trained kernel SVMs on a D-Wave annealer by encoding dual coefficients with a few bits each and ensembling low-energy solutions.
  • Feature-selection QUBOs typically balance relevance (correlation or mutual information with the label) against redundancy between features, plus a cardinality penalty for choosing exactly k features.
  • Clustering formulations use one-hot bits x_{i,c} (point i in cluster c) with a penalty per point; N points and K clusters need N·K variables, quickly exceeding hardware capacity.
  • Most published studies use tens to a few hundred binary variables per QUBO — far below real ML sizes — so decomposition or hybrid solvers are needed for anything realistic.

Common mistakes & misconceptions

  • Discretising continuous weights into many bits each: qubit counts explode and limited coefficient precision on annealers degrades results.
  • Reporting the lowest QUBO energy on training data instead of test accuracy; the ML goal is generalisation, not energy.
  • Skipping classical baselines such as L1-regularised regression or greedy selection, which often match QUBO-based selection.

Try it: QUBO feature selection on a scikit-learn dataset (relevance minus redundancy, pick about 5)

# pip install dimod dwave-samplers scikit-learn
import numpy as np, dimod
from dwave.samplers import SimulatedAnnealingSampler
from sklearn.datasets import load_breast_cancer
X, y = load_breast_cancer(return_X_y=True)
R = np.abs(np.corrcoef(np.c_[X, y].T))          # |correlation| matrix including the label
rel, red = R[-1, :-1], R[:-1, :-1]              # relevance to label, redundancy between features
k, alpha, P = 5, 0.5, 2.0                       # target size, redundancy weight, penalty weight
n = len(rel); bqm = dimod.BinaryQuadraticModel("BINARY")
for i in range(n):
    bqm.add_linear(i, -rel[i] + P * (1 - 2 * k))          # from P*(sum x - k)^2
    for j in range(i + 1, n):
        bqm.add_quadratic(i, j, alpha * red[i, j] + 2 * P)
best = SimulatedAnnealingSampler().sample(bqm, num_reads=100).first.sample
print("chosen features:", [i for i, v in best.items() if v])

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
QBoost
Neven, Denchev, Rose & Macready 2008 · Algorithm · Research · Intermediate
Boosting variant that chooses a sparse subset of weak classifiers by solving a QUBO with squared loss plus a sparsity penalty. Early Google-D-Wave experiments used it to combine simple weak classifiers into an image detector.
Higgs classification with annealing
Mott et al. 2017 (Nature) · Paper · Research · Intermediate
Quantum-annealing-trained classifier for Higgs-boson events, robust with small training sets but not better than classical methods with abundant data. Physicists compared it with boosted decision trees and deep neural networks on the same simulated collision events.
SVM training on a quantum annealer
Willsch, Willsch, De Raedt & Michielsen 2020 (CPC) · Paper · Research · Intermediate
Encodes kernel-SVM dual variables as small binary numbers in a QUBO and combines several low-energy solutions into an ensemble. Using a few bits per training point limited each QUBO to a few dozen training points on the annealer.
QUBO feature selection
Mücke et al. 2023 (Quantum Machine Intelligence) · Technique · Research · Intermediate
Selects k features by minimising redundancy minus relevance, with a cardinality penalty — a direct QUBO. On a 30-feature medical dataset, the QUBO picks five features with high label correlation and little mutual overlap.
Clustering QUBO
Optimisation literature · Technique · Research · Intermediate
One-hot variables per point and cluster, single-membership penalties, and pairwise distance costs for points sharing a cluster. 200 points into 3 clusters needs 600 densely coupled variables — too many for direct embedding on current annealers.
k-medoids QUBO
Optimisation literature · Technique · Research · Intermediate
Chooses k representative points by rewarding medoids that are spread out and close to many points, with a cardinality penalty. Choosing 10 of 500 store locations as cluster centres for a retailer's regional analysis.
Binary-weight model training
Optimisation literature · Technique · Research · Intermediate
Trains models with ±1 or few-bit weights by writing the squared loss as a QUBO over the weight bits. A 20-input binary perceptron becomes a 20-variable QUBO built from the data matrices XᵀX and Xᵀy.
Annealing for DNA-binding classification
Li, Di Felice, Rohs & Lidar 2018 (npj QI) · Paper · Research · Intermediate
Annealing-based classifier for transcription-factor binding data, competitive with classical methods on small training sets. A slight edge with very small training sets disappeared as data grew — a recurring pattern in this field.
Ensemble-selection QUBO
Optimisation literature · Technique · Research · Intermediate
Chooses a subset of already-trained models that are individually accurate but make different mistakes, rewarding accuracy and penalising correlated errors. From 50 trained gradient-boosting models, the QUBO picks 8 whose errors overlap least, forming a compact ensemble.
Graph-partitioning QUBO
Ushijima-Mwesigwa, Negre & Mniszewski 2017 · Technique · Research · Intermediate
Splits a graph into balanced parts with few cut edges; used for community detection in network data. Partitioning a 1,000-node collaboration network into communities with a hybrid annealing solver.
Hybrid quantum-classical ML pipeline
Industry practice · Concept · Current · Beginner
Only the discrete core, such as a feature subset, goes to the quantum solver; data preparation, training and validation stay classical. Ahmed's pipeline: pandas preprocessing, QUBO feature selection on an annealer, then scikit-learn logistic regression on chosen features.

6.4 Quantum Annealing: How It Works

Quantum annealing starts the qubits in the easy ground state of a 'transverse field' that puts every qubit in superposition, then slowly turns that field down while turning the problem's Ising energy up. If the change is slow enough (the adiabatic theorem), the system stays near its lowest-energy state and ends in a low-energy solution. Real devices are noisy and fast, so in practice they act as heuristic samplers.

Thousands of these short runs are sampled for every problem.
One quantum anneal. Thousands of these short runs are sampled for every problem.

Think of it like…

Like slowly cooling molten glass in a mould: start with everything soft and spread out, then gradually 'freeze' into the shape the mould (the problem) favours — with quantum tunnelling letting it slip through thin walls instead of climbing over them.

Real-world example

Jun at the fictional Kestrel Robotics runs a 500-variable scheduling QUBO on a D-Wave annealer. Each anneal lasts 20 microseconds; she requests 1,000 reads, receives a histogram of solutions and keeps the lowest-energy valid schedule. QPU time is well under a second, though network and queueing time add more.

How it works

  1. Encode the problem Hamiltonian H_P = Σhᵢσᶻᵢ + ΣJᵢⱼσᶻᵢσᶻⱼ on qubits and couplers.
  2. Start all qubits in the ground state of the driver H_D = −Σσˣᵢ, an equal superposition of all bitstrings.
  3. Sweep the schedule H(s) ∝ −A(s)·H_D + B(s)·H_P from s = 0 to 1, lowering A and raising B.
  4. At the end, measure every qubit to read out a spin configuration.
  5. Repeat hundreds or thousands of times and keep the best samples.

Who uses it

Users of annealing hardware in logistics, scheduling and finance, and physicists studying spin glasses and quantum phase transitions.

Key takeaway

Know the adiabatic condition: required run time grows roughly as 1/Δ², where Δ is the minimum energy gap — exponentially small gaps make annealing exponentially slow.

Going deeper

  • Kadowaki & Nishimori (Physical Review E, 1998) proposed quantum annealing in the transverse-field Ising model; Farhi, Goldstone, Gutmann & Sipser (2000) formulated adiabatic quantum computation.
  • Aharonov et al. (SIAM Journal on Computing, 2007) proved universal adiabatic computation equivalent to the circuit model, but that needs non-stoquastic Hamiltonians that today's commercial annealers do not provide.
  • D-Wave's schedule is H(s) = −A(s)/2·Σσˣ + B(s)/2·(Σhᵢσᶻ + ΣJᵢⱼσᶻσᶻ); A(s) starts at several gigahertz (times Planck's constant) and falls towards zero while B(s) rises.
  • The default anneal time on D-Wave systems is 20 μs and can be set from about a microsecond to milliseconds; a separate fast-anneal mode supports far shorter, nanosecond-scale anneals.
  • Real annealers are open systems at around ten to twenty millikelvin; thermal noise means outputs often resemble low-temperature Boltzmann samples rather than guaranteed ground states.
  • Stoquastic Hamiltonians, like the transverse-field Ising model, can often be simulated by quantum Monte Carlo — one reason experts doubt exponential speed-ups from today's annealers.

Common mistakes & misconceptions

  • Believing annealers always return the optimum: they are heuristic samplers, so take many reads and check quality.
  • Equating quantum annealing with gate-model quantum computing: today's annealers cannot run Shor's algorithm or general circuits.
  • Assuming slower anneals are always better: noise and thermal effects mean longer anneals often help less than expected.

Try it: Watch the energy gap change during a two-qubit anneal (NumPy)

import numpy as np
X = np.array([[0, 1], [1, 0]]); Z = np.diag([1, -1]); I = np.eye(2)
k = np.kron
HD = -(k(X, I) + k(I, X))                     # transverse-field driver
HP = k(Z, Z) + 0.5 * k(Z, I) - 0.2 * k(I, Z)  # a tiny Ising problem
for s in np.linspace(0, 1, 6):
    e = np.linalg.eigvalsh((1 - s) * HD + s * HP)
    print(f"s={s:.1f}  ground={e[0]:+.3f}  gap={e[1] - e[0]:.3f}")

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
Quantum annealing
Kadowaki & Nishimori 1998 · Algorithm · Current · Beginner
Heuristic that slowly lowers a transverse field while raising a problem Hamiltonian, so tunnelling helps reach low-energy solutions. D-Wave systems run thousands of 20-μs anneals per problem and return the lowest-energy samples.
Adiabatic quantum computation
Farhi, Goldstone, Gutmann & Sipser 2000 · Concept · Research · Intermediate
Computation by slowly evolving a Hamiltonian's ground state; the universal version is equivalent to circuit-model quantum computing. Aharonov et al. proved equivalence using non-stoquastic Hamiltonians; commercial annealers implement only a restricted stoquastic version.
Adiabatic theorem
Born & Fock 1928 · Theorem · Current · Intermediate
A system stays in its instantaneous ground state if the Hamiltonian changes slowly compared with the inverse square of the gap. Shrinking the minimum gap from 1 to 0.01 can lengthen the required anneal by a factor of around ten thousand.
Transverse-field driver
Kadowaki & Nishimori 1998 · Concept · Current · Beginner
The Hamiltonian −Σσˣ whose ground state is an equal superposition; it enables tunnelling and is switched off during the anneal. At s = 0 every qubit is in |+⟩, so all 2ᴺ spin configurations have equal amplitude.
Annealing schedule A(s), B(s)
D-Wave documentation · Concept · Current · Intermediate
Time-dependent strengths of the driver and problem terms; vendors publish the curves for each device. Changing the anneal time from 20 μs to 200 μs stretches the same schedule ten times longer.
Minimum gap and avoided crossings
Adiabatic quantum computing theory · Concept · Current · Advanced
The smallest separation between ground and first excited energies during the anneal; exponentially small gaps imply exponentially long runs. Some crafted instances show first-order transitions whose gaps shrink exponentially with problem size.
Freeze-out
Amin 2015 (PRA) · Concept · Current · Advanced
Point late in the anneal where the driver becomes too weak to change the state; samples reflect conditions at that point. Studies model annealer output as a Boltzmann distribution at the freeze-out point rather than at the end of the anneal.
Reverse annealing
D-Wave (feature since 2017) · Technique · Current · Intermediate
Starts from a chosen classical state, partly re-introduces the transverse field, then anneals forward — a quantum local search. Refining a good schedule from a greedy heuristic by reverse annealing to s = 0.6 and back.
Anneal pauses and offsets
D-Wave · Technique · Current · Advanced
Holding the schedule at a fixed point, or shifting individual qubits' timing, to improve sampling or balance chain dynamics. Pauses near the freeze-out region have raised ground-state probabilities in some published studies.
Stoquastic Hamiltonian
Bravyi, DiVincenzo, Oliveira & Terhal 2008 · Concept · Current · Advanced
A Hamiltonian with non-positive off-diagonal elements; its ground states avoid the sign problem, so quantum Monte Carlo often simulates it. The transverse-field Ising model is stoquastic, making path-integral Monte Carlo a natural classical competitor for annealers.
Quantum tunnelling
Quantum mechanics · Concept · Current · Beginner
Quantum systems passing through tall, thin energy barriers instead of climbing over them, which can help escape local minima. Denchev et al. (2016) built instances where tunnelling through narrow barriers gave the annealer a large edge over simulated annealing.
Coherent vs open-system annealing
King et al. 2022 · Concept · Current · Intermediate
Ideal annealing is coherent; real devices interact with their environment, so slow anneals thermalise while very fast anneals stay coherent. D-Wave fast-anneal experiments matched closed-system quantum predictions on chains and spin glasses — covered later in this chapter.

6.5 Running on a Real Annealer: Topology, Embedding & Tuning

Real annealers do not connect every qubit to every other. To run a QUBO you must 'embed' it: represent each logical variable by a chain of physical qubits tied together strongly so they act as one. You also tune chain strength, number of reads, anneal time and coefficient scaling — choices that strongly affect the answers you get.

D-Wave qubit topologies

Chimera Pegasus Zephyr
System D-Wave 2000Q and earlier Advantage (2020) Advantage2 (2025)
Qubits up to ~2,000 5,000+ 4,400+
Couplers per qubit 6 15 20
Role in 2026 legacy studies established workhorse newest generation

Richer connectivity means shorter chains and larger embeddable problems.

Think of it like…

Like seating guests at a long banquet table when some must talk to many others: you give a talkative guest several neighbouring seats (a chain) so they can reach everyone, and make sure those copies always agree.

Real-world example

Olga at the fictional Tessera Bank embeds a fully connected 120-variable portfolio QUBO on an Advantage system. The embedding tool finds chains of several qubits per variable, using over a thousand physical qubits. With weak chain strength many samples have broken chains; raising it fixes breaks but blurs the objective, so she settles on a value near the problem's coefficient scale.

How it works

  1. Inspect the hardware graph: Pegasus on Advantage, Zephyr on Advantage2.
  2. Find a minor embedding that maps each variable to a connected chain of qubits (minorminer or clique embedding).
  3. Set chain strength so chains rarely break without dwarfing the problem's coefficients.
  4. Scale coefficients into the allowed h and J ranges; choose anneal time and number of reads.
  5. Optionally apply spin-reversal transforms to average out hardware biases.
  6. Unembed: resolve broken chains, e.g. by majority vote, then polish with a quick classical local search.

Who uses it

Quantum application engineers and researchers who submit problems directly to D-Wave QPUs.

Key takeaway

Dense problems embed with long chains, so a fully connected problem uses many more physical qubits than variables — check the embedding before blaming the hardware.

Going deeper

  • Minor embedding (Choi, 2008 and 2011) maps a problem graph into the hardware graph as a graph minor; the heuristic of Cai, Macready & Roy (2014) underlies D-Wave's open-source minorminer.
  • Chimera (6 couplers per qubit) powered the D-Wave 2000Q; Pegasus (15 per qubit) powers Advantage with 5,000+ qubits; Zephyr (20 per qubit) powers Advantage2 with 4,400+ qubits, generally available since May 2025.
  • Ocean's EmbeddingComposite sets chain strength with a heuristic based on the problem's coefficients (uniform torque compensation) unless you override it, and reports a chain-break fraction for every sample.
  • Integrated control errors — small deviations of realised h and J from programmed values — limit effective precision, so problems relying on fine coefficient differences suffer.
  • Spin-reversal transforms (gauges) flip the encoding of random qubits to cancel systematic biases; splitting reads across several gauges usually gives more reliable statistics.
  • QPU access time per problem — programming plus sampling — is typically a fraction of a second; network latency and queueing come on top and matter for end-to-end comparisons.

Common mistakes & misconceptions

  • Ignoring chain breaks: majority-vote repairs can silently produce poor or invalid solutions.
  • Comparing problem size with qubit count: a 5,000-qubit chip embeds only on the order of 100-200 fully connected variables.
  • Over-scaling coefficients so that most terms are squashed to tiny values comparable to hardware noise.

Try it: Embed a fully connected 20-variable problem into a small Pegasus graph

# pip install minorminer dwave-networkx networkx
import networkx as nx, minorminer, dwave_networkx as dnx
source = nx.complete_graph(20)                 # fully connected 20-variable QUBO
target = dnx.pegasus_graph(6)                  # small Pegasus graph (Advantage family)
emb = minorminer.find_embedding(source.edges, target.edges, random_seed=1)
lengths = [len(chain) for chain in emb.values()]
print("physical qubits:", sum(lengths), " longest chain:", max(lengths))

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
Minor embedding
Choi 2008, 2011 · Technique · Current · Intermediate
Mapping each logical variable to a connected chain of physical qubits so the problem graph fits the hardware graph. A triangle of variables on a bipartite-style hardware graph needs one variable represented by a two-qubit chain.
minorminer
D-Wave (Cai, Macready & Roy 2014 heuristic) · Tool · Current · Intermediate
Open-source heuristic library that finds minor embeddings of arbitrary problem graphs into hardware graphs. find_embedding with a 20-node complete graph and a Pegasus graph returns a chain of qubits for each variable.
Chain strength
D-Wave practice · Technique · Current · Intermediate
Ferromagnetic coupling that ties a chain's qubits together; too weak breaks chains, too strong drowns the problem signal. A common starting point is somewhat above the largest problem coupling, then tuning while watching the chain-break fraction.
Chain-break resolution
D-Wave (dwave-system) · Technique · Current · Intermediate
Deciding a variable's value when its chain's qubits disagree, typically by majority vote or local energy minimisation. dwave-system reports chain_break_fraction per sample, with majority vote as the default repair method.
Chimera topology
D-Wave · Hardware · Legacy · Intermediate
Grid of 8-qubit bipartite unit cells with 6 couplers per qubit, used up to the 2,048-qubit D-Wave 2000Q. Many 2014-2018 benchmarking papers, such as Rønnow et al. and Denchev et al., ran on Chimera hardware.
Pegasus topology
D-Wave · Hardware · Current · Intermediate
Advantage's qubit graph with 15 couplers per qubit, giving shorter chains and larger embeddable problems than Chimera. Advantage processors offer 5,000+ qubits and around 35,000 couplers in the Pegasus layout.
Zephyr topology
D-Wave · Hardware · Current · Intermediate
Advantage2's qubit graph with 20 couplers per qubit, further shortening chains for dense problems. At Advantage2's May 2025 launch, D-Wave cited 20-way connectivity, doubled coherence and a 40% higher energy scale.
Clique embedding
Boothby, King & Roy 2016; dwave-system · Technique · Current · Intermediate
Pre-computed embeddings for fully connected graphs that give uniform chain lengths for dense problems. DWaveCliqueSampler embeds dense QUBOs up to the largest clique the chip supports, without a slow heuristic search.
Integrated control errors (ICE)
D-Wave documentation · Concept · Current · Advanced
Small random and systematic deviations between programmed and realised h and J values, limiting effective precision. Two couplings programmed as 0.50 and 0.51 may be physically indistinguishable, so QUBOs relying on that difference fail.
Spin-reversal transform (gauge)
D-Wave practice · Technique · Current · Advanced
Flips the encoding of chosen qubits and their coefficients, leaving the problem unchanged but averaging out hardware biases. Submitting 10 gauges of 100 reads each, instead of one batch of 1,000, typically yields more reliable statistics.
Coefficient scaling
D-Wave practice · Technique · Current · Intermediate
Rescaling h and J to fit hardware ranges such as J ∈ [−1, 1]; extreme ratios push small terms into the noise. A penalty of 100 next to objective terms of 0.1 squeezes the objective to a thousandth of the range — below the noise floor.
Classical post-processing
dwave-samplers (SteepestDescentSolver) · Technique · Current · Beginner
Quick classical steepest-descent or tabu search applied to annealer samples to remove small errors. Greedy single-bit flips on each returned sample often lower energies for a few milliseconds of CPU time.
QPU access time
D-Wave Leap · Metric · Current · Beginner
Billed time the QPU spends programming and sampling a problem, excluding network latency and queueing. 1,000 reads of 20-μs anneals, plus readout and delays, add up to roughly a few hundred milliseconds of QPU time.

6.6 D-Wave Advantage, Advantage2, Leap & Hybrid Solvers

D-Wave Quantum, founded in 1999 near Vancouver, Canada, is the main commercial maker of quantum annealers. Its Advantage (2020) and Advantage2 (generally available May 2025) systems are reached through the Leap cloud service and the open-source Ocean SDK. Most production users run 'hybrid solvers' that mix classical heuristics with QPU calls to handle problems far bigger than the chip itself.

Qubit counts rose, then connectivity and coherence became the focus.
D-Wave hardware and services. Qubit counts rose, then connectivity and coherence became the focus.

Think of it like…

The QPU is a specialist chef; the hybrid solver is the restaurant kitchen around it — prep cooks (classical heuristics) do most of the chopping and send only the trickiest steps to the specialist.

Real-world example

The fictional grocery chain FreshFold uses D-Wave's hybrid CQM solver to schedule 3,000 staff shifts under labour-law constraints. The solver returns feasible schedules within its time limit. FreshFold's team benchmarks it against its existing Gurobi model, finds similar quality, and chooses whichever is cheaper and easier to operate.

How it works

  1. Install Ocean (pip install dwave-ocean-sdk) and configure a Leap API token.
  2. Build a model: a BQM for the QPU or hybrid BQM solver, a CQM for constrained problems, or a nonlinear model for the Stride solver.
  3. Choose a sampler: DWaveSampler with EmbeddingComposite for direct QPU access, or a Leap hybrid sampler.
  4. Set time limits or numbers of reads, submit, and receive a SampleSet.
  5. Check feasibility and energy, and compare with classical solvers.

Who uses it

Operations-research and quantum teams at companies trialling D-Wave in manufacturing, logistics, telecoms and retail, and academic researchers with Leap access.

Key takeaway

Know the generations: D-Wave One (2011, 128 qubits) → D-Wave 2000Q (2017, 2,048) → Advantage (2020, 5,000+) → Advantage2 (2025, 4,400+ with richer connectivity).

Going deeper

  • Advantage (2020) has 5,000+ qubits in a Pegasus graph with 15 couplers per qubit; Advantage2 (generally available 20 May 2025) has 4,400+ qubits in Zephyr with 20 per qubit, plus claimed doubled coherence and 40% higher energy scale.
  • Leap hybrid solvers include hybrid BQM for unconstrained binary problems, hybrid CQM for explicit constraints with binary, integer and continuous variables, and a nonlinear solver renamed the Stride hybrid solver in January 2026.
  • Hybrid solvers run classical heuristics in the cloud and call the QPU for parts of the search; D-Wave does not publish how much each QPU call contributes, which complicates attributing results to quantum effects.
  • Ocean SDK components include dimod (models), dwave-system (QPU and Leap samplers), dwave-samplers (classical samplers), minorminer (embedding), dwave-networkx (topologies) and dwave-optimization (nonlinear models).
  • Solver limits depend on version and account; query them live, for example LeapHybridCQMSampler().properties['maximum_number_of_variables'], rather than trusting older white papers.
  • D-Wave's 2025 Science paper (King et al.) claimed beyond-classical quantum simulation of spin-glass dynamics on an annealer — a simulation result, not an optimisation or ML speed-up.

Common mistakes & misconceptions

  • Attributing hybrid-solver results to quantum effects without ablation tests; the classical part may be doing most of the work.
  • Assuming more qubits always means bigger problems: Advantage2 has fewer qubits than Advantage but better connectivity and coherence.
  • Forgetting cost: Leap usage is billed by solver time, so compare cost per good solution, not just speed.

Try it: A constrained model solved locally with Ocean (a Leap account adds hybrid and QPU solvers)

# pip install dimod dwave-samplers
import dimod
from dwave.samplers import SimulatedAnnealingSampler
cqm = dimod.ConstrainedQuadraticModel()
x = [dimod.Binary(f"x{i}") for i in range(5)]
cqm.set_objective(-3*x[0] - 2*x[1] - 4*x[2] - x[3] - 2*x[4] + 2*x[0]*x[2])
cqm.add_constraint(sum(x) == 2, label="pick_two")
bqm, invert = dimod.cqm_to_bqm(cqm, lagrange_multiplier=10)
best = SimulatedAnnealingSampler().sample(bqm, num_reads=100).first
print(invert(best.sample), best.energy)
# With Leap access: from dwave.system import LeapHybridCQMSampler
#                   LeapHybridCQMSampler().sample_cqm(cqm)

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
D-Wave Quantum Inc.
Founded 1999; NYSE: QBTS · Organisation · Current · Beginner
Canadian-American company building superconducting quantum annealers, publicly listed since 2022, which also develops gate-model qubits. Its Leap cloud service gives developers Python access to Advantage systems and hybrid solvers.
Advantage
D-Wave 2020 · Hardware · Current · Beginner
Quantum annealer with 5,000+ qubits and 15-way Pegasus connectivity; D-Wave's main production QPU from 2020. Most annealing-for-ML studies published between 2021 and 2024 ran on Advantage systems through Leap.
Advantage2
D-Wave 2025 · Hardware · Current · Beginner
Annealer generally available since May 2025 with 4,400+ qubits, 20-way Zephyr connectivity, doubled coherence and higher energy scale. Dense QUBOs embed with shorter chains than on Advantage, reducing chain breaks for the same problem.
Leap
D-Wave (launched 2018) · Service · Current · Beginner
D-Wave's cloud service for real-time access to QPUs and hybrid solvers, integrated with the Ocean Python tools. After saving an API token with 'dwave setup', calls to DWaveSampler() are routed to a cloud QPU.
Ocean SDK
D-Wave (open source) · Framework · Current · Beginner
Open-source Python tools for formulating, embedding and solving problems on D-Wave QPUs, hybrid solvers and classical samplers. pip install dwave-ocean-sdk installs dimod, dwave-system, dwave-samplers, minorminer and related packages.
Hybrid BQM solver
D-Wave Leap · Service · Current · Intermediate
Leap solver for large unconstrained binary quadratic models, combining classical heuristics with QPU calls. A 50,000-variable image-segmentation QUBO, far beyond direct QPU capacity, is solved within a time limit of seconds.
Hybrid CQM solver
D-Wave Leap · Service · Current · Intermediate
Leap solver for constrained quadratic models with binary, integer and continuous variables and explicit constraints. A shift-scheduling model with 20,000 variables and 5,000 constraints is submitted without hand-tuned penalty weights.
Stride hybrid solver
D-Wave (renamed January 2026) · Service · Emerging · Intermediate
Leap's nonlinear hybrid solver, formerly called the NL solver, for models with native constraints, permutations and subsets. A capacitated vehicle-routing problem is written with list (permutation) variables in dwave-optimization and sent via LeapHybridNLSampler.
dwave-samplers
D-Wave (open source) · Library · Current · Beginner
Ocean package of classical samplers: simulated annealing, tabu search, steepest descent, random sampling and tree decomposition. SimulatedAnnealingSampler gives a free local baseline for any BQM before spending QPU time.
DWaveSampler with EmbeddingComposite
D-Wave (dwave-system) · Tool · Current · Intermediate
The standard way to send a BQM straight to a QPU, embedding it automatically with minorminer. EmbeddingComposite(DWaveSampler()).sample(bqm, num_reads=1000) returns samples with timing and chain-break information.
dwave-hybrid
D-Wave (open source) · Framework · Current · Advanced
Framework for building custom hybrid workflows that decompose large problems and combine classical and quantum samplers. A researcher alternates tabu search with QPU sub-problems of 50 variables chosen by their energy impact.
qbsolv
D-Wave 2017 · Tool · Legacy · Intermediate
Early open-source decomposing QUBO solver, since deprecated in favour of Leap hybrid solvers and dwave-hybrid. Papers from 2017-2019 often report qbsolv results; reproducing them today usually means switching to newer tools.

6.7 Coherent Annealing, Beyond-Classical Claims & Other Analogue Optimisers

Early critics doubted that annealers were 'quantum' at all. Since 2022, D-Wave experiments with very fast, coherent anneals have reproduced textbook quantum dynamics in chains and spin glasses of thousands of qubits, and a 2025 Science paper claimed simulations beyond classical reach. These are physics-simulation results; they have not yet translated into faster ML or optimisation. Other analogue machines — optical Ising machines and Rydberg-atom arrays — pursue similar goals.

Strong physics evidence accumulated; optimisation speed-ups stayed limited.
The evidence trail for quantum annealing. Strong physics evidence accumulated; optimisation speed-ups stayed limited.

Think of it like…

Like proving a race car's engine really is turbocharged on a test bench: impressive engineering evidence, but not yet proof that it wins on the roads you actually drive.

Real-world example

Students in the fictional Northbridge University physics club read King et al. (2023): a 5,000-qubit spin glass was annealed quickly and its defects matched quantum predictions for a phase transition. They then ask whether this helps their feature-selection QUBO. The honest answer is 'not directly' — simulation advantage and optimisation advantage are different claims.

How it works

  1. Run very short anneals (nanoseconds) so the environment has little time to disturb the qubits.
  2. Compare measured correlations or defect densities with closed-system quantum predictions.
  3. Scale up the system and check where classical simulation methods stop keeping up.
  4. Separate simulation claims (physics) from optimisation claims (finding low energies faster).
  5. Ask whether the same coherence improves time-to-solution on useful optimisation instances.

Who uses it

Physicists studying quantum phase transitions, annealing-hardware engineers, and analysts judging quantum-advantage announcements.

Key takeaway

Distinguish three claims: coherence (is it quantum?), simulation advantage (can classical computers reproduce it?), and optimisation advantage (does it find better answers faster?).

Going deeper

  • Johnson et al. (Nature 473, 194, 2011) showed quantum annealing with eight 'manufactured spins' — early evidence of quantum behaviour in D-Wave's superconducting flux qubits.
  • King et al. (Nature Physics 2022) observed coherent dynamics in a 2,000-qubit Ising chain matching closed-system theory; King et al. (Nature 2023) extended this to a 5,000-qubit three-dimensional spin glass.
  • King et al. (Science 388, 199, 2025) claimed annealer samples of spin-glass quench dynamics that leading tensor-network and neural-network methods could not match; classical-simulation groups soon posted counter-simulations for parts of the problem.
  • King et al. (Nature Communications 2021) reported a scaling advantage over path-integral Monte Carlo for simulating frustrated magnets — again simulation, not optimisation.
  • Coherent Ising machines from NTT and Stanford encode spins in optical parametric oscillator pulses (Inagaki et al. and McMahon et al., Science 2016); Rydberg-atom arrays solve maximum independent set natively (Ebadi et al., Science 2022).
  • Gate-model teams also run digitised, annealing-like schedules such as counterdiabatic or linear-ramp QAOA, blurring the line between annealing and QAOA.

Common mistakes & misconceptions

  • Reading a simulation advantage as an optimisation advantage; they answer different questions.
  • Assuming coherence persists in default 20-μs anneals; the coherent results relied on very fast anneals.
  • Ignoring classical rebuttals: beyond-classical claims are often narrowed by improved classical algorithms within months.

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
'Quantum annealing with manufactured spins'
Johnson et al. 2011 (Nature) · Paper · Legacy · Intermediate
Early D-Wave paper showing eight coupled superconducting flux qubits behaving quantum-mechanically during annealing. Often cited in the 2011-2015 debates over whether D-Wave machines were 'really quantum'.
Coherent annealing in a 2,000-qubit chain
King et al. 2022 (Nature Physics) · Paper · Current · Advanced
Fast anneals of a long Ising chain matched closed-system quantum predictions for defect formation — coherence at scale. Kink densities after nanosecond anneals followed the quantum Kibble-Zurek prediction rather than thermal behaviour.
Quantum critical dynamics in a 5,000-qubit spin glass
King et al. 2023 (Nature) · Paper · Current · Advanced
Showed coherent quantum critical dynamics in three-dimensional spin glasses with thousands of qubits on Advantage. Measured scaling across many system sizes agreed with quantum, not classical, dynamics.
'Beyond-classical computation in quantum simulation'
King et al. 2025 (Science 388, 199) · Paper · Current · Advanced
Claimed annealer simulation of spin-glass quench dynamics in 2D, 3D and infinite dimensions beyond leading classical methods. Classical groups replied with tensor-network and neural-network simulations of some instances — a debate worth following.
Classical counter-simulations
Tindall et al. 2025; Mauron & Carleo 2025 (preprints) · Paper · Current · Advanced
Tensor-network and neural-network simulations challenging parts of the 2025 beyond-classical claim. They show that advantage claims are a moving target, tested by steadily improving classical methods.
Fast anneal
D-Wave · Technique · Current · Intermediate
QPU feature for very short, nanosecond-scale anneals with a modified schedule, keeping dynamics close to coherent. Researchers use it to probe quantum phase transitions; it is a physics tool rather than a default setting for optimisation.
Kibble-Zurek mechanism
Kibble 1976; Zurek 1985 · Concept · Current · Advanced
Theory predicting how many defects form when a system is driven through a phase transition at a finite speed. Faster sweeps leave more domain walls in an Ising chain, following a power law in anneal time.
Path-integral Monte Carlo (PIMC)
Suzuki 1976; Santoro et al. 2002 · Algorithm · Current · Advanced
Classical simulation of stoquastic quantum systems at finite temperature; a key competitor when simulating annealers. King et al. (2021) reported the annealer relaxing frustrated magnets with better scaling than PIMC.
Scaling advantage over PIMC
King et al. 2021 (Nature Communications) · Paper · Current · Advanced
Annealer simulation of geometrically frustrated magnets showed better scaling than path-integral Monte Carlo for relaxation dynamics. Time to reach equilibrium grew more slowly with system size on the QPU than with the classical method.
Coherent Ising machine
NTT; Stanford (Inagaki et al., McMahon et al. 2016) · Hardware · Research · Intermediate
Optical network of parametric oscillator pulses whose phases act as Ising spins, coupled through measurement feedback. A 2016 fibre-loop machine handled 2,000-spin MaxCut instances, with all-to-all coupling implemented by FPGA feedback.
Rydberg-atom MIS solving
Ebadi et al. 2022 (Science) · Paper · Research · Intermediate
Neutral atoms in optical tweezers with Rydberg blockade natively encode maximum independent set on unit-disk graphs. With up to 289 atoms, the team reported speed-ups over simulated annealing on some hard graphs — not over the best classical solvers.
QuEra Computing
Boston, USA · Organisation · Current · Beginner
Neutral-atom quantum company behind Aquila, a 256-atom analogue processor offered through Amazon Braket. Students encode a small maximum-independent-set problem as atom positions and run it as an analogue Hamiltonian simulation.

6.8 QAOA: The Quantum Approximate Optimisation Algorithm

QAOA (Farhi, Goldstone & Gutmann, 2014) is a gate-model algorithm for combinatorial problems. It alternates two operations p times — a 'cost' step that adds a phase to each bitstring according to its objective value, and a 'mixer' step that shuffles amplitude between bitstrings — with angles tuned by a classical optimiser. With many layers it can mimic annealing; with few layers it is a trainable heuristic.

The quantum computer only evaluates; the classical optimiser decides.
The QAOA training loop. The quantum computer only evaluates; the classical optimiser decides.

Think of it like…

Like kneading dough: press it according to the recipe (cost layer), fold it to spread things around (mixer layer), and repeat a few rounds, adjusting how hard you press and fold until it is just right.

Real-world example

Lucía at the fictional Saltmarsh Telecom runs QAOA with p = 2 on a 12-node MaxCut problem in PennyLane. A classical optimiser tunes four angles; 1,000 shots give cuts averaging about 85% of the maximum, and the best sampled bitstring hits the optimum. Since Goemans-Williamson already guarantees 87.8% on average, she treats QAOA as a learning exercise, not a production tool.

How it works

  1. Write the problem as a cost Hamiltonian H_C — for MaxCut, Σ(1 − ZᵢZⱼ)/2 over the edges.
  2. Prepare |+⟩ on every qubit: an equal superposition of all bitstrings.
  3. Apply p layers of the cost unitary e^{−iγₖH_C} and the mixer e^{−iβₖΣXᵢ}.
  4. Measure many shots to estimate ⟨H_C⟩ for the current angles γ and β.
  5. Let a classical optimiser update the angles; repeat until converged.
  6. Return the best bitstring sampled.

Who uses it

Quantum algorithm researchers, quantum software engineers, and finance or logistics teams prototyping gate-model optimisation.

Key takeaway

Memorise the first result: for p = 1 on 3-regular graphs, QAOA's MaxCut approximation ratio is at least 0.6924 — below Goemans-Williamson's 0.878.

Going deeper

  • Farhi, Goldstone & Gutmann (arXiv:1411.4028, 2014) introduced QAOA and proved a p = 1 MaxCut ratio of at least 0.6924 on 3-regular graphs; each MaxCut cost layer needs one ZZ rotation per edge.
  • Hastings (2019) and Bravyi, Kliesch, Koenig & Tang (PRL 2020) showed local classical algorithms match or beat low-depth QAOA on bounded-degree MaxCut, and that symmetry limits low-depth performance.
  • Farhi, Gamarnik & Gutmann (2020) showed QAOA 'needs to see the whole graph': on sparse random graphs, depth must grow with problem size before QAOA can outperform classical algorithms.
  • Parameter concentration (Brandão et al., 2018): for typical instances of a given type, optimal angles are nearly instance-independent, so angles trained on small graphs transfer to larger ones.
  • At high depth, Basso et al. (2022) computed QAOA performance on large-girth regular graphs and the Sherrington-Kirkpatrick model in the infinite-size limit, showing steady improvement with p.
  • PennyLane's qaoa.maxcut defines its cost Hamiltonian so that lower expectation means more edges cut; its minimum equals minus the maximum cut, which is why the optimiser minimises.

Common mistakes & misconceptions

  • Confusing the expected cut (an average) with the best sampled cut; report both, together with the classical baseline.
  • Assuming more layers always help on hardware: deeper circuits collect more noise, which often cancels the gains of extra layers.
  • Treating QAOA as a guaranteed speed-up: it is a heuristic with no proven advantage on practical problems.

Try it: QAOA for MaxCut on a 4-node graph with PennyLane

# pip install pennylane networkx
import pennylane as qml
from pennylane import qaoa
from pennylane import numpy as np
import networkx as nx
g = nx.Graph([(0, 1), (1, 2), (2, 0), (2, 3)])
cost_h, mixer_h = qaoa.maxcut(g)
dev = qml.device("default.qubit", wires=4)
def layer(gamma, alpha):
    qaoa.cost_layer(gamma, cost_h)
    qaoa.mixer_layer(alpha, mixer_h)
@qml.qnode(dev)
def cost(params):
    for w in range(4):
        qml.Hadamard(wires=w)
    qml.layer(layer, 2, params[0], params[1])
    return qml.expval(cost_h)
params = np.array([[0.5, 0.5], [0.5, 0.5]], requires_grad=True)
opt = qml.GradientDescentOptimizer(stepsize=0.1)
for _ in range(60):
    params = opt.step(cost, params)
print("expected cost:", round(float(cost(params)), 3), "(lower = more edges cut; max cut here = 3)")

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
QAOA
Farhi, Goldstone & Gutmann 2014 · Algorithm · Research · Intermediate
Alternates cost and mixer layers with p pairs of tuned angles to prepare states concentrated on good solutions. p = 1 MaxCut on an 8-node ring needs 8 ZZ rotations and 8 X rotations per layer.
Cost Hamiltonian
Farhi, Goldstone & Gutmann 2014 · Concept · Current · Intermediate
Diagonal operator whose eigenvalue on each bitstring equals its objective value; the cost layer applies e^{−iγH_C}. For MaxCut, H_C = Σ(1 − ZᵢZⱼ)/2 over edges counts how many edges a bitstring cuts.
Mixer Hamiltonian
Farhi, Goldstone & Gutmann 2014 · Concept · Current · Intermediate
Operator, usually ΣXᵢ, that does not commute with the cost and moves amplitude between bitstrings. The transverse-field mixer is just an RX(2β) rotation on every qubit — one layer of single-qubit gates.
0.6924 approximation guarantee
Farhi, Goldstone & Gutmann 2014 · Theorem · Current · Intermediate
Proven worst-case ratio of p = 1 QAOA for MaxCut on 3-regular graphs. On a 3-regular graph whose maximum cut is 90 edges, p = 1 QAOA's expected cut is at least about 62 edges.
Parameter concentration
Brandão et al. 2018 · Concept · Current · Intermediate
For typical instances from the same family, optimal QAOA angles are nearly identical, enabling transfer from small to large problems. Angles optimised on 12-node 3-regular graphs work well on 100-node 3-regular graphs without re-optimisation.
Locality limits of low-depth QAOA
Hastings 2019; Bravyi et al. 2020; Farhi, Gamarnik & Gutmann 2020 · Theorem · Current · Advanced
Low-depth QAOA sees only local neighbourhoods, so local classical algorithms can match it, and depth must grow to win. At p = 1 on 3-regular graphs, a simple local classical algorithm matches or beats QAOA's guarantee.
Expected value vs best sample
QAOA practice · Metric · Current · Beginner
QAOA can be judged by its average energy ⟨H_C⟩ or by the best bitstring among many shots; the two tell different stories. An average ratio of 0.75 can still yield the optimal cut in one of 1,000 shots on a small graph.
QAOA as Trotterised annealing
Farhi, Goldstone & Gutmann 2014 · Concept · Current · Intermediate
Many layers with small angles approximate a discretised annealing schedule; few layers explore non-adiabatic strategies. Initialising angles from a linear annealing ramp often beats random starting angles.
Sherrington-Kirkpatrick model
Sherrington & Kirkpatrick 1975 · Benchmark · Current · Advanced
Fully connected spin glass with random couplings; a standard theoretical benchmark for QAOA at large depth. Its all-to-all couplings make it hard to run on planar chips, where every pair of qubits must interact.
High-depth QAOA analysis
Basso et al. 2022 (TQC) · Paper · Research · Advanced
Computes QAOA's performance at growing depth for large-girth regular graphs and the SK model in the infinite-size limit. Shows performance rising steadily with p — evidence that depth, not just tuning, drives QAOA quality.
PennyLane qaoa module
Xanadu (PennyLane) · Library · Current · Beginner
Ready-made QAOA cost and mixer Hamiltonians for problems such as MaxCut and maximum independent set, plus layer helpers. qaoa.maxcut(graph) returns cost and mixer Hamiltonians; qml.layer repeats the cost and mixer layers p times.
Qiskit QAOA tools
IBM Qiskit; qiskit-community (Qiskit Optimization) · Library · Current · Intermediate
Core Qiskit's QAOAAnsatz builds QAOA circuits, while the community-maintained Qiskit Optimization package converts models into QUBOs. A docplex model is converted to a QUBO, then run with QAOA on a simulator and with a classical solver for comparison.

6.9 QAOA Variants: Warm-Start, Recursive, Multi-Angle & More

Plain QAOA struggles at low depth, so researchers modify it: warm-starting from a classical solution, recursively shrinking the problem, giving each qubit or edge its own angle, building the circuit adaptively, or using mixers that respect constraints. These variants often perform better in small experiments, but none has a proven practical advantage over classical methods.

Each variant fixes a different weakness of vanilla QAOA.
The QAOA family. Each variant fixes a different weakness of vanilla QAOA.

Think of it like…

Like upgrading a basic recipe: start from a store-bought base (warm start), cook in smaller batches (recursive), season each ingredient separately (multi-angle), or use a pan shaped for the dish (constraint-preserving mixers).

Real-world example

At the fictional Quill Securities, Hana compares QAOA variants on choosing exactly 8 of 16 assets. An XY mixer keeps every state at exactly 8 assets, so no penalty is needed; a warm start from the continuous relaxation provides a good initial state. Together they raise the probability of feasible, high-quality portfolios compared with vanilla QAOA in her simulations.

How it works

  1. Start from vanilla QAOA and identify its weakness: low depth, constraints, or a poor initial state.
  2. Warm start: solve a relaxation classically and encode its solution in the initial state and mixer.
  3. Recursive QAOA: use measured correlations to fix or merge variables, shrinking the problem until it is solvable classically.
  4. Multi-angle or adaptive: add parameters per layer, or grow the circuit operator by operator using gradient signals.
  5. Constraint-preserving: replace X mixers with XY or Grover mixers that stay inside the feasible set.

Who uses it

Quantum algorithm researchers and applied teams at banks, IBM, national laboratories and start-ups benchmarking QAOA.

Key takeaway

Mention Hadfield et al.'s 'Quantum Alternating Operator Ansatz' (2019) — same acronym, generalising QAOA to arbitrary constraint-preserving mixers.

Going deeper

  • Warm-start QAOA (Egger, Mareček & Woerner, Quantum 2021) turns a continuous relaxation's solution into initial single-qubit rotations and adapts the mixer so that the warm-start state is its ground state.
  • Recursive QAOA (Bravyi, Kliesch, Koenig & Tang, PRL 2020) measures ⟨ZᵢZⱼ⟩ correlations, imposes the strongest as Zᵢ = ±Zⱼ, removes a variable and repeats; it beat standard QAOA on instances where symmetry hampers it.
  • Multi-angle QAOA (Herrman et al., Scientific Reports 2022) gives every edge and qubit its own angle, improving shallow-circuit results but making the classical optimisation harder; ADAPT-QAOA (Zhu et al., 2022) grows mixers from an operator pool.
  • The Quantum Alternating Operator Ansatz (Hadfield et al., Algorithms 2019) and Grover mixers (Bärtschi & Eidenbenz, 2020) keep the search inside feasible solutions such as fixed Hamming weight or permutations.
  • CVaR-QAOA (Barkoutsos et al., Quantum 2020) optimises the mean of the best α fraction of samples rather than the full average, aligning training with the goal that the best sample wins.
  • Shaydulin et al. (Science Advances 2024) found fixed-parameter QAOA scaled better than branch-and-bound solvers on low-autocorrelation binary sequences in simulations up to 40 qubits, and ran small instances on Quantinuum hardware with error detection.

Common mistakes & misconceptions

  • Comparing a heavily tuned variant against vanilla classical heuristics; tune both sides with equal effort.
  • Counting only quantum time: recursive QAOA and warm starts include substantial classical processing.
  • Assuming scaling advantages seen in noiseless simulation survive noise and compilation on real hardware.

Try it: An XY mixer keeps the number of chosen assets fixed (NumPy and SciPy)

import numpy as np
from scipy.linalg import expm
X = np.array([[0, 1], [1, 0]]); Y = np.array([[0, -1j], [1j, 0]]); I = np.eye(2)
def pair(P, i, j, n=3):                       # P on qubits i and j, identity elsewhere
    ops = [I] * n; ops[i] = ops[j] = P
    out = ops[0]
    for o in ops[1:]:
        out = np.kron(out, o)
    return out
H_xy = sum(pair(X, i, j) + pair(Y, i, j) for i, j in [(0, 1), (1, 2), (0, 2)])
U = expm(-1j * 0.7 * H_xy)                    # XY 'ring' mixer
state = np.zeros(8); state[0b100] = 1         # exactly one asset chosen (Hamming weight 1)
out = U @ state
print({format(k, "03b"): round(float(abs(a) ** 2), 3) for k, a in enumerate(out) if abs(a) > 1e-9})

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
Warm-start QAOA
Egger, Mareček & Woerner 2021 (Quantum) · Algorithm · Research · Intermediate
Initialises QAOA from a classical relaxation's solution and adapts the mixer accordingly, improving low-depth results. A portfolio QP relaxation gives weights such as 0.9 and 0.1, which become initial qubit rotation angles instead of uniform |+⟩ states.
Recursive QAOA (RQAOA)
Bravyi, Kliesch, Koenig & Tang 2020 (PRL) · Algorithm · Research · Advanced
Repeatedly uses QAOA correlations to eliminate variables, shrinking the problem until it can be solved classically. A 100-node graph is reduced by fixing strongly correlated pairs until 10 nodes remain, which are brute-forced.
Multi-angle QAOA (ma-QAOA)
Herrman et al. 2022 (Scientific Reports) · Algorithm · Research · Intermediate
Assigns a separate angle to every cost term and every mixer qubit, adding expressiveness to each layer. For a graph with 10 edges and 8 nodes at p = 1, ma-QAOA trains 18 angles instead of 2.
ADAPT-QAOA
Zhu et al. 2022 (Physical Review Research) · Algorithm · Research · Advanced
Grows the circuit layer by layer, choosing each mixer from an operator pool by the size of its energy gradient. In small MaxCut simulations it reached high approximation ratios with fewer layers than standard QAOA.
Quantum Alternating Operator Ansatz
Hadfield et al. 2019 (Algorithms) · Algorithm · Research · Advanced
Generalises QAOA with problem-specific mixers and initial states that preserve constraints, avoiding penalty terms. For graph colouring, mixers swap colours within each node's one-hot register, so invalid encodings never appear.
XY mixer
Hadfield et al. 2019; Wang et al. 2020 · Ansatz · Research · Intermediate
Mixer built from XX + YY interactions that preserves Hamming weight, keeping 'choose exactly k' constraints satisfied. To select exactly 8 of 16 assets, start in a weight-8 state and apply ring-shaped XY mixers.
Grover mixer
Bärtschi & Eidenbenz 2020 (IEEE QCE) · Ansatz · Research · Advanced
Mixer that reflects about the uniform superposition of feasible states, prepared by a state-preparation circuit. Works for any constraint set whose uniform superposition is easy to prepare, such as fixed-weight strings.
Dicke-state preparation
Bärtschi & Eidenbenz 2019 · Technique · Research · Intermediate
Prepares the equal superposition of all n-bit strings with exactly k ones — the natural start for fixed-cardinality problems. The Dicke state with n = 4 and k = 2 is an equal superposition of the six 4-bit strings with two ones.
CVaR objective
Barkoutsos et al. 2020 (Quantum) · Technique · Research · Intermediate
Optimises the average of the best α fraction of measured energies instead of the overall mean, focusing on good samples. With α = 0.1 and 1,000 shots, only the 100 lowest-energy shots enter the cost function.
Annealing-ramp initialisation
Sack & Serbyn 2021 (Quantum) · Technique · Research · Intermediate
Sets initial QAOA angles from a discretised linear annealing schedule (TQA initialisation), avoiding poor local minima. For p = 10, γ rises and β falls linearly across the layers, then a local optimiser fine-tunes them.
Digitised counterdiabatic QAOA
Chandarana et al. 2022 (Physical Review Research) · Algorithm · Research · Advanced
Adds counterdiabatic-inspired terms to QAOA layers to suppress unwanted excitations and reduce the depth needed. Adding one extra single-qubit rotation term per layer sped up convergence for small Ising problems in simulation.
LABS scaling study
Shaydulin et al. 2024 (Science Advances) · Paper · Research · Advanced
Found fixed-parameter QAOA's runtime scaling beat branch-and-bound solvers on LABS in simulations up to 40 qubits. Combined with quantum minimum finding it gave the best empirical scaling reported for LABS; small runs used Quantinuum trapped ions.

6.10 Gate-Model Optimisation on Real Hardware

Running QAOA-style optimisation on real quantum processors adds practical problems: qubits are connected only to neighbours, so extra SWAP gates are needed; every cost evaluation costs thousands of shots; and noise lowers the quality of samples. Experiments by Google, university trapped-ion labs, Quantinuum and IBM show what is possible today — and where noise still dominates.

Routing a dense problem onto sparse hardware multiplies depth and therefore noise.
Two-qubit gate layers per QAOA layer (rough). Routing a dense problem onto sparse hardware multiplies depth and therefore noise.

Think of it like…

Like cooking a gourmet recipe in a cramped camping kitchen: the recipe is the same, but every extra step of moving pans around (SWAP gates) costs time and risks spilling something (errors).

Real-world example

Dev, a quantum engineer at the fictional Ridgeway Energy, runs QAOA on a 100-qubit IBM processor for a grid problem whose graph matches the chip's heavy-hex layout. With no SWAPs needed, a p = 2 circuit is shallow enough to give useful samples. When he tries a fully connected version of the same problem, routing adds hundreds of SWAPs and results approach random guessing.

How it works

  1. Map the problem graph to the chip; prefer hardware-native graphs or use swap networks.
  2. Transpile with error-aware layout and dynamical decoupling where available.
  3. Choose a shot budget and parameter strategy — transfer angles from simulation where possible.
  4. Apply readout mitigation; use error detection or post-selection on symmetries if the problem allows.
  5. Compare the sampled solutions with classical solvers on the same instances.

Who uses it

Quantum software engineers, hardware benchmarking teams, and application scientists running optimisation on IBM, Quantinuum, IonQ and Google-class devices.

Key takeaway

Hardware-native problem graphs avoid SWAP overhead; if your problem is fully connected, expect circuit depth to grow at least linearly with the number of qubits per QAOA layer.

Going deeper

  • Harrigan et al. (Nature Physics 2021) ran QAOA on Google's Sycamore with up to 23 qubits: hardware-native problems kept their quality as size grew, while non-native graphs degraded towards random results.
  • Pagano et al. (PNAS 2020) ran p = 1 QAOA on up to 40 trapped-ion qubits, exploiting the ions' native long-range interactions to avoid routing.
  • Swap networks (Kivlichan et al., PRL 2018; O'Gorman et al. 2019) let every qubit pair become adjacent once per layer, giving linear-depth all-to-all interactions on a line of qubits.
  • Estimating ⟨H_C⟩ to precision ε needs about Var(H_C)/ε² shots, so a full optimisation with hundreds of iterations can need hundreds of thousands to millions of shots.
  • Zero-noise extrapolation improves expectation values but not individual bitstrings; for optimisation, where the best sample matters, error detection and post-selection are often more useful.
  • IBM's Qiskit Functions catalogue lists third-party optimisation services — such as Q-CTRL's Optimization Solver and Kipu Quantum's Iskay optimizer — that wrap QAOA-like methods with error suppression.

Common mistakes & misconceptions

  • Running dense problems on sparse hardware without counting SWAP overhead; routing noise can erase any signal.
  • Mitigating expectation values and then reporting the best raw sample as if it had been mitigated too.
  • Spending the whole shot budget on parameter training, leaving too few shots for the final sampling.

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
Hardware-native problems
Harrigan et al. 2021 · Concept · Current · Intermediate
Problems whose interaction graph matches the chip's qubit connectivity, needing no SWAP gates; QAOA performs best on these. A heavy-hex Ising model on an IBM chip needs only about three layers of two-qubit gates per QAOA layer.
Routing overhead for dense QAOA
Quantum compilation · Concept · Current · Intermediate
Extra SWAP gates needed so non-neighbouring qubits can interact; for dense problems they multiply circuit depth and noise. A fully connected 20-node problem on a line of qubits needs on the order of 20 SWAP layers per QAOA layer.
Swap networks
Kivlichan et al. 2018 (PRL); O'Gorman et al. 2019 · Technique · Current · Advanced
Fixed SWAP patterns that make every qubit pair adjacent once per layer, giving linear-depth all-to-all interactions. Dense Sherrington-Kirkpatrick instances are compiled with swap networks so every coupling can be applied.
Sycamore QAOA experiment
Harrigan et al. 2021 (Nature Physics) · Paper · Current · Intermediate
Google ran QAOA on hardware-grid, 3-regular and SK problems with up to 23 qubits, exposing routing-noise penalties. Grid-native problems kept their quality as size grew, while non-native graphs drifted towards random guessing.
Trapped-ion QAOA experiment
Pagano et al. 2020 (PNAS) · Paper · Current · Intermediate
Demonstrated p = 1 QAOA on up to 40 trapped-ion qubits by using native long-range interactions. Showed that all-to-all connectivity removes routing costs, at the price of slower gates than superconducting chips.
Shot budget per cost evaluation
Measurement statistics · Metric · Current · Beginner
Number of circuit repetitions per cost evaluation; estimating ⟨H_C⟩ to precision ε needs about Var/ε² shots. With variance 25 and target ±0.1, each evaluation needs about 2,500 shots; 200 iterations need 500,000 shots.
Parameter transfer
Brandão et al. 2018; Shaydulin et al. 2024 · Technique · Current · Intermediate
Reusing angles optimised on small or simulated instances to skip expensive on-hardware training. The LABS study fixed QAOA parameters from small instances and applied them to larger ones without retraining.
Readout error mitigation
Quantum hardware practice · Technique · Current · Beginner
Calibrates measurement errors and corrects output distributions; simple and important when individual bitstrings matter. Calibration circuits reveal one qubit reads 1 as 0 with 3% probability, and counts are corrected accordingly.
Zero-noise extrapolation for QAOA
Temme, Bravyi & Gambetta 2017; Kandala et al. 2019 · Technique · Current · Intermediate
Runs circuits at amplified noise levels and extrapolates ⟨H_C⟩ to zero noise; improves averages, not individual samples. Folding gates to 1×, 3× and 5× noise gives a cleaner energy estimate, yet the best bitstring still comes from raw samples.
Error detection for optimisation
Shaydulin et al. 2024 (Quantinuum experiment) · Technique · Emerging · Advanced
Lightweight codes or symmetry checks that discard runs where an error was detected, trading shots for fidelity. The LABS experiment used an algorithm-specific error-detection scheme on trapped ions and post-selected clean runs.
Quantinuum trapped-ion systems
Quantinuum · Hardware · Current · Intermediate
Trapped-ion computers with all-to-all connectivity and high two-qubit fidelity; Helios, launched in late 2025, has 98 qubits. Teams favour them for QAOA on dense problems because no SWAP routing is required.
IBM Heron processors
IBM · Hardware · Current · Intermediate
IBM's 133- and 156-qubit tunable-coupler superconducting processors on heavy-hex lattices, used for 100+ qubit optimisation experiments. Researchers run QAOA on heavy-hex-native graphs with over 100 qubits and compare samples with classical solvers.
Qiskit Functions optimisation services
IBM catalogue (Q-CTRL, Kipu Quantum, others) · Service · Emerging · Intermediate
Third-party optimisation services in IBM's Qiskit Functions catalogue that wrap QAOA-like methods with error suppression. A user submits a binary cost function to Q-CTRL's Optimization Solver and receives bitstrings without writing circuits.

6.11 The Variational Quantum Eigensolver as a Learning Problem

The variational quantum eigensolver (VQE; Peruzzo et al., 2014) finds the lowest energy of a molecule or material by training a parameterised circuit to minimise the measured energy — just like training a model to minimise a loss. Viewing VQE as machine learning highlights familiar issues: choosing the model (ansatz), noisy gradients, optimiser choice, local minima and trainability.

VQE seen as machine learning

Machine learning VQE
Model neural network parameterised circuit (ansatz)
Loss error on training data measured energy ⟨H⟩
Data labelled examples none — the Hamiltonian defines the loss
Gradients backpropagation (cheap) parameter-shift: 2 circuits per parameter
Noise minibatch sampling shot noise plus hardware noise
Failure modes overfitting, vanishing gradients barren plateaus, local minima

Same training loop, different 'data' and different noise.

Think of it like…

VQE is like tuning a guitar by ear: twist the pegs (parameters), listen to how far off the note is (energy measurement), and keep adjusting until the sound can't get any better.

Real-world example

Dr. Kwame Mensah at the fictional Lattice Pharma uses VQE to estimate the ground-state energy of a small molecular fragment on 12 qubits. A chemistry-inspired ansatz reaches chemical accuracy in simulation, but on hardware each energy needs thousands of shots across hundreds of Pauli terms, so he groups commuting terms and applies error mitigation — and still checks the answer against classical CCSD(T).

How it works

  1. Map the molecular Hamiltonian to qubits (Jordan-Wigner or Bravyi-Kitaev) as a sum of Pauli strings.
  2. Choose an ansatz: chemistry-inspired (UCCSD), hardware-efficient, or adaptive (ADAPT-VQE).
  3. Estimate ⟨H⟩ by measuring groups of commuting Pauli terms with many shots.
  4. Update the parameters with a classical optimiser, gradient-based or gradient-free.
  5. Stop when the energy converges and validate against classical methods such as CCSD(T) or DMRG.

Who uses it

Computational chemists, materials scientists, and quantum algorithm teams at pharmaceutical, chemical and quantum-hardware companies.

Key takeaway

State the variational principle: for any trial state, ⟨ψ(θ)|H|ψ(θ)⟩ ≥ E₀, so lower measured energies mean better approximations — apart from noise.

Going deeper

  • Peruzzo et al. (Nature Communications 2014) introduced VQE on a photonic chip for HeH⁺; Kandala et al. (Nature 2017) used a hardware-efficient ansatz on superconducting qubits for molecules up to BeH₂ on six qubits.
  • The number of Pauli terms in molecular Hamiltonians grows roughly as N⁴ in the number of spin-orbitals, so measurement cost dominates; grouping commuting terms and shadow-style estimators cut shot counts substantially.
  • ADAPT-VQE (Grimsley, Economou, Barnes & Mayhall, Nature Communications 2019) builds the ansatz operator by operator from a pool using energy gradients, giving shorter circuits than UCCSD.
  • Chemical accuracy is 1.6 millihartree (about 1 kcal/mol); reaching it requires statistical error well below that, which can mean millions of shots for realistic molecules.
  • Bittel & Kliesch (PRL 2021) proved that training variational quantum algorithms is NP-hard in general, so local minima — not only barren plateaus — are a fundamental obstacle.
  • Unlike ML, VQE has no training data: the Hamiltonian is the loss, so 'generalisation' becomes transferability, such as reusing optimised parameters along a bond-stretching curve.

Common mistakes & misconceptions

  • Assuming VQE gives a chemistry advantage today: classical methods such as CCSD(T) and DMRG handle the molecules VQE has run so far.
  • Ignoring measurement cost: thousands of Pauli terms times thousands of shots times hundreds of iterations quickly reaches billions of shots.
  • Celebrating energies below the true ground state: noise and mitigation can bias estimates below E₀, which signals an error, not success.

Try it: A two-qubit VQE trained with Adam in PennyLane

# pip install pennylane
import pennylane as qml
from pennylane import numpy as np
H = qml.Hamiltonian([0.5, -0.8, 0.3], [qml.PauliZ(0) @ qml.PauliZ(1), qml.PauliX(0), qml.PauliX(1)])
dev = qml.device("default.qubit", wires=2)
@qml.qnode(dev)
def energy(t):
    qml.RY(t[0], wires=0); qml.RY(t[1], wires=1)
    qml.CNOT(wires=[0, 1]); qml.RY(t[2], wires=1)
    return qml.expval(H)
t = np.array([0.1, 0.2, 0.3], requires_grad=True)
opt = qml.AdamOptimizer(stepsize=0.1)
for _ in range(200):
    t = opt.step(energy, t)
print("VQE energy:", round(float(energy(t)), 4), "  exact:", round(float(min(np.linalg.eigvalsh(qml.matrix(H)))), 4))

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
Variational quantum eigensolver (VQE)
Peruzzo et al. 2014 (Nature Communications) · Algorithm · Current · Beginner
Hybrid algorithm that minimises a measured energy over parameterised circuits to approximate a Hamiltonian's ground state. Estimating hydrogen's bond-dissociation curve with a four-qubit, one-parameter ansatz is the classic first exercise.
Variational principle
Rayleigh-Ritz method · Theorem · Current · Beginner
The energy of any state is at least the true ground-state energy, so minimising it approaches E₀ from above. If H₂'s exact minimal-basis energy is about −1.137 Ha, every valid trial state measures at or above that value, apart from noise.
UCCSD ansatz
Peruzzo et al. 2014; Romero et al. 2018 · Ansatz · Current · Intermediate
Unitary coupled cluster with single and double excitations — chemistry-inspired and accurate, but produces deep circuits. For a 12-qubit molecule, UCCSD can need thousands of CNOTs — too deep for today's hardware without heavy simplification.
Hardware-efficient VQE
Kandala et al. 2017 (Nature) · Paper · Current · Intermediate
VQE with shallow layers of native rotations and entangling gates, demonstrated on superconducting qubits for small molecules. The team estimated energies for H₂, LiH and BeH₂, the last on six qubits.
Fermion-to-qubit mappings
Jordan & Wigner 1928; Bravyi & Kitaev 2002 · Technique · Current · Intermediate
Encode fermionic orbitals into qubits so a molecular Hamiltonian becomes a weighted sum of Pauli strings. Under Jordan-Wigner, an orbital's occupation is a qubit's |1⟩, with strings of Z operators tracking fermionic signs.
Classical chemistry baselines
CCSD(T): Raghavachari et al. 1989; DMRG: White 1992 · Algorithm · Current · Intermediate
Gold-standard classical methods VQE results must be checked against: CCSD(T) for weakly correlated molecules, DMRG for strongly correlated ones. Kwame's 12-qubit VQE energy is compared with a CCSD(T) calculation that runs in seconds on a workstation.
Chemical accuracy
Computational chemistry · Metric · Current · Beginner
An energy error within 1.6 millihartree (about 1 kcal/mol) — the usual target for useful chemistry predictions. A VQE energy 3 mHa above the exact value misses chemical accuracy, even though it looks close.
Training VQAs is NP-hard
Bittel & Kliesch 2021 (PRL) · Theorem · Current · Advanced
Proves that optimising the parameters of variational quantum algorithms is NP-hard in general, even in simple settings. It explains why optimisers stall in local minima, and why good initialisation and problem structure matter.
Energy as a loss function
VQE as machine learning · Concept · Current · Beginner
In VQE the loss is the measured energy and there are no labelled examples; the Hamiltonian plays the role of the dataset. Changing the molecule's bond length changes the 'dataset', so parameters from one geometry warm-start the next.
Variational quantum deflation
Higgott, Wang & Brierley 2019 (Quantum) · Algorithm · Research · Intermediate
Finds excited states by adding overlap penalties with previously found states to the VQE cost. After finding the ground state, adding β·|⟨ψ₀|ψ(θ)⟩|² to the cost locates the first excited state.
Sample-based quantum diagonalisation (SQD)
Kanno et al. 2023; IBM and RIKEN · Algorithm · Emerging · Advanced
Samples electronic configurations on a quantum computer, then diagonalises the Hamiltonian classically in that subspace — a noise-robust VQE alternative. IBM and RIKEN combined Heron processors with the Fugaku supercomputer to study iron-sulfur clusters using up to 77 qubits.

6.12 Benchmarking Against Classical Heuristics

Claims of quantum optimisation advantage only mean something against the best classical methods, run fairly: simulated annealing, parallel tempering, tabu search, mixed-integer solvers such as Gurobi and CPLEX, specialised heuristics, and tensor-network simulations. Good benchmarks fix a target quality, measure total time-to-solution including overheads, tune every solver, and study how runtime grows with problem size.

A single missing ingredient can turn a 'speed-up' into an artefact.
What makes a benchmark fair. A single missing ingredient can turn a 'speed-up' into an artefact.

Think of it like…

A fair race: same track, same distance, and every runner properly trained — not a sprinter against someone who has never run before.

Real-world example

The fictional Arcadia Rail benchmarks a train-timetabling QUBO with D-Wave's hybrid solver, QAOA in simulation, Gurobi and tuned simulated annealing. Gurobi proves optimality on small instances within seconds; simulated annealing finds near-optimal answers on large ones in minutes; the annealer is competitive on mid-size instances but not cheaper. The report includes scaling curves and every solver's settings.

How it works

  1. Choose instances: realistic, varied in size, including some with known optima.
  2. Pick metrics: time-to-target, quality at fixed time, success probability — including all overheads.
  3. Tune every solver with comparable effort: hyperparameters, number of reads, time limits.
  4. Measure how runtime scales with problem size rather than reporting a single win.
  5. Report hardware, software versions, settings and both wall-clock and pure compute time; publish data and code.

Who uses it

Quantum benchmarking researchers, operations-research teams, and technical due-diligence analysts at investors and government agencies.

Key takeaway

Quote Rønnow et al. (Science 2014): defining quantum speed-up needs scaling comparisons against the best classical algorithm — and their tests on random spin glasses found none.

Going deeper

  • Rønnow et al. (Science 345, 420, 2014) distinguished 'limited' from genuine quantum speed-up and found none for random spin glasses on a 503-qubit D-Wave Two against optimised simulated annealing.
  • Denchev et al. (Physical Review X 2016) reported a D-Wave 2X up to 10⁸ times faster than single-core simulated annealing on crafted instances, but quantum Monte Carlo and other classical algorithms closed most of that gap.
  • Albash & Lidar (Physical Review X 2018) demonstrated a limited scaling advantage of a D-Wave 2000Q over simulated annealing on frustrated-loop instances, carefully not claiming advantage over all classical methods.
  • Strong baselines include parallel tempering with isoenergetic cluster moves (Zhu, Ochoa & Katzgraber, PRL 2015), tabu search, Gurobi or CPLEX, Burer-Monteiro heuristics for MaxCut, and GPU-accelerated Ising solvers.
  • The Quantum Optimization Benchmarking Library (QOBLIB; Koch et al., 2025) offers ten hard problem classes — the 'intractable decathlon' — with instances and records of best-known solutions.
  • Time-to-solution, TTS = t_run × ln(1 − 0.99)/ln(1 − p_success), is standard for annealers; for QAOA, also count shots, parameter optimisation and compilation.

Common mistakes & misconceptions

  • Comparing quantum hardware against single-threaded, untuned classical code instead of the best parallel solvers.
  • Reporting only the instances where the quantum solver wins instead of full performance distributions.
  • Ignoring overheads such as embedding, queueing, network latency and repeated parameter optimisation.

Try it: Exact brute force vs simulated annealing on an 18-spin random spin glass (Ocean, runs locally)

# pip install dimod dwave-samplers
import dimod, time
from dwave.samplers import SimulatedAnnealingSampler
bqm = dimod.generators.ran_r(1, 18, seed=7)      # random +/-1 couplings on 18 fully connected spins
t = time.time(); exact = dimod.ExactSolver().sample(bqm).first.energy; t_exact = time.time() - t
t = time.time(); sa = SimulatedAnnealingSampler().sample(bqm, num_reads=200).first.energy; t_sa = time.time() - t
print(f"exact {exact} in {t_exact:.2f}s | SA best {sa} in {t_sa:.2f}s")

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
Simulated annealing
Kirkpatrick, Gelatt & Vecchi 1983 (Science) · Algorithm · Current · Beginner
Classical heuristic that randomly walks over solutions, accepting worse moves with a probability that shrinks as 'temperature' falls. dwave-samplers' SimulatedAnnealingSampler solves a 1,000-variable sparse QUBO to good quality in seconds on a laptop.
Parallel tempering
Swendsen & Wang 1986; Hukushima & Nemoto 1996 · Algorithm · Current · Intermediate
Runs replicas at several temperatures and swaps them, escaping local minima better than single-temperature annealing. With isoenergetic cluster moves it is among the strongest classical solvers for two- and three-dimensional spin glasses.
Tabu search
Glover 1986 · Algorithm · Current · Intermediate
Local search that forbids recently changed variables for a while, preventing cycling and encouraging exploration. D-Wave includes tabu search in its classical samplers because it performs strongly on many QUBOs.
Gurobi
Gurobi Optimization · Tool · Current · Intermediate
Leading commercial mixed-integer programming solver that can solve moderate QUBOs exactly and prove optimality gaps. Gurobi solves a 200-variable dense QUBO and reports a certified optimality gap — something heuristics and annealers cannot provide.
IBM CPLEX
IBM · Tool · Current · Intermediate
Commercial solver for linear, quadratic and mixed-integer problems; a common baseline in quantum optimisation papers. Qiskit Optimization converts docplex models to QUBOs, so CPLEX and QAOA can be compared on exactly the same model.
'Defining and detecting quantum speedup'
Rønnow et al. 2014 (Science) · Paper · Current · Intermediate
Defined quantum speed-up for annealers carefully and found none for a D-Wave Two over simulated annealing on random spin glasses. Introduced the distinction between speed-up against one chosen algorithm and speed-up against the best classical algorithm.
'What is the computational value of finite-range tunneling?'
Denchev et al. 2016 (PRX) · Paper · Current · Intermediate
Showed a D-Wave 2X tunnelling edge on crafted instances, up to 10⁸ times faster than single-core simulated annealing. Quantum Monte Carlo scaled similarly to the annealer, so the edge was over simulated annealing specifically.
Scaling advantage over simulated annealing
Albash & Lidar 2018 (PRX) · Paper · Current · Advanced
Reported a limited scaling advantage of a D-Wave 2000Q over simulated annealing on frustrated-loop instances. A model of careful wording: the advantage was relative to simulated annealing, not to every classical solver.
Time-to-target (TTT)
Benchmarking practice · Metric · Current · Intermediate
Time for a solver to reach a specified quality, such as within 1% of the best-known energy, with given confidence. Arcadia Rail reports TTT at 1% and 0.1% gaps, since one solver may win at one threshold and lose at another.
QOBLIB
Koch et al. 2025 (Quantum Optimization Benchmarking Library) · Benchmark · Emerging · Intermediate
Library of ten hard optimisation problem classes with instances and track records, built for fair quantum-classical comparisons. Researchers submit new results for a problem class, recording solver, hardware, runtime and the best objective found.
Selby's algorithm
Selby 2014 · Algorithm · Legacy · Advanced
Classical solver exploiting the low-treewidth structure of Chimera graphs; it matched or beat early D-Wave hardware on native instances. It showed that hardware-native instance families can be easier classically than they first appear.
Tensor-network simulation
Matrix product states (White 1992; Vidal 2003) · Technique · Current · Advanced
Classical methods such as MPS and PEPS that simulate low-entanglement circuits or annealing dynamics, testing whether quantum results are reproducible. MPS simulations of low-depth QAOA on 100+ qubits can match hardware results when entanglement stays small.
Burer-Monteiro MaxCut heuristic
Burer, Monteiro & Zhang 2002 · Algorithm · Current · Advanced
Low-rank SDP-based heuristic for MaxCut that is fast and very strong in practice on large graphs. It handles MaxCut on graphs with tens of thousands of nodes in seconds to minutes — a tough baseline for QAOA.

6.13 Quantum-Inspired Optimisation

Quantum-inspired optimisers borrow ideas from quantum annealing and physics but run on classical hardware — special digital chips, GPUs, FPGAs or supercomputer cards. They often solve QUBOs very quickly at large scale today, which makes them both useful tools and tough competitors for quantum hardware.

All of these run on classical hardware.
The quantum-inspired landscape. All of these run on classical hardware.

Think of it like…

Like a flight simulator inspired by real planes: it captures the useful dynamics without leaving the ground — and for many training tasks it is cheaper and good enough.

Real-world example

The fictional chemicals firm Corrin Materials schedules 5,000 batch jobs every night. A GPU-based simulated-bifurcation solver finds good QUBO solutions in under a minute. The team keeps a quantum annealing pilot running alongside, but uses the quantum-inspired result in production because it is cheaper, faster to obtain and more predictable.

How it works

  1. Formulate the problem as a QUBO or Ising model, exactly as for an annealer.
  2. Choose a quantum-inspired engine: digital annealer, simulated bifurcation, GPU parallel tempering or a tensor-network optimiser.
  3. Tune engine parameters such as time limit, number of replicas and temperatures.
  4. Compare solutions against MIP solvers and quantum hardware on the same instances.
  5. Deploy whichever offers the best quality per unit cost for the use case.

Who uses it

Operations-research teams in manufacturing, finance and logistics, and vendors such as Fujitsu, Toshiba, NEC and Hitachi.

Key takeaway

When you hear 'quantum-inspired', ask what hardware it runs on — it is classical, available today, and it keeps raising the bar for quantum optimisation.

Going deeper

  • Toshiba's simulated bifurcation algorithm (Goto, Tatsumura & Dixon, Science Advances 2019) evolves classical nonlinear oscillators through a bifurcation; ballistic and discrete variants (Goto et al. 2021) improved speed and accuracy.
  • Toshiba says its SQBM+ product now supports problems with up to one billion variables and ten billion nonzero coefficients (June 2026 announcement) — a scale far beyond any quantum annealer.
  • Fujitsu's Digital Annealer is a dedicated CMOS design implementing parallel-trial Markov-chain Monte Carlo with fully connected couplings; later generations handle problems with on the order of 100,000 binary variables.
  • Microsoft's Azure Quantum optimisation (QIO) solvers, inspired by annealing and quantum Monte Carlo, were deprecated after 30 June 2023 and released as open source; Azure's Toshiba solvers were deprecated in February 2024.
  • Simulated quantum annealing (Santoro, Martoňák, Tosatti & Car, Science 2002) runs path-integral Monte Carlo of a transverse-field Ising model on classical computers and often tracks annealer scaling.
  • 'Quantum-inspired' also names Tang-style dequantised linear-algebra algorithms — a different idea, covered in the fault-tolerant chapter.

Common mistakes & misconceptions

  • Calling quantum-inspired solvers 'quantum computers': they run entirely on classical hardware, available today.
  • Dismissing them as toys: on many industrial QUBOs they currently beat available quantum hardware on scale and cost.
  • Confusing quantum-inspired optimisation (annealing-like heuristics) with quantum-inspired algorithms from dequantisation (sampling-based linear algebra).

Try it: A tiny ballistic simulated-bifurcation solver for a random Ising problem (NumPy)

import numpy as np
rng = np.random.default_rng(0)
n = 30
J = np.triu(rng.choice([-1.0, 1.0], size=(n, n)), 1); J = J + J.T   # random +/-1 couplings
def energy(s):
    return -0.5 * s @ J @ s                          # Ising energy to minimise
x = 0.01 * rng.normal(size=n); y = np.zeros(n)
dt, steps, c0 = 0.5, 2000, 0.5 / np.sqrt(n)
for k in range(steps):                               # ballistic simulated bifurcation
    a = k / steps                                    # pump ramps from 0 to 1
    y += dt * (-(1 - a) * x + c0 * J @ x)
    x += dt * y
    hit = np.abs(x) > 1
    x[hit] = np.sign(x[hit]); y[hit] = 0             # inelastic walls at +/-1
best_random = min(energy(rng.choice([-1, 1], size=n)) for _ in range(1000))
print("simulated bifurcation:", energy(np.sign(x)), "  best of 1,000 random guesses:", best_random)

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
Simulated bifurcation (SB)
Goto, Tatsumura & Dixon 2019 (Science Advances) · Algorithm · Current · Intermediate
Classical algorithm that evolves coupled nonlinear oscillators whose positions settle into ±1 spins with low Ising energy. Its updates are highly parallel, so it runs efficiently on GPUs and FPGAs for large, dense problems.
Toshiba SQBM+
Toshiba · Tool · Current · Intermediate
Commercial quantum-inspired optimisation product based on simulated bifurcation, offered in the cloud and on-premises. Toshiba has showcased simulated bifurcation on financial tasks such as fast detection of arbitrage opportunities.
Fujitsu Digital Annealer
Fujitsu · Hardware · Current · Intermediate
Dedicated digital circuit, offered as a service, that solves fully connected QUBOs with parallel-trial annealing. Fujitsu has trialled it with customers on logistics, production scheduling and drug-candidate search.
Hitachi CMOS annealer
Hitachi (Yamaoka et al. 2016) · Hardware · Research · Intermediate
CMOS chip implementing Ising spins in memory-like cells with local interactions, designed for low-power annealing. Hitachi presented it as a route to energy-efficient combinatorial optimisation at the edge.
NEC Vector Annealing
NEC · Service · Current · Intermediate
Annealing service running on NEC's SX-Aurora TSUBASA vector processor cards, marketed for large QUBO problems. NEC has also partnered with D-Wave, letting customers compare classical and quantum annealing on the same QUBO.
Microsoft QIO (retired)
Microsoft Azure Quantum · Tool · Legacy · Beginner
Azure Quantum's quantum-inspired optimisation solvers, deprecated after June 2023 and later released as open source. Older Azure Quantum optimisation tutorials no longer run; the solver code lives on in an open-source release.
Population annealing
Hukushima & Iba 2003; Machta 2010 · Algorithm · Current · Advanced
Runs a large population of annealing replicas with resampling by Boltzmann weights, parallelising well on GPUs. Used in spin-glass physics and formerly among the solvers in Microsoft's QIO suite.
Parallel-trial Monte Carlo
Fujitsu Digital Annealer design · Technique · Current · Advanced
Evaluates every possible single-bit flip at once and accepts one, avoiding long runs of rejected moves at low temperature. The Digital Annealer keeps making progress where serial simulated annealing would reject most proposals.
GPU Ising solvers
Academic and vendor codes · Tool · Current · Intermediate
Massively parallel implementations of annealing, parallel tempering or simulated bifurcation on GPUs for very large QUBOs. A single data-centre GPU runs thousands of annealing replicas of a 10,000-variable QUBO in parallel.
Simulated quantum annealing (SQA)
Santoro, Martoňák, Tosatti & Car 2002 (Science) · Algorithm · Current · Advanced
Classical path-integral Monte Carlo simulation of quantum annealing, used both as an optimiser and as an annealer benchmark. SQA's scaling often tracks D-Wave's on spin glasses, suggesting much of the hardware's behaviour is classically reproducible.
Tensor-network optimisation
Research literature · Technique · Research · Advanced
Uses tensor-network contraction or MPS-based sampling to find low-energy states of structured Ising problems. For QUBOs on graphs with low treewidth, exact tensor contraction finds ground states quickly.
Quantum-inspired evolutionary algorithms
Han & Kim 2002 (IEEE TEVC) · Algorithm · Current · Intermediate
Evolutionary algorithms that represent candidate solutions with 'Q-bit' probability amplitudes — quantum in name only. Common in engineering-design papers; treat the 'quantum' label here as a metaphor, not physics.

6.14 Realistic Expectations & Published Comparisons

After more than a decade of experiments, no quantum optimiser has shown a broad, practical advantage over the best classical methods for real-world ML or business problems. There are encouraging signs — scaling results on specific problems, coherent annealing at scale, better QAOA variants — and new claims keep appearing, but each must be checked for fair baselines, problem relevance and total cost.

The state of evidence (2026)

Shown so far Not yet shown
Quantum annealing coherent dynamics at 5,000 qubits; simulation claims practical optimisation speed-up
QAOA scaling edge in simulation (LABS) advantage on hardware for useful problems
ML via QUBO competitive with small datasets better accuracy at realistic scale
Hybrid solvers solve large industrial models proof the QPU drives the result
Fault-tolerant future provable quadratic search speed-ups practical runtimes after overheads

Real progress on the left; the claims that matter for business remain on the right.

Think of it like…

Like an early electric-car prototype winning one carefully chosen hill climb: promising engineering, but not yet the car you would buy for your daily commute.

Real-world example

The board of the fictional Harlow Logistics asks whether to invest in quantum optimisation. Their analyst summarises: annealers and QAOA match classical solvers on small instances, show limited scaling edges on crafted problems, and hybrid solvers work but hide the quantum contribution. She recommends a small, well-benchmarked pilot plus strong classical tooling, revisited every year.

How it works

  1. Identify the claim — speed, quality, scaling or cost — and the classical baseline it is measured against.
  2. Check instance relevance: crafted, random or real-world?
  3. Check end-to-end accounting: encoding, embedding, queueing, parameter training and post-processing.
  4. Look for independent replication or classical rebuttal papers.
  5. Decide between research, pilot and production — and set a date to re-evaluate.

Who uses it

Technology strategists, managers, journalists and students who need to evaluate quantum optimisation announcements.

Key takeaway

A balanced interview answer: 'No demonstrated practical advantage yet; promising scaling evidence on specific problems; fault-tolerant machines offer at most quadratic speed-ups for generic search, which overheads may cancel.'

Going deeper

  • Abbas et al. (Nature Reviews Physics 2024) conclude that quantum optimisation's value must be established by rigorous benchmarking on meaningful problems, pointing to finance and sustainability as sources of instances.
  • For QAOA, the strongest scaling evidence so far comes from noiseless simulations of specific problems such as LABS (Shaydulin et al. 2024); hardware runs remain small or noise-limited.
  • Industry 'runtime advantage' preprints in 2024-2025, for example counterdiabatic methods from Kipu Quantum run on IBM processors, should be treated as contested until replicated against tuned classical heuristics.
  • Generic unstructured search on fault-tolerant machines gains at most a quadratic speed-up; the beyond-quadratic argument of Babbush et al. (2021) suggests that alone won't give early practical advantage.
  • Montanaro's quantum-walk speed-up of backtracking (2018) and Campbell, Khurana & Montanaro's resource analysis (Quantum 2019) show fault-tolerant constraint solving might help, but only for large instances with long runtimes.
  • QOBLIB and the community working group behind the 2024 review aim to make claims comparable over time by tracking best-known results per instance.

Common mistakes & misconceptions

  • Trusting press releases over peer-reviewed comparisons; always look for the classical baseline and the instance details.
  • Dismissing the field entirely: honest negative results and narrow positive ones both guide where quantum optimisation may eventually help.
  • Ignoring cost: equal quality at higher price and latency is not an advantage for a business.

Key algorithms, circuits, techniques, tools & papers

Name What it does Example
Quantum optimisation advantage
Benchmarking literature · Concept · Research · Beginner
Demonstrably better time, quality or cost than the best classical method on a relevant problem class, with fair accounting. Beating single-core simulated annealing on crafted instances does not qualify; beating tuned parallel tempering on real schedules would.
Limited vs genuine speed-up
Rønnow et al. 2014 · Concept · Current · Intermediate
Limited speed-up beats one chosen classical algorithm; genuine speed-up beats the best known classical algorithm. Every claim should state which kind it is — most published annealing results are limited speed-ups.
Counterdiabatic optimisation claims
Kipu Quantum and others, 2024-2025 · Concept · Emerging · Intermediate
Recent announcements of hardware 'runtime advantage' using counterdiabatic-inspired circuits; independent replication with tuned baselines is still needed. Kipu Quantum's Iskay optimizer, offered through IBM's Qiskit Functions, builds on this line of work.
Hybrid attribution problem
Benchmarking practice · Concept · Current · Intermediate
In hybrid solvers it is hard to tell how much of the result comes from the QPU and how much from surrounding classical heuristics. An ablation that replaces QPU calls with simulated annealing tests whether the quantum calls matter at all.
QPU ablation study
Experimental method · Technique · Current · Beginner
Removing or replacing one component, such as the QPU, to measure its real contribution to the results. Harlow's analyst reruns the hybrid workflow with QPU calls replaced; quality is unchanged, so the QPU adds no measurable value.
Total cost of a solution
Business practice · Metric · Current · Beginner
All costs to reach a target solution — compute fees, QPU time, engineering, encoding and latency — compared across solvers. A five-cent GPU run matching a five-dollar QPU run at equal quality means the classical option wins commercially.
Diverse low-energy sampling
Research literature · Concept · Research · Intermediate
Annealers and QAOA may be valued for many different good solutions, not just the single best one. Willsch et al.'s annealer-trained SVMs combined several low-energy solutions into an ensemble to improve generalisation.
Energy-efficiency claims
Vendor literature · Concept · Current · Intermediate
Some vendors highlight low power per solution; fair comparisons must include cryogenics, control electronics and data-centre overheads. A dilution-refrigerated quantum system draws tens of kilowatts in total, comparable to a rack of GPU servers.
Quantum Optimization Working Group
IBM-convened, with academic partners · Organisation · Current · Intermediate
Community group behind the 2024 review of quantum optimisation; related efforts produced the QOBLIB benchmark library. Researchers can submit results to QOBLIB so claims are tracked against best-known solutions over time.
Quantum backtracking speed-up
Montanaro 2018; Campbell, Khurana & Montanaro 2019 · Algorithm · Research · Advanced
Quantum-walk algorithms that speed up backtracking tree search for constraint problems roughly quadratically on fault-tolerant hardware. Resource analyses suggest advantage only for large instances where both machines run for a long time.
Research, pilot, production framework
Technology strategy practice · Concept · Current · Beginner
A staged approach: follow research, run small benchmarked pilots, and adopt in production only with measured advantage. Harlow budgets one engineer for a yearly benchmark refresh instead of committing its routing system to quantum hardware.
Quantum optimisation roles
Industry · Career · Current · Beginner
Jobs combining operations research, QUBO modelling and quantum SDKs; the OR skills stay valuable whenever quantum advantage arrives. A quantum application scientist at a bank models portfolio problems, benchmarks Gurobi against QAOA, and writes the comparison report.