Source-linked AI summary
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev
TL;DR
Whether adiabatic computation has the full power of standard quantum computation was unknown. The paper constructs efficient adiabatic simulations of quantum circuits and proves polynomial equivalence, including a two-dimensional nearest-neighbor construction. It also leaves open whether adiabatic optimization can be efficiently simulated classically.
Problem
Whether adiabatic computation can achieve the full power of quantum computation, or efficiently simulate general classical computations, was unknown.
Source: §1 · p. 2Method
The authors construct an adiabatic simulation of quantum circuits using local Hamiltonians and extend it to two-local nearest-neighbor interactions on a two-dimensional grid.
Source: §1.1 · p. 3, §1.2 · p. 4Results
The adiabatic and standard quantum computation models are polynomially equivalent, including with explicit sparse Hamiltonians.
Source: §1.1 · p. 3Takeaways & Limitations
Quantum computation can be studied and implemented within the adiabatic model without losing computational power.
Source: §1.1 · p. 3, §1.2 · p. 4Whether adiabatic optimization can be simulated efficiently by a classical Turing machine remains open.
Source: §1.6 · p. 6
Abstract
from arXiv · showhide
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models provides a new vantage point from which to tackle the central issues in quantum computation, namely designing new quantum algorithms and constructing fault tolerant quantum computers. In particular, by translating the main open questions in the area of quantum algorithms to the language of spectral gaps of sparse matrices, the result makes these questions accessible to a wider scientific audience, acquainted with mathematical physics, expander theory and rapidly mixing Markov chains.
1 Introduction
Adiabatic computation uses local Hamiltonians and a slowly changing path to encode a solution in a final ground state; its full computational power was unknown. The paper establishes equivalence with standard quantum computation and extends the simulation to a two-dimensional nearest-neighbor setting.
1 Introduction
- The minimal spectral gap along the Hamiltonian path governs runtime; an inverse-polynomial gap makes the computation polynomial time.The path interpolates linearly between Hinit and Hfinal, and the adiabatic theorem relates a sufficiently slow evolution to reaching the final ground state.Source: §1 · p. 2
1.1 Results – Computational Complexity of the Adiabatic Model
- The model is polynomially equivalent to standard quantum computation, and explicit sparse-Hamiltonian adiabatic computation is equivalent as well.The paper supplies the previously missing efficient simulation of standard quantum computation by adiabatic computation, using 3-local Hamiltonians.Source: §1.1 · p. 3
1.2 Results – Towards Experimental Implications
- Any quantum computation can be simulated with two-local nearest-neighbor Hamiltonians on six-state particles arranged on a two-dimensional grid.The construction’s need for six-state particles is an open question for improvement.Source: §1.2 · pp. 3–4
1.3 Proof of Theorem 1.1: Overview
- A circuit’s unknown final state need not be specified as the final ground state: a history state has non-negligible overlap with it and is locally verifiable using a unary clock.The Hamiltonians are constructed efficiently from the circuit without knowing its output state.Source: §1.3 · pp. 4–5
1.4 Proof of Theorem 1.3: Overview
- The grid construction gives each particle both clock and computational degrees of freedom, propagating the computation in a snake-like sequence across the lattice.The particles’ combined degrees of freedom make them six-state; the spectral-gap lower bound is obtained in essentially the same way as for the 3-local case.Source: §1.4 · p. 6
1.5 Related Work
- The spectral gap has a different role here than in topological and geometrical quantum computation: it determines adiabatic runtime, rather than only separating computational and noisy subspaces.The paper also notes that later work tightened quantum-NP-completeness results and used them to show Theorem 1.1 for 2-local Hamiltonians.Source: §1.5 · p. 6
1.6 Open Questions
- Open questions include improving runtime and particle dimensionality, using a one-dimensional grid, establishing fault tolerance, and characterizing adiabatic optimization, which may be classically simulable.The paper also leaves open whether adiabatic evolution helps physically implement quantum computers.Source: §1.6 · p. 6
2 Preliminaries
The preliminaries define local Hamiltonian evolution and gap-based adiabatic runtime, then connect Hamiltonian spectral gaps to Markov-chain gaps through conductance.
2.1 Hamiltonians of n-Particle Systems
- Hamiltonians govern continuous quantum evolution; the paper restricts to k-local interactions, each acting on a constant-size subset of particles.For constant k, these Hamiltonians can be described with polynomially many numbers.Source: §2.1 · p. 7
2.2 The Model of Adiabatic Computation
- The model interpolates linearly between Hamiltonians from an easy tensor-product ground state, with runtime accounting for evolution time and Hamiltonian norm.Efficiency follows when Hamiltonian norms are polynomially bounded and the path's spectral gap is at least inverse polynomial.Source: §2.2 · pp. 8–9
2.3 Markov Chains and Hermitian Matrices
- For G = I − H with positive ground-state amplitudes, the associated stochastic matrix has normalized squared amplitudes as its limiting distribution, and its gap rescales from Δ(H).The mapping requires a Hermitian matrix with non-negative entries and a positive largest-eigenvalue eigenvector.Source: §2.3 · p. 9
2.4 Spectral Gaps of Markov Chains
- Conductance compares probability flow leaving a set with its stationary weight, and the cited bound lower-bounds the eigenvalue gap by half its square.The conductance is the minimum flow-to-weight ratio over nonempty sets with stationary weight at most one-half.Source: §2.4 · pp. 9–10
3 Equivalence of Adiabatic and Quantum Computation
The section proves the equivalence theorem by simulating quantum circuits with adiabatic computation. Its construction uses n+L particles and reduces interaction size from five to three.
3 Equivalence of Adiabatic and Quantum Computation
- A circuit of L two-qubit gates on n qubits can be simulated by adiabatic computation on n+L qubits.The other direction of the equivalence had been shown in [14].Source: §3 · p. 10
- The construction first allows five-qubit interactions, then reduces them to three using techniques also used in Section 4.Source: §3 · p. 10
3.1 Five-local Hamiltonian
The section constructs a five-local adiabatic simulation of quantum circuits and analyzes its running time using spectral-gap, ground-energy, and ground-space-angle bounds, while identifying the limited properties of Hinput needed for the argument.
3.1 Five-local Hamiltonian
- A 5-local adiabatic computation simulates an n-qubit circuit with L two-qubit gates to trace distance ǫ in time O(ǫ−(5+3δ)L5+2δ), for fixed δ > 0.It uses n + L qubits, and its initial and final Hamiltonians are polynomial-time computable.Source: §3.1 · p. 10, §3.1.3 · p. 15
3.1.1 The Hamiltonian
- The construction uses penalty terms to enforce the desired initial state and legal clock states, while propagation terms ensure each clock step applies its circuit gate.The resulting initial and final Hamiltonians have the desired starting state and history state as zero-energy ground states.Source: §3.1.1 · pp. 10–11
3.1.2 Spectral Gap in a Subspace
- The history-state subspace S0 is invariant under H(s), and the restricted spectral gap satisfies ∆(HS0(s)) = Ω(L−2) throughout the evolution.The proof treats early evolution near the initial Hamiltonian and later evolution using a stochastic-walk conductance bound.Source: §3.1.2 · pp. 11, 12, 14
3.1.3 Running Time
- Appending O(ǫ−1L) identity gates increases the final circuit state’s weight in the history state, enabling a one-run adiabatic output close to that state without classical postselection.This resolves the model’s restriction to one adiabatic evolution followed by measurement and tracing out ancillas; the resulting overall running time is O(ǫ−(5+3δ)L5+2δ).Source: §3.1.3 · pp. 14–15
3.1.4 Spectral Gap
- Across the full Hilbert space, the spectral gap satisfies ∆(H(s)) = Ω(L−3) for all s.Illegal clock states have energy at least 1, while the legal-clock subspace has the same Ω(L−3) gap; the analysis decomposes it into invariant input-state blocks.Source: §3.1.4 · pp. 15–16
- The spectral gaps of HS0(s) and M are Ω(1/L^2) and 1, respectively, and the ground-space angle bound yields an Ω(1/L^3) ground-energy increase for HSj(s) over HS0(s).The angle bound is cos(θ) ≤ 1 − 1/L.Source: §3.1.4 · p. 17
- The argument only requires Hinput to vanish on S0 and to be diagonal on each Sj for j ≠ 0, with a top-left entry of at least 1 and all other entries non-negative.The passage notes that this observation will be useful in Section 4.Source: §3.1.4 · p. 17
3.2 Three-local Hamiltonian
The section constructs a 3-local adiabatic computation that simulates a quantum circuit, then bounds its spectral gap and shows its final ground state approximates the circuit’s history state.
3.2 Three-local Hamiltonian
- A 3-local adiabatic computation simulates an n-qubit circuit with L two-qubit gates in polynomial time, producing a state ǫ-close in trace distance to U|0n⟩.The theorem also states that Hinit and Hfinal can be computed by a polynomial-time Turing machine.Source: §3.2 · p. 17
3.2.1 The Hamiltonian
- The construction reduces the 5-local terms to 3-local terms by removing two clock qubits, then uses a large penalty on illegal clock states.The modified final Hamiltonian’s ground state is not exactly the history state, but is later shown to be close to it.Source: §3.2.1 · pp. 17–18
3.2.2 The Spectral Gap
- The modified Hamiltonian has spectral gap Ω(L^-3) throughout the interpolation, with the large clock penalty keeping its low spectrum close to the restriction to legal clock states.The proof compares against the restricted Hamiltonian’s Ω(1/L^3) gap and uses J = ǫ^-2L^6.Source: §3.2.2 · pp. 18–19
- The final ground state is ǫ-close to the history state, yielding an adiabatic simulation whose output is ǫ-close in trace distance to U|0n⟩.The running time is O(ǫ^-(16+4δ)L^(14+3δ)) for any fixed δ > 0.Source: §3.2.2 · pp. 19–20
4 Two Local Hamiltonians on a Two-Dimensional Lattice
This section constructs a two-dimensional nearest-neighbor adiabatic simulation of quantum circuits using particle phases as a geometric clock, with an inverse-cubic spectral gap. It also addresses the lattice Hilbert space’s failure to separate computation and clock qubits, using identity gates and a shape measurement to identify the circuit’s final state with high probability.
4 Two Local Hamiltonians on a Two-Dimensional Lattice
- A circuit with L two-qubit gates can be simulated by a 2-local adiabatic computation on 6-dimensional particles in a 2D nearest-neighbor grid, with poly(L, 1/ε) runtime and ε-close output.The Hamiltonians are polynomial-time computable, and the output is ε-close in trace distance to U|0^n⟩.Source: §4 · p. 20
4.1 Assumptions on the Input Circuit
- The input circuit is arranged in R rounds of n nearest-neighbor gates followed by n identity gates, with L = 2nR and only polynomial overhead.Any circuit can be transformed to this layout by adding identity and swap gates.Source: §4.1 · p. 21
4.2 The Particles of the Adiabatic Quantum System
- The system uses an n-row, (R + 1)-column lattice of 6-state particles, whose phases define shapes while two phases carry qubit degrees of freedom.The four phases are unborn, first, second, and dead.Source: §4.2 · p. 21
4.3 Geometrical Clock
- The clock is encoded by a sequence of legal particle shapes: each of the L + 1 clock positions spans a 2n-dimensional subspace, and shape changes trace a snake-like path through the lattice.Active particles encode the circuit state after the corresponding gates; within a round, the downward stage applies gates as particles change phase.Source: §4.3 · pp. 21–23
4.4 The Hamiltonian
- The Hamiltonians use J = ε^-2 L^6 to penalize illegal shapes, keeping the computation in the legal-shape space.The projected propagation terms check correct evolution between consecutive clock steps.Source: §4.4 · pp. 23–24
4.4.1 The Clock Hamiltonian
- A shape is legal exactly when it avoids the forbidden local configurations, enabling a 2-local nearest-neighbor clock Hamiltonian whose ground space is precisely the span of legal shapes.This space S has dimension (L + 1)2n.Source: §4.4.1 · p. 24
4.4.2 The Propagation Hamiltonian
- Consecutive legal shapes differ at at most two sites, where the relevant gate acts, so two-body nearest-neighbor terms can advance the clock and computational state together.The circuit layout ensures the gate-acting particles coincide with those whose phases change.Source: §4.4.2 · p. 25
4.5 Spectral Gap
- For all interpolation parameters, the spectral gap is Ω(L^-3), and the final ground state is ε-close to the target history state.The construction generates that history state in the same runtime as the three-local construction for the modified circuit.Source: §4.5 · p. 27
- After adding L/ε identity gates, measuring only the system’s shape yields ℓ≥L with probability at least 1−ε, leaving active particles in the circuit’s final state.The adiabatic computation first produces a state close to the history state; the shape measurement avoids measuring the inner computational degrees of freedom.Source: §4.5 · p. 27