Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.00161

The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete

Nelson, Jon, Daniel Gottesman

Published Aug 29, 2025• 0 citations
arXivHTMLPDF

Abstract

In this work, we study a variant of the local Hamiltonian problem where we restrict to Hamiltonians that live on a lattice and are invariant under translations and rotations of the lattice. In the one-dimensional case this problem is known to be QMA$_{\rm EXP}$-complete. On the other hand, if we fix the lattice length then in the high-dimensional limit the ground state becomes unentangled due to arguments from mean-field theory. We take steps towards understanding this complexity spectrum by studying a problem that is intermediate between these two extremes. Namely, we consider the regime where the lattice dimension is arbitrary but fixed and the lattice length is scaled. We prove that this rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete answering an open question of [Gottesman, Irani 2013]. This characterizes a broad parameter range in which these rotation-invariant Hamiltonians have high computational complexity.

DOI
10.48550/arxiv.2509.00161

Related papers

The Rotation-Invariant Hamiltonian Problem Is QMA_EXP-Complete

Nelson, Jon, Gottesman, Daniel

In this work we study a variant of the local Hamiltonian problem where we restrict to Hamiltonians that live on a lattice and are invariant under translations and rotations of the lattice. In the one-dimensional case this problem is known to be QMA_EXP-complete. On the other hand, if we fix the lattice length then in the high-dimensional limit the ground state becomes unentangled due to arguments from mean-field theory. We take steps towards understanding this complexity spectrum by studying a problem that is intermediate between these two extremes. Namely, we consider the regime where the lattice dimension is arbitrary but fixed and the lattice length is scaled. We prove that this rotation-invariant Hamiltonian problem is QMA_EXP-complete answering an open question of [Gottesman and Irani, 2013]. This characterizes a broad parameter range in which these rotation-invariant Hamiltonians have high computational complexity.

Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems

Alastair Kay

Here we present a problem related to the local Hamiltonian problem (identifying whether the ground-state energy falls within one of two ranges) which is restricted to being translationally invariant. We prove that for Hamiltonians with a fixed local dimension and $O\mathbf{(}\mathrm{log}(N)\mathbf{)}$-body local terms, or local dimension $N$ and two-body terms, there are instances where finding the ground-state energy is quantum-Merlin-Arthur-complete and simulating the dynamics is BQP-complete (BQP denotes ``bounded error, quantum polynomial time''). We discuss the implications for the computational complexity of finding ground states of these systems and hence for any classical approximation techniques that one could apply including density-matrix renormalization group, matrix product states, and multiscale entanglement renormalization ansatz. One important example is a one-dimensional lattice of bosons with nearest-neighbor hopping at constant filling fraction---i.e., a generalization of the Bose-Hubbard model.

arXiv:0704.3142•Physical Review A•Sep 20, 2007•21 citations

Complexity of geometrically local stoquastic Hamiltonians

Asad Raza, Jens Eisert, Alex B. Grilo

The QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity that studies the computational complexity of problems in quantum many-body physics. Since its proposal, substantial effort has been invested in better understanding the problem for physically motivated important families of Hamiltonians. In particular, the QMA-completeness of approximating the ground state energy of local Hamiltonians has been extended to the case where the Hamiltonians are geometrically local in one and two spatial dimensions. Among those physically motivated Hamiltonians, stoquastic Hamiltonians play a particularly crucial role, as they constitute the manifestly sign-free Hamiltonians in Monte Carlo approaches. Interestingly, for such Hamiltonians, the problem at hand becomes more ''classical'', being hard for the class MA (the randomized version of NP) and its complexity has tight connections with derandomization. In this work, we prove that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension. Moreover, we show that related problems are StoqMA-complete.

arXiv:2407.15499•Quantum•Feb 11, 2026•0 citations

The complexity of translationally invariant low-dimensional spin lattices in 3D

Johannes Bausch, Stephen Piddock

In this theoretical paper, we consider spin systems in three spatial dimensions and consider the computational complexity of estimating the ground state energy, known as the local Hamiltonian problem, for translationally invariant Hamiltonians. We prove that the local Hamiltonian problem for 3D lattices with face-centered cubic unit cells and 4-local translationally invariant interactions between spin-3/2 particles and open boundary conditions is QMAEXP-complete, where QMAEXP is the class of problems which can be verified in exponential time on a quantum computer. We go beyond a mere embedding of past hard 1D history state constructions, for which the local spin dimension is enormous: even state-of-the-art constructions have local dimension 42. We avoid such a large local dimension by combining some different techniques in a novel way. For the verifier circuit which we embed into the ground space of the local Hamiltonian, we utilize a recently developed computational model, called a quantum ring machine, which is especially well suited for translationally invariant history state constructions. This is encoded with a new and particularly simple universal gate set, which consists of a single 2-qubit gate applied only to nearest-neighbour qubits. The Hamiltonian construction involves a classical Wang tiling problem as a binary counter which translates one cube side length into a binary description for the encoded verifier input and a carefully engineered history state construction that implements the ring machine on the cubic lattice faces. These novel techniques allow us to significantly lower the local spin dimension, surpassing the best translationally invariant result to date by two orders of magnitude (in the number of degrees of freedom per coupling). This brings our models on par with the best non-translationally invariant construction.

arXiv:1702.08830•Journal of Mathematical Physics•Nov 1, 2017•13 citations

The Complexity of Translationally Invariant Problems Beyond Ground State Energies

James D. Watson, Johannes Bausch, Sevag Gharibian

It is known that three fundamental questions regarding local Hamiltonians -- approximating the ground state energy (the Local Hamiltonian problem), simulating local measurements on the ground space (APX-SIM), and deciding if the low energy space has an energy barrier (GSCON) -- are $\mathsf{QMA}$-hard, $\mathsf{P}^{\mathsf{QMA}[log]}$-hard and $\mathsf{QCMA}$-hard, respectively, meaning they are likely intractable even on a quantum computer. Yet while hardness for the Local Hamiltonian problem is known to hold even for translationally-invariant systems, it is not yet known whether APX-SIM and GSCON remain hard in such "simple" systems. In this work, we show that the translationally invariant versions of both APX-SIM and GSCON remain intractable, namely are $\mathsf{P}^{\mathsf{QMA}_{\mathsf{EXP}}}$- and $\mathsf{QCMA}_{\mathsf{EXP}}$-complete, respectively. Each of these results is attained by giving a respective generic "lifting theorem" for producing hardness results. For APX-SIM, for example, we give a framework for "lifting" any abstract local circuit-to-Hamiltonian mapping $H$ (satisfying mild assumptions) to hardness of APX-SIM on the family of Hamiltonians produced by $H$, while preserving the structural and geometric properties of $H$ (e.g. translation invariance, geometry, locality, etc). Each result also leverages counterintuitive properties of our constructions: for APX-SIM, we "compress" the answers to polynomially many parallel queries to a QMA oracle into a single qubit. For GSCON, we give a hardness construction robust against highly non-local unitaries, i.e. even if the adversary acts on all but one qudit in the system in each step.

arXiv:2012.12717•Leibniz international proceedings in informatics•Dec 23, 2020•8 citations

2D Local Hamiltonian with Area Laws Is QMA-Complete

Yichen Huang

We show that the 2D local Hamiltonian problem with the constraint that the ground state obeys area laws is QMA-complete. We also prove similar results in 2D translation- invariant systems and for the 3D Heisenberg and Hubbard models with local magnetic fields. Consequently, unless MA = QMA, not all ground states of 2D local Hamiltonians with area laws have efficient classical representations that support efficient computation of local expectation values. In the future, even if area laws are proved for ground states of 2D gapped systems, the computational complexity of these systems remains unclear.

arXiv:1411.6614•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•6 citations
The rotation-invariant Hamiltonian problem is QMAEXP_{\rm EXP}EXP​-complete
In this work, we study a variant of the local Hamiltonian problem where we restrict to Hamiltonians that live on a lattice and are invariant under translations and rotations of the lattice. In the one-dimensional case this problem is known to be QMAEXP_{\rm EXP}EXP​-complete. On the other hand, if we fix the lattice length then in the high-dimensional limit the ground state becomes unentangled due to arguments from mean-field theory. We take steps towards understanding this complexity spectrum by studying a problem that is intermediate between these two extremes. Namely, we consider the regime where the lattice dimension is arbitrary but fixed and the lattice length is scaled. We prove that this rotation-invariant Hamiltonian problem is QMAEXP_{\rm EXP}EXP​-complete answering an open question of [Gottesman, Irani 2013]. This characterizes a broad parameter range in which these rotation-invariant Hamiltonians have high computational complexity.
In this work we study a variant of the local Hamiltonian problem where we restrict to Hamiltonians that live on a lattice and are invariant under translations and rotations of the lattice. In the one-dimensional case this problem is known to be QMA_EXP-complete. On the other hand, if we fix the lattice length then in the high-dimensional limit the ground state becomes unentangled due to arguments from mean-field theory. We take steps towards understanding this complexity spectrum by studying a problem that is intermediate between these two extremes. Namely, we consider the regime where the lattice dimension is arbitrary but fixed and the lattice length is scaled. We prove that this rotation-invariant Hamiltonian problem is QMA_EXP-complete answering an open question of [Gottesman and Irani, 2013]. This characterizes a broad parameter range in which these rotation-invariant Hamiltonians have high computational complexity.
Here we present a problem related to the local Hamiltonian problem (identifying whether the ground-state energy falls within one of two ranges) which is restricted to being translationally invariant. We prove that for Hamiltonians with a fixed local dimension and O(log(N))O\mathbf{(}\mathrm{log}(N)\mathbf{)}O(log(N))-body local terms, or local dimension NNN and two-body terms, there are instances where finding the ground-state energy is quantum-Merlin-Arthur-complete and simulating the dynamics is BQP-complete (BQP denotes ``bounded error, quantum polynomial time''). We discuss the implications for the computational complexity of finding ground states of these systems and hence for any classical approximation techniques that one could apply including density-matrix renormalization group, matrix product states, and multiscale entanglement renormalization ansatz. One important example is a one-dimensional lattice of bosons with nearest-neighbor hopping at constant filling fraction---i.e., a generalization of the Bose-Hubbard model.
The QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity that studies the computational complexity of problems in quantum many-body physics. Since its proposal, substantial effort has been invested in better understanding the problem for physically motivated important families of Hamiltonians. In particular, the QMA-completeness of approximating the ground state energy of local Hamiltonians has been extended to the case where the Hamiltonians are geometrically local in one and two spatial dimensions. Among those physically motivated Hamiltonians, stoquastic Hamiltonians play a particularly crucial role, as they constitute the manifestly sign-free Hamiltonians in Monte Carlo approaches. Interestingly, for such Hamiltonians, the problem at hand becomes more ''classical'', being hard for the class MA (the randomized version of NP) and its complexity has tight connections with derandomization. In this work, we prove that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension. Moreover, we show that related problems are StoqMA-complete.
In this theoretical paper, we consider spin systems in three spatial dimensions and consider the computational complexity of estimating the ground state energy, known as the local Hamiltonian problem, for translationally invariant Hamiltonians. We prove that the local Hamiltonian problem for 3D lattices with face-centered cubic unit cells and 4-local translationally invariant interactions between spin-3/2 particles and open boundary conditions is QMAEXP-complete, where QMAEXP is the class of problems which can be verified in exponential time on a quantum computer. We go beyond a mere embedding of past hard 1D history state constructions, for which the local spin dimension is enormous: even state-of-the-art constructions have local dimension 42. We avoid such a large local dimension by combining some different techniques in a novel way. For the verifier circuit which we embed into the ground space of the local Hamiltonian, we utilize a recently developed computational model, called a quantum ring machine, which is especially well suited for translationally invariant history state constructions. This is encoded with a new and particularly simple universal gate set, which consists of a single 2-qubit gate applied only to nearest-neighbour qubits. The Hamiltonian construction involves a classical Wang tiling problem as a binary counter which translates one cube side length into a binary description for the encoded verifier input and a carefully engineered history state construction that implements the ring machine on the cubic lattice faces. These novel techniques allow us to significantly lower the local spin dimension, surpassing the best translationally invariant result to date by two orders of magnitude (in the number of degrees of freedom per coupling). This brings our models on par with the best non-translationally invariant construction.
It is known that three fundamental questions regarding local Hamiltonians -- approximating the ground state energy (the Local Hamiltonian problem), simulating local measurements on the ground space (APX-SIM), and deciding if the low energy space has an energy barrier (GSCON) -- are QMA\mathsf{QMA}QMA-hard, PQMA[log]\mathsf{P}^{\mathsf{QMA}[log]}PQMA[log]-hard and QCMA\mathsf{QCMA}QCMA-hard, respectively, meaning they are likely intractable even on a quantum computer. Yet while hardness for the Local Hamiltonian problem is known to hold even for translationally-invariant systems, it is not yet known whether APX-SIM and GSCON remain hard in such "simple" systems. In this work, we show that the translationally invariant versions of both APX-SIM and GSCON remain intractable, namely are PQMAEXP\mathsf{P}^{\mathsf{QMA}_{\mathsf{EXP}}}PQMAEXP​- and QCMAEXP\mathsf{QCMA}_{\mathsf{EXP}}QCMAEXP​-complete, respectively. Each of these results is attained by giving a respective generic "lifting theorem" for producing hardness results. For APX-SIM, for example, we give a framework for "lifting" any abstract local circuit-to-Hamiltonian mapping HHH (satisfying mild assumptions) to hardness of APX-SIM on the family of Hamiltonians produced by HHH, while preserving the structural and geometric properties of HHH (e.g. translation invariance, geometry, locality, etc). Each result also leverages counterintuitive properties of our constructions: for APX-SIM, we "compress" the answers to polynomially many parallel queries to a QMA oracle into a single qubit. For GSCON, we give a hardness construction robust against highly non-local unitaries, i.e. even if the adversary acts on all but one qudit in the system in each step.
We show that the 2D local Hamiltonian problem with the constraint that the ground state obeys area laws is QMA-complete. We also prove similar results in 2D translation- invariant systems and for the 3D Heisenberg and Hubbard models with local magnetic fields. Consequently, unless MA = QMA, not all ground states of 2D local Hamiltonians with area laws have efficient classical representations that support efficient computation of local expectation values. In the future, even if area laws are proved for ground states of 2D gapped systems, the computational complexity of these systems remains unclear.