Optimal spectral gap and minimal local dimension for universal adiabatic quantum computation: the surviving open core of the Aharonov–van Dam–Kempe–Landau–Lloyd–Regev open questions

The proof that adiabatic quantum computation (AQC) is polynomially equivalent to circuit-based quantum computation left open how weak the physical requirements on the Hamiltonians of a universal adiabatic computer can be. Two coupled pieces of that question remain unresolved. First, every known universal adiabatic construction has a minimum spectral gap that shrinks inverse-polynomially with system size; Hastings (2009) proved that in one dimension a constant gap is useless (such evolution is efficiently classically simulable) and explicitly left open whether universal adiabatic computation with a constant, system-size-independent spectral gap is possible in two or more dimensions. Second, the smallest local Hilbert-space dimension permitting universal nearest-neighbor adiabatic computation on a one-dimensional line is unknown: the best construction uses 9-state particles. Resolving either — a constant-gap universal construction in two or more dimensions, an impossibility proof for such constructions, or a determination of the minimal local dimension on the line — would materially change Hamiltonian complexity and the physical resource requirements for adiabatic quantum computing.

Background

Adiabatic quantum computation (AQC) replaces the discrete gate sequence of the circuit model by a slowly varying Hamiltonian $H(s)$ , $s\in[0,1]$ : one prepares the ground state of an initial Hamiltonian $H(0)$ with a simple tensor-product ground state, slowly deforms the system to a final Hamiltonian $H(1)$ , and reads the output from the final (near-)ground state. The adiabatic theorem guarantees that if the deformation is slow enough relative to the spectral gap $\Delta(H(s))$ — the energy difference between the ground state and the first excited state along the path — the system stays near the instantaneous ground state; the required runtime scales at least as the inverse square of the smallest gap along the path. A Hamiltonian is $k$ -local if it is a sum of terms each acting nontrivially on at most $k$ particles, and geometrically local if those particles are neighbors on a lattice. Aharonov, van Dam, Kempe, Landau, Lloyd, and Regev (SIAM Review 2008; arXiv:quant-ph/0405098) proved that AQC with local Hamiltonians efficiently simulates any quantum circuit, so the two models are polynomially equivalent. Their construction uses the Feynman–Kitaev history-state method: the ground state of a specially designed local Hamiltonian is a superposition over all time steps of the simulated circuit (a 'history state'), which links AQC to the local Hamiltonian problem — deciding whether the ground energy of a local Hamiltonian lies below $a$ or above $b$ — which is complete for QMA, the quantum analogue of NP (with ground-energy QMA-completeness established for 5-local and then 2-local Hamiltonians by Kempe, Kitaev, and Regev). All history-state constructions, however, have a minimum gap along the adiabatic path that shrinks only inverse-polynomially in the computation length (the original 2D-grid construction achieves $\Delta\ge 1/L^{3}$ for a length- $L$ computation). In their open-questions section the authors asked how far the physical resources can be reduced: lower local dimension (from six-state particles toward two or three), one instead of two spatial dimensions, fault tolerance, and whether the adiabatic viewpoint can yield new algorithms. Subsequent work resolved much of this. Kempe–Kitaev–Regev (2006) showed 2-local qubit Hamiltonians suffice (via perturbative gadgets, which build effective many-body interactions from two-body ones), and Oliveira–Terhal (2008) achieved universality with qubits on a two-dimensional square lattice with nearest-neighbor interactions. Aharonov, Gottesman, Irani, and Kempe (2009) reduced the spatial dimension to one: universal AQC on a line of 9-state particles with nearest-neighbor interactions (and, with 12-state particles, QMA-completeness of the 1D ground-energy problem, improved to 8-state particles by Hallgren, Nagaj, and Narayanaswami in 2013). On the gap side, the 1D case is closed: Hastings (2009) proved that one-dimensional constant-gap adiabatic evolution from a product state is efficiently classically simulable — the proof combines the area law (ground states of gapped 1D local Hamiltonians have entanglement bounded by a constant across any cut) with matrix product states, i.e., wavefunctions parametrized by a chain of small bond-dimension tensors that can be updated as the Hamiltonian changes — so constant gap in 1D cannot be computationally useful, and any universal 1D construction must have a vanishing gap. Hastings explicitly left open the computational power of constant-gap adiabatic evolution in more than one dimension. This is adjacent to the quantum PCP conjecture (Aharonov, Arad, Vidick 2013), which predicts that approximating the ground energy of local Hamiltonians to constant accuracy remains QMA-hard; a central proposed route is gap amplification, following the pattern of Dinur's proof of the classical PCP theorem (the result that every NP proof can be recast so that reading only a constant number of randomly chosen locations suffices to check it with high confidence). Somma and Boixo (2013) showed that a Hamiltonian's spectral gap can be amplified (quadratically) only for frustration-free Hamiltonians — those whose ground state minimizes every term simultaneously — and only by evolving a mid-spectrum eigenstate rather than the ground state, i.e., outside strict AQC. The NLTS ('no low-energy trivial states') theorem, proved by Anshu, Breuckmann, and Nirkhe (2022) using good quantum error-correcting codes, established a necessary condition for the quantum PCP conjecture, which remains open (Natarajan–Nirkhe 2024; Bergamaschi, Metger, Vidick, and Zhang 2025). On fault tolerance, the direction posed in 2004 has a positive theoretical resolution in standard noise models: Jordan, Farhi, and Shor (2006) constructed error-correcting codes for AQC, and Lidar (2008) proved a threshold-type result protecting AQC against decoherence and certain control errors using dynamical decoupling (averaging out noise by rapidly modulated control fields) combined with stabilizer/subsystem codes and two-body interactions.

Problem Statement

Determine how far the physical requirements for computationally universal adiabatic quantum computation can be weakened, in the two respects left open after the resolution of the geometry question. A universal adiabatic construction here means a uniform family $H_n(s)=(1-s)H_{\mathrm{init}}+sH_{\mathrm{final}}$ , $s\in[0,1]$ , of Hamiltonians on a lattice of $n$ particles with nearest-neighbor (geometrically local) terms, bounded local Hilbert-space dimension, and bounded-norm local terms, such that adiabatic evolution from the ground state of $H_{\mathrm{init}}$ (an efficiently preparable product state) prepares, in polynomial time, a state from which the output of any polynomial-size quantum circuit can be extracted. All known constructions have minimum gap $\Delta_{\min}=\min_{s\in[0,1]}\Delta(H_n(s))$ scaling inverse-polynomially in $n$ . The open targets are: (1) the optimal spectral-gap scaling — exhibit a universal adiabatic construction in two or more spatial dimensions with $\Delta_{\min}\ge c$ for a constant $c>0$ independent of $n$ , or prove that every universal adiabatic construction in this class requires $\Delta_{\min}\to 0$ ; Hastings (2009) resolved the one-dimensional case negatively (constant-gap 1D adiabatic evolution is efficiently classically simulable and hence not universal), explicitly leaving the two-or-more-dimensional case open; and (2) the minimal local dimension — determine the smallest local Hilbert-space dimension $d$ for universal nearest-neighbor adiabatic computation on a one-dimensional line, where the best known construction uses $d=9$ (Aharonov–Gottesman–Irani–Kempe 2009; the related 1D local-Hamiltonian ground-energy QMA-completeness is known at $d=8$ ). Determining the smallest $d$ requires bracketing it — a construction of such a universal 1D adiabatic family at some local dimension $d$ together with a matching lower bound proving that no smaller $d$ admits one. A construction at a smaller $d$ (e.g., $d=3$ ) and a lower bound $d\ge d_0$ for some $d_0>2$ are each partial progress toward this, not a resolution; note that the only known obstruction to $d=2$ is the constant-gap case — Hastings's simulation result rules out universality for every fixed local dimension with constant gap in 1D — so whether qubits with vanishing gap suffice on a line is itself part of the question. The problem concerns both respects: each of the two targets is a well-posed open question in its own right, and resolving either one on its own completes the task; the two together instantiate one common, optional objective — characterize the trade-off among spectral gap, spatial dimension, and local dimension under which adiabatic evolution retains full computational power — and any answer must pin down the model class (locality, dimension, norm bounds, noiseless evolution) within which the claim is proved.

References

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev, 'Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation', SIAM Review 50(4), 755–787 (2008), DOI: 10.1137/080734479; arXiv:quant-ph/0405098, https://arxiv.org/abs/quant-ph/0405098
Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe, 'The Power of Quantum Systems on a Line', Communications in Mathematical Physics 287(1), 41–65 (2009), DOI: 10.1007/s00220-008-0710-3; arXiv:0705.4077, https://arxiv.org/abs/0705.4077
Julia Kempe, Alexei Kitaev, Oded Regev, 'The Complexity of the Local Hamiltonian Problem', SIAM Journal on Computing 35(5), 1070–1097 (2006), DOI: 10.1137/S0097539704445226
Rolando D. Oliveira, Barbara M. Terhal, 'The complexity of quantum spin systems on a two-dimensional square lattice', Quantum Information and Computation 8(10), 900–924 (2008), DOI: 10.26421/qic8.10-2
Stephen P. Jordan, Edward Farhi, Peter W. Shor, 'Error-correcting codes for adiabatic quantum computation', Physical Review A 74, 052322 (2006), DOI: 10.1103/PhysRevA.74.052322
Daniel A. Lidar, 'Towards Fault Tolerant Adiabatic Quantum Computation', Physical Review Letters 100, 160506 (2008), DOI: 10.1103/PhysRevLett.100.160506
Matthew B. Hastings, 'Quantum Adiabatic Computation with a Constant Gap Is Not Useful in One Dimension', Physical Review Letters 103, 050502 (2009), DOI: 10.1103/PhysRevLett.103.050502; arXiv:0902.2960, https://arxiv.org/abs/0902.2960
Roberto D. Somma, Sergio Boixo, 'Spectral Gap Amplification', SIAM Journal on Computing 42(2), 593–610 (2013), DOI: 10.1137/120871997; arXiv:1110.2494, https://arxiv.org/abs/1110.2494
Tameem Albash, Daniel A. Lidar, 'Adiabatic Quantum Computing', Reviews of Modern Physics 90, 015002 (2018), DOI: 10.1103/RevModPhys.90.015002; arXiv:1611.04471, https://arxiv.org/abs/1611.04471
Sean Hallgren, Daniel Nagaj, Sandeep Narayanaswami, 'The local Hamiltonian problem on a line with eight staes is QMA-complete', Quantum Information and Computation 13(9–10), 721–750 (2013), DOI: 10.26421/qic13.9-10-1
Dorit Aharonov, Itai Arad, Thomas Vidick, 'Guest column: The Quantum PCP Conjecture', ACM SIGACT News 44(2), 47–79 (2013), DOI: 10.1145/2491533.2491549; arXiv:1309.7495, https://arxiv.org/abs/1309.7495
Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe, 'NLTS Hamiltonians from good quantum codes', arXiv:2206.13228 (2022), https://arxiv.org/abs/2206.13228; STOC 2023, DOI: 10.1145/3564246.3585114
Anand Natarajan, Chinmay Nirkhe, 'The status of the quantum PCP conjecture (games version)', arXiv:2403.13084 (2024), https://arxiv.org/abs/2403.13084
Thiago Bergamaschi, Tony Metger, Thomas Vidick, Tina Zhang, 'Derandomised tensor product gap amplification for quantum Hamiltonians', arXiv:2510.01333 (2025), https://arxiv.org/abs/2510.01333
Andrew M. Childs, 'Universal Computation by Quantum Walk', Physical Review Letters 102, 180501 (2009), DOI: 10.1103/PhysRevLett.102.180501; arXiv:0806.1972, https://arxiv.org/abs/0806.1972