Equivalence to the Circuit Model

A natural worry about adiabatic quantum computation is that it might be weaker than the gate model — perhaps it can only handle optimization, not general quantum algorithms. A landmark result settles this: adiabatic quantum computation is polynomially equivalent to the standard circuit model. Anything one can do efficiently, the other can too.

What "equivalent" means

Two models of computation are polynomially equivalent if each can simulate the other with only polynomial overhead in time and space. Concretely, for AQC and circuits:

Any quantum circuit of $g$ gates on $n$ qubits can be simulated by an adiabatic computation with a Hamiltonian on $\mathrm{poly}(n, g)$ qubits whose minimum gap is at least $1/\mathrm{poly}(n, g)$ , so the runtime is polynomial.
Any adiabatic computation with an inverse-polynomial gap can be simulated by a polynomial-size quantum circuit.

The first direction is the surprising and harder one, established by Aharonov and collaborators. It means AQC is universal for quantum computation, not merely an optimization heuristic.

The history-state idea

The construction encodes the entire history of a circuit into the ground state of a local Hamiltonian. If the circuit applies gates $U_1, U_2, \ldots, U_g$ to an input $|\psi_0\rangle$ , define the intermediate states $|\psi_t\rangle = U_t \cdots U_1 |\psi_0\rangle$ . A clock register counting the step $t$ tags each one, and the target ground state is the uniform superposition over the whole computation, the history state

|\eta\rangle = \frac{1}{\sqrt{g+1}} \sum_{t=0}^{g} |\psi_t\rangle \otimes |t\rangle_{\text{clock}}.

A carefully designed local Hamiltonian — penalizing wrong inputs, wrong gate applications, and illegal clock states — has exactly $|\eta\rangle$ as its ground state. Adiabatically reaching $|\eta\rangle$ and then measuring the clock in the " $t = g$ " subspace yields the circuit's output. This is closely tied to the Feynman–Kitaev clock construction and the QMA-completeness of the local Hamiltonian problem.

Why this matters

The equivalence has two consequences. First, it tells algorithm designers that AQC loses no computational power: any speedup achievable with circuits is in principle achievable adiabatically, and vice versa. Second, it sharply separates the universal, closed-system adiabatic model from practical quantum annealers, which are noisy, finite-temperature, and restricted to stoquastic (sign-problem-free) Hamiltonians. Those restrictions are believed to limit annealers, and they are not known to be universal — so the elegant equivalence theorem applies to idealized AQC, not to today's annealing hardware.