Computational Power of Constant-Gap Adiabatic Quantum Computation in More Than One Dimension

Hastings (2009) proved that adiabatic evolution of a one-dimensional, nearest-neighbor quantum system with a unique ground state and a spectral gap bounded below by a constant, started from a known product state, can be simulated efficiently on a classical computer, so such evolution cannot be a route to universal quantum computation. The paper explicitly leaves open what happens in two or more spatial dimensions, where no general area law is known and where, as Hastings put it, it is 'quite conceivable' that constant-gap adiabatic simulation with a unique ground state is computationally universal. Since then, the one-dimensional algorithmic sub-questions have been largely resolved (polynomial-time algorithms for gapped 1D ground states), and there is partial progress on both horns of the higher-dimensional question — an area law for frustration-free 2D systems (Anshu–Arad–Gosset) on the simulability side, and the criticality of all history-state Hamiltonian constructions (González-Guillén–Cubitt) on the universality side — but the computational power of constant-gap adiabatic computation in two or more dimensions remains undetermined in either direction.

Background

In adiabatic quantum computation (AQC), one encodes the answer to a computational problem in the ground state of a local Hamiltonian $H(s)=\sum_i h_i(s)$, where $s$ is slowly swept from $0$ to $s_{\max}$ along a path of Hamiltonians; $H(0)$ has a known, simple ground state (typically a product state, i.e. a tensor of single-site states with no entanglement), and $H(s_{\max})$ has a ground state from which the answer is read via expectation values of observables acting on a constant number of sites. The spectral gap $\Delta E$ is the energy difference between the ground state and the first excited state; the quantum adiabatic theorem guarantees the evolution stays near the instantaneous ground state when the evolution time scales polynomially in $1/\Delta E$, so a constant (system-size-independent) gap is the desirable regime for both run time and passive protection against excitations. Aharonov, van Dam, Kempe, Landau, Lloyd and Regev (2004) showed AQC with inverse-polynomial gaps is polynomially equivalent to the standard circuit model (i.e., universal for BQP, the class of problems solvable by quantum computers with bounded error), and topological schemes can be universal with a constant gap but only by exploiting a degenerate ground-state space, which the present question excludes.

Hastings (2009) proved a no-go result in one dimension: for a nearest-neighbor chain of $N$ sites with constant local Hilbert space dimension, bounded interaction strength $J$, unique ground state, and $J/\Delta E=O(1)$ along the whole path, starting from a known product state, expectation values of local observables in the final ground state can be approximated to accuracy $\epsilon$ in classical time polynomial in $N$ and $1/\epsilon$. The proof combines the area law for gapped one-dimensional systems — the bound that the entanglement entropy (von Neumann entropy of the reduced state of any subchain) of the ground state is bounded by a constant depending only on $J/\Delta E$ — with the fact that such states are well approximated by matrix product states (MPS), i.e. states built from contracted chains of low-dimensional site tensors with bond dimension $k$; the algorithm constructs a sequence of MPS approximations along the adiabatic path. Hence, in 1D, constant-gap adiabatic evolution with a unique ground state is classically simulable and 'not useful' for universal quantum computation; universal 1D adiabatic constructions, such as the 9-state-particle construction of Aharonov, Gottesman, Irani and Kempe (2007), necessarily have gaps shrinking as an inverse polynomial. In the same paper's discussion, Hastings asks what happens above one dimension. Two facts frame the question. First, no general area law is proven for gapped systems in two or more dimensions (in contrast to 1D, where Hastings 2007 and later refinements by Arad, Kitaev, Landau and Vazirani 2013 give a full proof); the strongest partial result, by Anshu, Arad and Gosset (2022), covers only frustration-free 2D systems (systems whose ground state minimizes every interaction term simultaneously). Second, even a full area law would not by itself yield efficient classical simulation: Huang (2014) proved that the two-dimensional local Hamiltonian problem — deciding whether the ground-state energy of a geometrically local Hamiltonian lies below one threshold or above another, the quantum analogue of MAX-k-SAT, complete for the class QMA (quantum Merlin–Arthur, the quantum generalization of NP) — remains QMA-complete even when restricted to ground states obeying area laws, and Schuch, Cirac and Verstraete (2008) showed that finding the optimal MPS is NP-hard for systems with inverse-polynomial gaps. On the other side of the question, the standard route to encoding computation in a ground state — the Feynman–Kitaev history-state (clock) construction — was shown by González-Guillén and Cubitt (2018) to necessarily produce critical (gapless) Hamiltonians: any circuit-to-Hamiltonian mapping with low-energy history states yields a gap closing at least as fast as $O(1/n)$. Mizel (2010) proposed a two-dimensional 'fixed-gap' ground-state computer with a size-independent gap, but the gap bound is argued heuristically (Hellman–Feynman estimates and small simulations) and holds only with a nonzero error probability per gate; it is a plausibility argument for Hastings' 'quite conceivable' scenario, not a rigorous construction. Related complexity evidence — the proven NLTS theorem (Anshu, Breuckmann, Nirkhe 2023: there exist Hamiltonians all of whose low-energy states require deep circuits, built from quantum LDPC codes that are not geometrically 2D-local) and the open quantum PCP conjecture (the conjecture that the local Hamiltonian problem remains QMA-hard even when the promised energy gap is a constant) — indicates that constant-gap local Hamiltonian problems may be computationally hard, but nothing is settled for geometrically 2D lattices along an adiabatic path from a product state. A review by Albash and Lidar (2018) presents the 1D constant-gap no-go and the dimension/gap trade-off as the standing state of the art.

Problem Statement

Determine the computational power of adiabatic quantum computation with a constant spectral gap in two or more spatial dimensions, under the conditions of Hastings' one-dimensional no-go theorem: Hamiltonian paths $H(s)=\sum_i h_i(s)$ of nearest-neighbor, geometrically local interactions on a lattice of two or more dimensions, with constant local Hilbert space dimension and bounded interaction strength, a unique ground state throughout the path, a spectral gap $\Delta E$ bounded below by a constant independent of system size, an initial Hamiltonian $H(0)$ with a known product ground state, and an output read from expectation values of observables supported on a constant number of sites of the final ground state. Specifically: either (a) prove that such adiabatic evolution is always classically simulable in polynomial time — i.e., extend Hastings' theorem by showing that expectation values of local observables in the final ground state can be approximated to inverse-polynomial accuracy by a classical polynomial-time algorithm, which would require structural control of general gapped 2D ground states going beyond the currently proven frustration-free area law and an algorithmic technique that does not follow from entanglement bounds alone; or (b) construct a rigorous family of such constant-gap, unique-ground-state Hamiltonian paths in two or more dimensions whose adiabatic evolution implements universal quantum computation (BQP-completeness), overcoming the proven criticality of all history-state circuit-to-Hamiltonian constructions; or (c) otherwise characterize this power (e.g., by an impossibility result or a complexity-theoretic collapse consequence in either direction).

References

1. M. 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, https://doi.org/10.1103/PhysRevLett.103.050502; arXiv:0902.2960, https://arxiv.org/abs/0902.2960
2. D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, O. Regev, 'Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation' (2004). arXiv:quant-ph/0405098, https://arxiv.org/abs/quant-ph/0405098
3. D. Aharonov, D. Gottesman, S. Irani, J. Kempe, 'The Power of Quantum Systems on a Line', Communications in Mathematical Physics (2009). DOI: 10.1007/s00220-008-0710-3; arXiv:0705.4077, https://arxiv.org/abs/0705.4077
4. N. Schuch, J. I. Cirac, F. Verstraete, 'Computational Difficulty of Finding Matrix Product Ground States', Physical Review Letters 100, 250501 (2008). DOI: 10.1103/PhysRevLett.100.250501, https://doi.org/10.1103/PhysRevLett.100.250501
5. I. Arad, A. Kitaev, Z. Landau, U. Vazirani, 'An area law and sub-exponential algorithm for 1D systems' (2013). arXiv:1301.1162, https://arxiv.org/abs/1301.1162
6. Z. Landau, U. Vazirani, T. Vidick, 'A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians' (2013). arXiv:1307.5143, https://arxiv.org/abs/1307.5143
7. Y. Huang, 'A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians' (2014). arXiv:1406.6355, https://arxiv.org/abs/1406.6355
8. A. Mizel, 'On fixed-gap adiabatic quantum computation' (2010; v2 title: 'Fixed-gap ground-state quantum computation and quantum concurrent processing'). arXiv:1002.0846, https://arxiv.org/abs/1002.0846
9. Y. Huang, 'Two-dimensional local Hamiltonian problem with area laws is QMA-complete', Journal of Computational Physics 443, 110534 (2021; first posted as arXiv:1411.6614, 2014). DOI: 10.1016/j.jcp.2021.110534, https://doi.org/10.1016/j.jcp.2021.110534; arXiv:1411.6614, https://arxiv.org/abs/1411.6614
10. A. Anshu, I. Arad, D. Gosset, 'Entanglement subvolume law for 2D frustration-free spin systems', Communications in Mathematical Physics (2022). DOI: 10.1007/s00220-022-04381-2; arXiv:1905.11337, https://arxiv.org/abs/1905.11337
11. A. Anshu, I. Arad, D. Gosset, 'An area law for 2D frustration-free spin systems' (STOC 2022). DOI: 10.1145/3519935.3519962; arXiv:2103.02492, https://arxiv.org/abs/2103.02492
12. A. Anshu, A. W. Harrow, M. Soleimanifar, 'Entanglement spread area law in gapped ground states', Nature Physics 18, 1362-1366 (2022; preprint posted as 'From communication complexity to an entanglement spread area law in the ground state of gapped local Hamiltonians'). DOI: 10.1038/s41567-022-01740-7, https://doi.org/10.1038/s41567-022-01740-7; arXiv:2004.15009, https://arxiv.org/abs/2004.15009
13. C. E. González-Guillén, T. S. Cubitt, 'History-state Hamiltonians are critical' (2018). arXiv:1810.06528, https://arxiv.org/abs/1810.06528
14. A. Anshu, N. P. Breuckmann, C. Nirkhe, 'NLTS Hamiltonians from good quantum codes', Proceedings of STOC 2023. DOI: 10.1145/3564246.3585114; arXiv:2206.13228, https://arxiv.org/abs/2206.13228
15. T. Albash, D. A. Lidar, 'Adiabatic Quantum Computing', Reviews of Modern Physics 90, 015002 (2018). DOI: 10.1103/RevModPhys.90.015002, https://doi.org/10.1103/RevModPhys.90.015002; arXiv:1611.04471, https://arxiv.org/abs/1611.04471