Adiabatic Quantum Computation

Overview

Adiabatic quantum computation, or AQC, solves a problem by slowly changing a quantum system. The answer is encoded in the lowest-energy state, or ground state, of a Hamiltonian that describes the problem. The system starts in the easy-to-prepare ground state of a simple Hamiltonian and is slowly deformed into the problem Hamiltonian. The adiabatic theorem guarantees that if the change is slow enough, the system stays in its ground state and ends up in the answer.

AQC is a full model of quantum computation. Aharonov, van Dam, Kempe, Landau, Lloyd, and Regev proved that it is polynomially equivalent to the standard circuit model. It is also the theoretical foundation of quantum annealing and the inspiration for QAOA.

The problem it solves

Solving general computational problems by slowly evolving a quantum system from an easy starting configuration toward one encoding the desired answer.

History and background

The adiabatic theorem goes back to Max Born and Vladimir Fock in 1928. In 2000 Farhi, Goldstone, Gutmann, and Sipser proposed using it for computation in a paper called Quantum Computation by Adiabatic Evolution. In 2001 the same group, with Lapan and Preda, published numerical evidence in Science that the method could solve random instances of an NP-complete problem, exact cover, with up to 20 bits in a time that appeared to grow polynomially.

Later work cooled that optimism. Van Dam, Mosca, and Vazirani showed in 2001 that some instances need exponential time because the energy gap becomes exponentially small, and Altshuler, Krovi, and Roland argued in 2010 that Anderson localization causes failure on random instances. In 2002 Roland and Cerf showed that adiabatic evolution can reproduce Grover's square-root speedup if the schedule is adapted to the gap. In 2004 and 2007 Aharonov and coauthors proved the equivalence to the circuit model, and Kempe, Kitaev, and Regev showed the required Hamiltonians can be 2-local or 3-local.

How it works

Starts the system in an easily prepared low-energy state and gradually changes its governing equations so that, if done slowly enough, the system stays in its lowest-energy state — which is engineered to represent the problem's solution.

Think of a ball in a landscape. If you carefully carry it from one valley to the next on a slowly tilting tray, it stays at the bottom of the valley it started in. In quantum mechanics the analogue is a system in its ground state of a Hamiltonian H of s, where s goes from 0 to 1. If s changes slowly enough, the system remains in the instantaneous ground state.

How slow is slow enough depends on the minimum energy gap between the ground state and the first excited state during the evolution. The required time scales as one over the square of the minimum gap. If the gap stays large, the computation is fast. If the gap becomes exponentially small, the time is exponential.

The design problem is to choose a starting Hamiltonian whose ground state is easy to prepare, such as all qubits pointing along the x axis, and a final Hamiltonian whose ground state encodes the answer, such as an Ising energy over bit strings that equals the cost. The interpolation between them, called the schedule, can be linear or adapted to the gap.

Step by step

1. Encode the problem in a final Hamiltonian H sub P whose ground state is the solution, for example by assigning each bit string an energy equal to its cost.
2. Choose an initial Hamiltonian H sub 0 with a known, easily prepared ground state, such as a uniform transverse field.
3. Prepare the system in the ground state of H sub 0.
4. Evolve under H of s equal to one minus s times H sub 0 plus s times H sub P, with s increasing from 0 to 1 over a total time T.
5. Measure the final state in the computational basis. If T was long enough compared with the inverse square of the minimum gap, the result is the ground state with high probability.
6. Verify the solution classically, and repeat or increase T if needed.

A worked example

For Grover search over N items with one marked item, take H sub 0 as the projector onto the uniform superposition and H sub P as the projector onto the marked item. With a linear schedule, the minimum gap is about one over the square root of N, so the required time is of order N, no better than classical search. If the schedule slows down only near the point of minimum gap, as Roland and Cerf showed, the time is of order the square root of N.

For an optimization problem such as MaxCut on a small graph, the final Hamiltonian counts uncut edges. The adiabatic path leads the system from the equal superposition to the maximum cut, as long as the gap does not close too fast. For hard instances, the gap can shrink exponentially, which is the main obstacle to the method solving NP-hard problems quickly.

Complexity and resources

What hardware it needs

• Programmable Hamiltonians with controllable couplings, as in superconducting flux-qubit annealers.
• Long coherence relative to the evolution time, or error suppression techniques for AQC.
• For universality, non-stoquastic interactions, which current annealers do not implement.

Applications

• Optimization and sampling, implemented approximately by quantum annealers.
• Ground-state preparation for quantum chemistry and condensed matter, as in adiabatic state preparation.
• A theoretical framework for studying quantum phase transitions and gaps.
• Universal quantum computation in architectures where adiabatic control is natural.

Limitations and caveats

• The gap can close exponentially fast, making evolution times impractical.
• Calculating the gap is itself a hard problem, so the required time is hard to know in advance.
• Thermal and control noise excite the system out of the ground state in real devices.
• Only stoquastic Hamiltonians are available on current annealers, which may limit power.

Common misconceptions

• AQC does not solve NP-hard problems efficiently in general. Hard instances have tiny gaps.
• Quantum annealing is not exactly the same as AQC. Annealers operate at finite temperature, with noise and finite times.
• It is not slower in principle than circuit-model computing. The two are polynomially equivalent.

How it compares

• Quantum annealing is the noisy, hardware version of the same idea.
• QAOA uses a few discrete steps with optimized angles instead of a slow ramp.
• Gate-model algorithms such as Shor's require different primitives but can be simulated by AQC with polynomial overhead.

Real-world impact

Proven theoretically equivalent in computational power to standard gate-based quantum computing, and forms the theoretical basis for quantum annealing hardware like D-Wave's systems.

Why it matters

AQC provides a different way to think about quantum computation, in terms of energy landscapes and gaps instead of circuits. It connects computational complexity to physics, since the hardness of problems appears as the closing of an energy gap.

It also underpins the entire quantum annealing industry, so understanding it is the key to judging what annealers can and cannot do.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Annealing
• Related algorithm: Quantum Approximate Optimization Algorithm (QAOA)
• Related algorithm: Grover's Algorithm
• Related algorithm: Quantum Imaginary Time Evolution (QITE)

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