Adiabatic Quantum Computation

Adiabatic quantum computation (AQC) turns the adiabatic theorem into an algorithm. Instead of building a circuit from discrete gates, you encode the answer to a problem as the ground state of a Hamiltonian, prepare the easy-to-make ground state of a different Hamiltonian, and then slowly morph one into the other. If you go slowly enough, the system tracks the ground state and ends up in the answer.

The three ingredients

An adiabatic algorithm specifies:

1. A driver (or initial) Hamiltonian $H_B$ whose ground state is easy to prepare. The canonical choice on $n$ qubits is $$H_B = -\sum_{i=0}^{n-1} X_i ,$$ whose ground state is the uniform superposition $|{+}\rangle^{\otimes n}$.
2. A problem Hamiltonian $H_P$, diagonal in the computational basis, whose ground state is the bit string that solves your problem.
3. A schedule that interpolates between them, most simply the linear one $$H(s) = (1 - s)\,H_B + s\,H_P, \qquad s = t/T \in [0,1].$$

At $s = 0$ the Hamiltonian is $H_B$; at $s = 1$ it is $H_P$. The system starts in the ground state of $H_B$ and, run slowly, ends in the ground state of $H_P$.

The algorithm

1. Prepare $|\psi(0)\rangle = |{+}\rangle^{\otimes n}$, the ground state of $H_B$.
2. Evolve under $H(s)$ for total time $T$, where $T$ is chosen large enough that the evolution is adiabatic — set by the minimum spectral gap of $H(s)$.
3. Measure in the computational basis. With high probability the outcome is the ground state of $H_P$, i.e. the solution.

Why it can be powerful

The cost of the algorithm is dominated by the runtime $T$, which the adiabatic theorem ties to $1/\Delta_{\min}^2$. For problems where the minimum gap shrinks only polynomially in the system size, AQC runs in polynomial time. For hard problems the gap can close exponentially fast, forcing exponential runtime — exactly mirroring the difficulty seen in the circuit model.

Relation to quantum annealing

Physical devices that implement a noisy, finite-temperature, open-system version of this idea are called quantum annealers. They use the same $H_B \to H_P$ interpolation but do not guarantee perfect adiabaticity: thermal noise and fast schedules allow excitations. AQC is the idealized, closed-system, zero-temperature limit; annealing is its practical, heuristic cousin. The remaining lessons make the Hamiltonians, schedules, and gap analysis concrete, and you will simulate small instances directly.

Sign in on the full site to ask questions and join the discussion.