Equivalence of Adiabatic and Circuit Models

You have now met two ways to compute with quantum mechanics. In the circuit model — the one Shor, Grover, and every textbook uses — you line up qubits, apply a sequence of one- and two-qubit gates like H, CNOT, and T, and measure at the end. The whole computation is a choreographed sequence of operators that you, the programmer, specified explicitly. In adiabatic quantum computing, you do something that looks completely different: you pick a simple Hamiltonian H_0 whose ground state is a uniform superposition, a problem Hamiltonian H_p whose ground state encodes the answer, and then you slowly interpolate between them. There are no gates. There is no circuit diagram. There is a piece of physics, running according to Schrödinger's equation, with a dial you twist from 0 to 1 over time T.

If a friend showed you these two machines without labels, you would swear they were solving different problems. Circuits look like computer science; adiabatic evolution looks like condensed-matter physics. The operations, the hardware, the intuition — everything is different. In 2004, Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev published a paper proving that these two models are polynomially equivalent [1]. Anything a circuit can compute in polynomial time, an adiabatic evolution can compute in polynomial time. Anything an adiabatic evolution can compute in polynomial time, a circuit can compute in polynomial time. The two machines are the same machine, just wearing different clothes.

The proof is constructive in both directions. Going from adiabatic to circuit is the easier direction and essentially amounts to Trotter decomposition — you approximate e^{-iH(t)t} by a product of short-time evolutions, each of which is a constant-depth circuit. Going from circuit to adiabatic is harder and cleverer. It uses a construction Kitaev invented in 1999 for a completely different purpose (proving QMA-completeness of the local-Hamiltonian problem — the quantum Cook-Levin theorem): a history-state Hamiltonian whose ground state is a superposition over every intermediate snapshot of the circuit's execution, correlated with a clock register that says "I am at step \ell."

This chapter explains both directions carefully, works through two small explicit examples, and draws out the consequences. By the end, you should be able to look at a circuit and sketch, in words, how it becomes an adiabatic evolution — and conversely, look at an adiabatic schedule and sketch how it becomes a circuit. More importantly, you should understand what the equivalence does and does not tell you: it says AQC is universal (good news for AQC advocates) and it says AQC is no more powerful than the circuit model (bad news for anyone hoping AQC can crack NP-complete problems on its own).

The statement, precisely

Here is what "polynomially equivalent" means, unpacked.

Applied to our case: the circuit model with one- and two-qubit gates defines the complexity class BQP (bounded-error quantum polynomial time). The Aharonov–van Dam theorem says adiabatic quantum computing, suitably defined, also defines BQP. They are the same class.

The "suitably defined" caveat matters. Adiabatic computation has knobs that the circuit model does not: how local the Hamiltonian is allowed to be, how large the spectral gap must stay, whether the Hamiltonian's matrix elements are positive or complex (the "stoquastic" vs "non-stoquastic" distinction). The strongest form of the equivalence theorem — and the one most widely cited — uses:

• k-local Hamiltonians with k fixed (e.g. k = 5 in the original proof, improved to k = 2 in later work).
• Polynomially-small spectral gap: g_{\min} \ge 1/\text{poly}(n). Since the adiabatic runtime scales as 1/g_{\min}^2, this gives polynomial-time evolution.
• Bounded Hamiltonian norms: each local term has norm O(1), so the total \|H\| = O(\text{poly}(n)).

Under these conditions, AQC = BQP. Weaker conditions give weaker results: if you restrict to stoquastic Hamiltonians, you get a class called StoqMA or equivalent, which may be strictly smaller than BQP; if you allow the gap to shrink exponentially, you might escape BQP but the evolution time blows up correspondingly. The clean picture is "polynomial gap, local Hamiltonian, universal AQC = circuit-model BQP."

Adiabatic to circuit — the easy direction

Start with the easier direction, because it builds intuition for what an adiabatic evolution is as a unitary operator. Given an adiabatic schedule H(s) = (1-s) H_0 + s H_p with s = t/T running over 0 \le t \le T, the state evolves according to Schrödinger's equation:

The solution is |\psi(T)\rangle = U_{\text{ad}} |\psi(0)\rangle where

with \mathcal{T} denoting time-ordering. This U_{\text{ad}} is a perfectly ordinary unitary matrix on the Hilbert space of n qubits. You could, in principle, write it down as a 2^n \times 2^n matrix. To simulate the adiabatic evolution on a gate-based quantum computer, you need to build a circuit that implements U_{\text{ad}}.

The tool is Trotter-Suzuki decomposition. Slice the interval [0, T] into M small steps of size \Delta t = T/M. Within each slice, treat H as approximately constant:

where t_k = k \Delta t and the product is time-ordered (most recent on the left). The error from treating H as constant within each slice is O(\Delta t^2) per slice, or O(T \cdot \Delta t) = O(T^2/M) total — shrinks as M grows.

Why the constant-Hamiltonian approximation works per-slice: within a slice of length \Delta t, the Hamiltonian changes by about \Delta t \cdot \partial_t H = O(1/M) (since \partial_t H \sim 1/T for a linear schedule and \Delta t = T/M). So within one slice, H is constant up to an error that shrinks as M grows. Evolving under a constant Hamiltonian for time \Delta t is just the matrix exponential e^{-iH\Delta t}. The Trotter error bound says the cumulative error from stitching M such slices together is O(T^2/M).

Now each matrix exponential e^{-iH(t_k) \Delta t} must itself be turned into a gate sequence. Since H(t_k) = (1 - s_k) H_0 + s_k H_p is a sum of two Hamiltonians, use Trotter's formula again:

Applied to our splitting:

Because H_0 and H_p are each k-local Hamiltonians (sums of polynomially many terms, each acting on at most k qubits), each individual exponential e^{-i h_i \Delta t} is a small unitary on at most k qubits, which can be decomposed into a constant-depth circuit of one- and two-qubit gates using the Solovay-Kitaev theorem.

Stitching it all together: the total circuit size is O(M \cdot \text{(terms in }H\text{)}\cdot\text{constant}) = O(M \cdot \text{poly}(n)). Choosing M = \text{poly}(n, T) large enough to keep Trotter error below a desired \epsilon, and noting that the adiabatic theorem requires T = O(1/g_{\min}^2) = O(\text{poly}(n)) when the gap is polynomial, gives a total circuit of size \text{poly}(n). Done.

The takeaway: any adiabatic evolution with polynomial gap is simulated by a polynomial-size circuit. The overhead is multiplicative and manageable. Shor's factoring run adiabatically would become Shor's factoring run as a circuit, plus a Trotter-sized-polynomial blow-up.

Circuit to adiabatic — the clever direction

Now the harder direction. Given a quantum circuit U = U_L U_{L-1} \cdots U_2 U_1 of L gates acting on n qubits, build an adiabatic evolution whose ground state at s = 1 encodes the circuit's output. This is the direction that required the key new idea, and the idea is Kitaev's history-state construction.

The history state

A quantum circuit running on input |\psi_0\rangle produces a sequence of intermediate states:

where |\psi_\ell\rangle = U_\ell U_{\ell-1} \cdots U_1 |\psi_0\rangle is the state after \ell gates. The output of the computation is |\psi_L\rangle.

Kitaev's idea: introduce a separate clock register that can store values \ell = 0, 1, \ldots, L (this takes \lceil \log_2(L+1) \rceil qubits, or in the unary encoding used in most proofs, L+1 qubits). Define the history state

Why a uniform superposition over clock values: we want a single state that simultaneously "remembers" every intermediate step of the computation. The clock register is the index \ell; the computation register is the state at step \ell; the sum ties them together. The factor 1/\sqrt{L+1} normalises. Measuring the clock register collapses the computation register to whatever state it was in at that time step — including the final output at \ell = L.

If you can prepare the history state |\eta\rangle, you can extract the computation's output: measure the clock register, and conditional on getting \ell = L (which happens with probability 1/(L+1)), the computation register is in |\psi_L\rangle. The probability 1/(L+1) is only polynomially small, so repeating the whole process polynomially many times gets the output with high probability.

The question becomes: can we prepare the history state via adiabatic evolution? And that is where the Hamiltonian engineering comes in.

The history-state Hamiltonian

Construct a Hamiltonian H_{\text{hist}} on the joint clock + computation Hilbert space, built from three kinds of penalty terms:

1. Clock-validity terms, H_{\text{clock}}: penalise any clock state that isn't a valid unary-encoded clock value. In the unary encoding, a valid clock is a string like 1^\ell 0^{L-\ell} — some number of 1's followed by 0's. Any invalid pattern gets energy > 0.

2. Initial-state terms, H_{\text{init}}: penalise the configuration (clock = 0, computation \ne |\psi_0\rangle). This says "if the clock is at the start, the computation register must hold the initial state."

3. Propagation terms, H_{\text{prop}}: for each gate U_\ell, a term that penalises the configuration "clock is at \ell, computation register does NOT equal U_\ell applied to whatever was there at clock \ell - 1." Concretely, for each \ell:

The total history-state Hamiltonian is

Key claim: H_{\text{hist}} has a unique ground state, and that ground state is exactly the history state |\eta\rangle, with energy 0.

Why the history state is the unique zero-energy ground state: each term in H_{\text{hist}} is positive semi-definite (you can check the matrix of each propagation term is a projector times a scalar). So the total energy is zero iff every term's expectation is zero. H_{\text{clock}} being zero means the state is a superposition over valid clock values. H_{\text{init}} being zero means the clock-0 component holds |\psi_0\rangle. H_{\text{prop}} being zero forces consistency: the state at clock \ell must equal U_\ell applied to the state at clock \ell-1, for every \ell. The only state satisfying all three is |\eta\rangle.

The other crucial property: H_{\text{hist}} has a spectral gap g = \Omega(1/L^2) between the ground state and the first excited state. This is a non-trivial theorem (Kitaev 1999, improved by later authors); the key step is noticing that H_{\text{prop}} looks like a random-walk kernel on the clock register, whose gap is controlled by the 1/L^2 scaling of discrete Laplacian spectra.

The adiabatic sweep

Now you have everything. Define:

• H_0 (easy): a Hamiltonian whose ground state is trivial to prepare. For instance, |0\rangle^{\otimes \text{everything}} in the computation register, with the clock in |0\rangle_{\text{clock}} (i.e., clock says "step zero").
• H_p (problem): H_{\text{hist}}, the history-state Hamiltonian for the target circuit U.

Interpolate: H(s) = (1-s) H_0 + s H_{\text{hist}}. The ground state of H(0) is the trivial initial state; the ground state of H(1) is the history state. If the interpolation is slow enough, the adiabatic theorem takes the initial state to the history state.

The runtime: the gap of H(s) along the path is bounded below by 1/L^2 (actually tighter analysis gives 1/L^{2+o(1)} for specific constructions). So the adiabatic time is T = O(1/g_{\min}^2) = O(L^4). Measuring the clock and post-selecting on outcome L succeeds with probability 1/(L+1). Total expected time: O(L^5) — polynomial in L and n.

That is the theorem. Any circuit U of depth L can be simulated by an adiabatic evolution on n + O(L) qubits (including the clock), running for time \text{poly}(n, L), using only k-local terms in the Hamiltonian (originally k = 5 in Kitaev; Kempe, Kitaev, Regev improved to k = 3; Oliveira and Terhal pushed to k = 2 on a 2D lattice [2]).

A tiny intuition for the gap bound

Why is the spectral gap of H_{\text{hist}} of order 1/L^2? Here is the flavour, without a full proof.

Restrict attention to the subspace where H_{\text{clock}} and H_{\text{init}} are zero — i.e., the subspace of valid clock configurations with the initial computation state. On this subspace, the propagation Hamiltonian H_{\text{prop}} acts like a discrete second derivative on the clock register. Specifically, let W = U_\ell U_{\ell-1} \cdots U_1 map the computation state at step 0 to step \ell. Then in the basis rotated by W, H_{\text{prop}} becomes the Laplacian-like operator \sum_\ell |\ell\rangle\langle\ell| - \tfrac{1}{2}(|\ell-1\rangle\langle\ell| + |\ell\rangle\langle\ell-1|). This is the discrete Laplacian on a line of length L+1, and its smallest non-zero eigenvalue is well-known to scale as 1/L^2 (by analogy with the continuous Laplacian on an interval).

The "circuit-to-adiabatic" construction, in other words, turns the circuit-depth cost of the computation into a spectral-gap cost of the Hamiltonian. A deep circuit becomes a tight gap becomes a long adiabatic time. Same fundamental difficulty, translated.

Worked examples

|0⟩ ─ H ──[R_x(α_1)]─●──[R_z(θ_1)]─●──── ... (repeat slice 200 times)
                     │               │
|0⟩ ─ H ──[R_x(α_2)]─⊕───────────────⊕─●──[R_z(θ_2)]─●── ...
                                       │               │
|0⟩ ─ H ──[R_x(α_3)]───────────────────⊕───────────────⊕── ...

Why this matters — the implications

AQC is universal

Before Aharonov–van Dam, it was not obvious that adiabatic quantum computing could do everything the circuit model could. Early AQC papers gave efficient adiabatic algorithms for specific problems (unstructured search, certain optimisation instances), but a general recipe for simulating arbitrary circuits was missing. The history-state construction closes this gap. Whatever you can compute with gates, you can compute by Hamiltonian engineering.

AQC is not more universal

The equivalence goes both ways. Whatever you can compute adiabatically, you can compute with gates, with only polynomial overhead. AQC does not secretly solve problems that circuits cannot. In particular:

• AQC does not solve NP-complete problems in polynomial time. If it did, so would circuit-model BQP — contradicting the widely-believed conjecture that \text{NP} \not\subseteq \text{BQP}.
• AQC does not break the BBBV lower bound. The optimal quantum search algorithm is Grover's O(\sqrt N) search. Adiabatic search matches this — no better — because it is the same computational class.
• Hard problems are still hard. An NP-hard instance that requires an exponentially-deep circuit in the gate model becomes an adiabatic evolution with an exponentially-small spectral gap, forcing exponentially-long runtime. The difficulty does not disappear; it gets re-expressed.

The "barren plateau" analogue

Readers who have met the barren-plateau problem in variational quantum algorithms may notice a parallel. Variational circuits suffer from exponentially-vanishing gradients on random parameterisations — an obstacle to training. AQC suffers from exponentially-vanishing spectral gaps on hard problem instances — an obstacle to efficient runtime. Both are specific forms of the same meta-phenomenon: quantum hardness, when translated between formulations, becomes a small number somewhere. In the circuit picture it is circuit depth; in the adiabatic picture it is spectral gap; in the variational picture it is gradient magnitude. There is no free lunch, only different plates at the same table.

Practical consequences

For algorithm designers, the equivalence means you can design in whichever model is easier and translate later. Many optimisation algorithms are more naturally described adiabatically (you are sliding a Hamiltonian), while many number-theoretic algorithms are more naturally described circuit-style (you are composing phase-kickback tricks). Pick the description that fits the problem, and the other description is only a polynomial Trotter away.

For hardware builders, the equivalence means both kinds of machines are legitimate universal quantum computers. D-Wave's quantum annealers are a restricted form of adiabatic hardware; IBM's gate-model superconducting processors are circuit hardware. The universality theorem says a sufficiently powerful adiabatic machine (with arbitrary multi-qubit Hamiltonians, not just 2-local Ising) would be equivalent to a sufficiently powerful gate-model machine. The engineering trade-offs differ, but the computational goalposts are the same.

Common confusions

• "The equivalence means AQC and circuits are literally the same." They are not — they are polynomially equivalent in computational power. Their internal mechanics are different; their runtimes can differ by polynomial factors; their sensitivity to noise and error correction is quite different. "Same complexity class" is a much weaker claim than "identical machines."
• "Because AQC is universal, D-Wave can run Shor's algorithm." D-Wave's hardware implements a restricted form of AQC where H_p is limited to 2-local Ising terms. Universal AQC in the Aharonov–van Dam sense requires arbitrary multi-qubit interactions (and, technically, non-stoquastic Hamiltonians). D-Wave cannot run Shor's algorithm natively; that would require different hardware supporting the full set of local terms.
• "The history-state construction is just a trick." It is an essential trick. The "clock register" encodes the circuit's computational history in a single quantum state, turning a time-sequential computation into a single ground-state-finding problem. This exact idea is what lets Kitaev prove QMA-completeness of the local-Hamiltonian problem — the quantum analogue of the Cook–Levin theorem [3].
• "Trotter decomposition is a physics approximation, so adiabatic-to-circuit is inexact." Trotter has error O(T^2/M), which shrinks arbitrarily as the slice count M grows. You can always pick M large enough (but still polynomial) to drive the error below any desired threshold \epsilon. So the simulation is inexact in the same sense as "you need more than one bit of precision to simulate real numbers" — a finite, polynomial cost.
• "Aharonov–van Dam showed AQC equals BQP, therefore it equals classical BPP." No. The equivalence is among quantum models. BQP is widely believed to be strictly larger than BPP (the class of classical polynomial-time algorithms with randomness). Shor's factoring is in BQP but is not known to be in BPP. Since AQC = BQP, AQC can factor efficiently too; classical machines (probably) cannot.
• "If gap closes polynomially, AQC is fast; if it closes exponentially, it is slow." Correct, but the direction of the implication matters. It is the problem that determines the gap, not the algorithm designer. You can choose H_0 and the interpolation schedule, but for NP-hard problems no natural choice of Hamiltonian gives a polynomial gap — because if it did, NP would equal BQP, which is not believed.

Going deeper

The spectral gap bound — sketch

For the history-state Hamiltonian H_{\text{hist}} on L+1 clock steps, the gap analysis proceeds via a unitary change of basis. Define

In the rotated frame, H_{\text{prop}} becomes a clock-only operator:

This is the discrete Laplacian on the path graph with L+1 nodes. Its smallest non-zero eigenvalue is 2 \sin^2(\pi/(2(L+1))) \approx \pi^2/(2 L^2) for large L — the classic 1/L^2 scaling. The full analysis (with H_{\text{init}} and H_{\text{clock}} included) shows the gap of H_{\text{hist}} is at least \Omega(1/L^2); with tighter modifications (Caha, Landau, Nagaj 2018) it can be made \Omega(1/L), matching a natural lower bound.

From 5-local to 2-local — the locality reduction

Kitaev's original construction used 5-local Hamiltonian terms. Kempe, Kitaev, and Regev (2006) improved to 3-local via perturbation gadgets: terms that encode a high-weight interaction in the low-energy sector of a stronger 2-local or 3-local Hamiltonian. Oliveira and Terhal (2008) further reduced to 2-local on a 2D square lattice [2]. The 2-local result is optimal: 1-local Hamiltonians cannot encode any non-trivial computation, since their ground states are products of single-qubit ground states.

The perturbation-gadget idea is elegant. You want a 3-body term h_{ijk}, but your hardware only has 2-body terms. Add an ancilla qubit a and a strong 2-body Hamiltonian \lambda H_{\text{penalty}} that forces a into a specific state in the low-energy sector. Design 2-body couplings between i, j, k, a such that, in the effective low-energy theory (obtained by Schrieffer-Wolff perturbation theory in powers of 1/\lambda), the 3-body term h_{ijk} emerges at second or third order. The ground state and low-lying spectrum of the gadget Hamiltonian reproduces that of the original 3-body Hamiltonian, up to corrections that vanish as \lambda \to \infty.

Stoquastic vs non-stoquastic

A Hamiltonian H is stoquastic (in some basis) if all off-diagonal matrix elements in that basis are real and non-positive. Stoquastic Hamiltonians have special structure: their ground states can be written as superpositions with non-negative coefficients (they look like classical probability distributions), and their thermal states admit efficient classical Monte Carlo simulation.

Here is the catch: the history-state Hamiltonian in its natural form is stoquastic only for a restricted class of circuits. For general universal circuits, H_{\text{hist}} is non-stoquastic. So the Aharonov–van Dam equivalence — that AQC = BQP — relies on non-stoquastic Hamiltonians. If you restrict to stoquastic AQC (which is what D-Wave hardware implements), you get a smaller complexity class, widely conjectured to sit between MA and BQP, called StoqMA.

The practical consequence is sobering: D-Wave's flux-qubit annealers are stoquastic. Even as an adiabatic machine, they are not universal in the full BQP sense. Building a non-stoquastic universal adiabatic machine — with something like XY-type or XZX-type couplings — is a distinct (and harder) hardware engineering challenge.

Beyond BQP — adiabatic complexity classes

The equivalence theorem pins AQC at BQP when the gap is polynomially small. If you allow the gap to be exponentially small and accept an exponentially-long evolution time, adiabatic evolution climbs up to PSPACE or even higher — because you can explore the energy landscape arbitrarily slowly. If you allow the gap to be constant (harder problems forbidden), you land in a strictly smaller class.

These fine-grained distinctions give a rich complexity-theoretic picture:

• Constant gap, polynomial Hamiltonian norm: AQC can solve problems in a class sometimes called BPL (bounded-error quantum logspace).
• Polynomial inverse gap: BQP (the Aharonov–van Dam regime).
• Exponential inverse gap, exponential evolution time: PSPACE, which includes NP.
• Exponential inverse gap, polynomial evolution time: fails to converge to the ground state; you end up computing something probabilistic that may or may not be useful.

The lesson: "how slow" is the fundamental knob, and it maps cleanly onto classical-complexity refinements.

The QAOA connection

Farhi, Goldstone, and Gutmann's QAOA can be seen as "adiabatic evolution with a learned Trotter schedule." The p \to \infty limit of QAOA is exactly AQC with the schedule s(t) parametrised by the learned (\gamma_k, \beta_k) parameters. For finite p, QAOA is a small-slice Trotter discretisation of AQC — with the crucial twist that the slice durations are optimised by a classical outer loop, potentially doing better than a naive linear adiabatic schedule. The Aharonov–van Dam equivalence, through the Trotter-decomposition direction, tells you that p must generically scale polynomially with problem size to maintain adiabatic fidelity; the sub-polynomial "low-p QAOA" that NISQ experiments actually run is a gamble on whether the low-depth heuristic beats the asymptotic requirement on specific problem families.

Where this leads next

• Adiabatic Quantum Computing — the full physical model that the equivalence theorem is about.
• Quantum Annealing — the restricted, stoquastic hardware-specific version that D-Wave implements.
• QAOA Algorithm — finite-depth Trotterised adiabatic evolution, runnable on NISQ hardware.
• Local Hamiltonians — the structural class of Hamiltonians used on both sides of the equivalence.
• QMA and the Quantum Cook-Levin Theorem — the complexity-theoretic sibling, also proved by Kitaev's history-state construction.

References

1. Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev, Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation (2004, published 2007), SIAM J. Comp. — arXiv:quant-ph/0405098.
2. Roberto Oliveira and Barbara Terhal, The complexity of quantum spin systems on a two-dimensional square lattice (2008) — arXiv:quant-ph/0504050.
3. Alexei Kitaev, Alexander Shen, Mikhail Vyalyi, Classical and Quantum Computation (2002), AMS Graduate Studies in Mathematics vol. 47 — AMS landing page.
4. Julia Kempe, Alexei Kitaev, Oded Regev, The Complexity of the Local Hamiltonian Problem (2006), SIAM J. Comp. — arXiv:quant-ph/0406180.
5. Tameem Albash and Daniel A. Lidar, Adiabatic Quantum Computation (2018), Rev. Mod. Phys. — arXiv:1611.04471.
6. Wikipedia, Adiabatic quantum computation.