The rotation-invariant Hamiltonian problem is QMA EXP \text{QMA}_{\text{EXP}} -complete
Jon Nelson, Daniel Gottesman · 2025
Read The rotation-invariant Hamiltonian problem is QMA EXP \text{QMA}_{\text{EXP}} -complete by Jon Nelson, Daniel Gottesman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00161.txt.
Introduction
Jon Nelson and Daniel Gottesman settle the complexity of the rotation-invariant Hamiltonian problem in 2025. The local Hamiltonian problem asks for the lowest energy state of a system built from local terms, a core question in quantum computing theory. Here the terms sit on a lattice and stay the same under shifts and rotations of that lattice.
The one-dimensional case was known to be complete for a class called QMA_EXP, which captures very hard quantum checks. Nelson and Gottesman prove the same completeness when lattice dimension is fixed but length scales. Their result answers an open question from 2013 by Gottesman and Irani. It maps a broad range where such symmetric systems stay computationally hard.
Catalog record
| CREATOR | Jon Nelson, Daniel Gottesman |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-00161
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The rotation-invariant Hamiltonian problem is QMA EXP \text{QMA}_{\text{EXP}} -complete Jon Nelson, Daniel Gottesman 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 EXP \text{QMA}_{\text{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 \text{QMA}_{\text{EXP}} -complete answering an open question of [ GI13 ] . This characterizes a broad parameter range in which these rotation-invariant Hamiltonians have high computational complexity. 1 Introduction In order to understand the behavior of a quantum many-body system, it is crucial to study its Hamiltonian. The Hamiltonian operator not only governs the system’s dynamics through the Schrödinger equation but also encodes its low-energy states and energy spectrum. It is thus important to understand which Hamiltonians are tractable to analyze. In this work, we study the computational complexity of estimating the ground-state energy of a Hamiltonian with only short-range interactions, which is known as the local Hamiltonian problem. Often the goal is to show that a specific variant of this problem is QMA-complete, which implies that for certain Hamiltonians not even a quantum computer can be expected to find its ground state energy. On the one hand, this is a negative result for being able to calculate ground state energies. On the other hand, these results lead to constructions of highly complex quantum systems that are interesting objects of study in their own right. Kitaev initiated the study of local Hamiltonian problems in his landmark result proving that this problem in its most general form is QMA-complete [ KSV02 ] . However, Kitaev’s result only applies for a worst-case family of Hamiltonians, which are not physically natural. In order to study the complexity of more physically relevant cases, subsequent work has extended Kitaev’s result to apply under additional constraints that capture what it means to be “natural”. This has included restricting the local dimension of each particle as well as constraining the geometry of the interactions. For example, [ OT05 ] extends Kitaev’s result to qubits on a 2D lattice while [ AGIK09 ] further restricts to particles on a line with constant local dimension. Additional follow-up work has also emphasized symmetry constraints. This is motivated by the observation that many systems in nature are highly symmetric. For instance, the laws of gravity, electromagnetism, etc., do not change depending on where you are or how you are oriented; thus, these laws are translation and rotation-invariant. For translation-invariant one-dimensional spin chains, [ GI13 ] showed that this local Hamiltonian problem is \text{QMA}_{\text{EXP}} -complete. Although much work is now known about the complexity of translation-invariant systems [ GI13 , BP17 , BCW21 , KC19 , PB20 ] , there have been very few results for the rotation-invariant case. In fact, it was posed as an open question of [ GI13 ] whether their results can be extended to rotation-invariant Hamiltonians in higher dimensions. In this work, we solve this question and hope similar techniques can be used to lift other translation-invariant results to the rotation-invariant case. Translation invariance with reflection symmetry and rotation invariance coincide in 1D and so the main challenge is to extend [ GI13 ] to Hamiltonians on higher dimensional lattices. It is trivial to extend their result to higher dimensional translation-invariant lattices simply by ignoring all but one dimension. However, this breaks the rotation symmetry, which requires that the Hamiltonian terms act identically in all directions. In this case, the key challenge is to handle the increasingly high degree of interaction without increasing the number of parameters in the Hamiltonian. This presents issues, for example, when attempting to encode computation into the Hamiltonian’s ground state, which is an essential step for proving hardness. Controlling this computation requires the ability to track time, which can be accomplished in the 1D setting by moving a clock pointer along the spin chain [ GI13 ] . However, this same idea cannot be used in higher dimensions since the paths can branch in many directions throughout the lattice. In order to pick out a specific time direction, we must engineer a family of Hamiltonians that spontaneously breaks the rotation symmetry. Technical difficulties aside, it may seem intuitive that increasing the lattice dimension only makes the local Hamiltonian problem more difficult, and so one might assume that the complexity for higher dimensional cases follows from the one-dimensional case. However, due to the rotation symmetry, the increase in lattice dimension does not correspond to more Hamiltonian parameters, and so it is unclear how the complexity actually compares. In fact, standard condensed matter arguments imply that increasing the dimension can instead make the problem easier. This follows from the observation that for higher-dimensional lattices, mean-field theory (which uses a product-state ansatz to approximate the ground state) becomes more and more accurate [ RNB94 ] . In the quantum setting, this can be explained by an effect called monogamy of entanglement [ Ter04 ] , which states that a particle cannot be highly entangled with many other particles. Thus, for high lattice dimension, each particle has many neighbors and so on average they must be nearly unentangled. Due to this effect, the product state becomes a good approximation of the ground state, suggesting that this problem could now be more tractable than the lower dimensional cases. This has been formalized in [ BH13 ] which shows that for lattice dimension r there is a product state that approximates the ground-state energy by an average error of O(r^{-1/3}) per term of the Hamiltonian. Furthermore, [ KLC13 ] rigorously show that in the limit as r\rightarrow\infty the ground state is exactly a product state when the Hamiltonian is translation and rotation invariant. These results suggest that if the lattice dimension is high enough, the problem loses its quantum hardness since the low-energy states become unentangled. Another result that captures this phenomenon is [ AE13 ] , who show that a commuting version of the local Hamiltonian problem becomes easier as the interaction graphs become more expanding, which intuitively corresponds to more interaction. In this work, we consider a lattice dimension that is in an intermediate regime between one-dimensional spin chains, which are hard and spin chains with r\rightarrow\infty , which are easy. In particular, we consider an arbitrary but fixed lattice dimension and show that this rotation-invariant Hamiltonian problem is quantumly hard as you scale the lattice length. 1.1 Results We informally describe the rotation-invariant Hamiltonian problem as follows. Definition 1 (Rotation-invariant Hamiltonian problem (Informal)) . Consider the Hamiltonian where a single two-body term is applied to each neighboring pair of qudits on an r -dimensional lattice of side length n . Is the ground-state energy below a or greater than b ? Our