Quantum Annealing

Overview

Quantum annealing is a method for finding low-cost solutions to optimization problems by using quantum fluctuations. The problem is encoded as an energy landscape over bit strings. The system starts in a simple quantum state in which all bit strings are equally likely, and a transverse magnetic field is gradually turned down while the problem energies are turned up. If this is done slowly enough, the system tends to end in the lowest-energy configuration, the best answer.

It is the idea behind D-Wave's computers, the first commercial quantum machines. Quantum annealing is different from gate-based quantum computing. It is an analog process rather than a sequence of logic gates, and it targets optimization and sampling instead of general algorithms.

The problem it solves

Finding near-optimal solutions to combinatorial optimization problems (like scheduling, routing, or portfolio selection).

History and background

The idea that quantum tunneling could help escape local minima in optimization appeared in the late 1980s, and Apolloni, Carvalho, and De Falco proposed quantum stochastic optimization in 1989. Tadashi Kadowaki and Hidetoshi Nishimori's 1998 paper formulated quantum annealing for the transverse-field Ising model and demonstrated it numerically, which is the paper most often cited as the origin of the modern method. In 2001 Farhi and colleagues described the closely related adiabatic quantum computation.

D-Wave sold the first commercial machine in 2011, the D-Wave One, and later generations grew from 128 qubits to more than 5,000 in the Advantage system and more than 4,400 in Advantage2, released in 2025. Whether annealers beat classical algorithms has been debated for more than a decade. Google and D-Wave reported in 2016 a large speedup over simulated annealing for a specific problem, but classical quantum Monte Carlo methods matched it. In 2025 D-Wave published a Science paper claiming a beyond-classical simulation of magnetic materials, which other researchers contested with tensor-network calculations.

How it works

Starts qubits in a simple, easily prepared quantum state and slowly evolves the system toward a final configuration encoding the problem, exploiting quantum tunneling to escape local minima that would trap classical methods.

Think of the cost of each bit string as the height of a landscape. A classical optimizer such as simulated annealing explores the landscape by random hops that sometimes go uphill, with the temperature controlling how often. Quantum annealing explores it by quantum superposition and tunneling: the system can pass through a thin barrier rather than climbing over it.

The Hamiltonian is a sum of two terms. The driver, a transverse field, causes bits to flip between 0 and 1 and spreads the system over all configurations. The problem Hamiltonian assigns energies to configurations according to the cost function. A schedule decreases the driver and increases the problem term. The adiabatic theorem says that if the change is slow compared with the minimum gap between the ground state and the first excited state, the system stays in the ground state.

Real devices are not perfectly adiabatic. They operate at finite temperature, with noise and a limited annealing time, so they behave as heuristic samplers that return low-energy states with some probability. Users run the anneal many times and keep the best result.

Step by step

1. Formulate the problem as an Ising model or a quadratic unconstrained binary optimization, which assigns an energy to each bit string using linear and pairwise terms.
2. Map the variables to qubits using minor embedding, because the hardware couples qubits only in a specific pattern. Variables that interact with many others are represented by chains of physical qubits.
3. Set the qubit biases and coupler strengths to match the problem, and choose an annealing time and schedule.
4. Run the anneal: the transverse field starts large and decreases while the problem Hamiltonian grows.
5. Read out the qubits to obtain a bit string, which is a candidate solution. Repeat for hundreds to thousands of anneals.
6. Unembed the chains, repair broken chains, and choose the lowest-energy sample. Optionally refine it with classical post-processing.

A worked example

Consider a small scheduling problem of three tasks and two time slots, where conflicts penalize two tasks in the same slot. Each task-slot pair is a binary variable. The cost function adds a penalty when two conflicting tasks take the same slot and when a task is assigned zero or two slots. This is written as a QUBO with a handful of coefficients.

On the annealer, each variable becomes a qubit, and each penalty becomes a coupling. After several hundred anneals, the lowest-energy samples correspond to valid schedules with no conflicts. For real problems with thousands of variables, D-Wave's hybrid solvers split the problem into pieces for the annealer and combine the results classically.

Complexity and resources

What hardware it needs

• Superconducting flux qubits cooled to about 15 millikelvin with programmable couplers, as in D-Wave systems.
• Low-noise control of qubit biases and couplings, with enough connectivity to embed the problem.
• Alternative implementations include trapped ions and Rydberg atom arrays that emulate the Ising model.

Applications

• Scheduling, logistics, and routing optimization in industry pilots.
• Sampling from Boltzmann distributions for machine learning.
• Simulating quantum magnetism and spin glasses.
• Portfolio optimization, traffic flow, and manufacturing planning case studies.

Limitations and caveats

• No broad, unambiguous speedup over the best classical solvers has been demonstrated on commercially relevant problems.
• Noise and finite temperature prevent true adiabatic evolution.
• Embedding overhead limits the effective problem size, and chain breaks degrade results.
• Only stoquastic Hamiltonians are implemented, which limits the quantum effects that can be used.

Common misconceptions

• Quantum annealing does not try all solutions at once. It is a physical process that tends to settle into low-energy states.
• It is not the same as gate-based quantum computing, and its qubit counts are not comparable.
• It does not solve NP-hard problems in polynomial time.

How it compares

• QAOA is a gate-based counterpart that discretizes the evolution and optimizes the step sizes.
• Adiabatic quantum computation is the theoretical framework, proven equivalent to gate-based computing when non-stoquastic terms are included.
• Simulated annealing uses thermal hops instead of quantum tunneling and runs on any computer.

Real-world impact

Commercially available today via D-Wave's quantum annealers, used in early-stage optimization research, though whether it provides genuine quantum advantage over classical heuristics remains debated.

Why it matters

Quantum annealing is the oldest commercialized quantum computing approach, and the experience of using it has taught the industry about benchmarking, embedding, and hybrid workflows. It shows that even without full fault tolerance, specialized quantum devices can be built and sold.

Whether annealers will give real advantage remains one of the most debated questions, which makes the field a good place to learn how to evaluate claims by comparing with the strongest classical baselines.

Frequently asked questions

Keep learning

• Related algorithm: Adiabatic Quantum Computation
• Related algorithm: Quantum Approximate Optimization Algorithm (QAOA)
• Related algorithm: Quantum Boltzmann Machine (QBM)
• Related algorithm: Max-Cut with Quantum Algorithms (QAOA and Quantum Max-Cut)

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database