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:1201.3387 · Quantum Information and Computation

Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture

Matthew B. Hastings

Published May 1, 2013• 36 citations
arXivHTMLPDF

Abstract

We consider the entanglement properties of ground states of Hamiltonians which are sums of commuting projectors (we call these commuting projector Hamiltonians), in particular whether or not they have ``trivial" ground states, where a state is trivial if it is constructed by a local quantum circuit of bounded depth and range acting on a product state. It is known that Hamiltonians such as the toric code only have nontrivial ground states in two dimensions. Conversely, commuting projector Hamiltonians which are sums of two-body interactions have trivial ground states\cite{bv}. Using a coarse-graining procedure, this implies that any such Hamiltonian with bounded range interactions in one dimension has a trivial ground state. In this paper, we further explore the question of which Hamiltonians have trivial ground states. We define an ``interaction complex" for a Hamiltonian, which generalizes the notion of interaction graph and we show that if the interaction complex can be continuously mapped to a $1$-complex using a map with bounded diameter of pre-images then the Hamiltonian has a trivial ground state assuming one technical condition on the Hamiltonians holds (this condition holds for all stabilizer Hamiltonians, and we additionally prove the result for all Hamiltonians under one assumption on the $1$-complex). While this includes the cases considered by Ref.~\onlinecite{bv}, we show that it also includes a larger class of Hamiltonians whose interaction complexes cannot be coarse-grained into the case of Ref.~\onlinecite{bv} but still can be mapped continuously to a $1$-complex. One motivation for this study is an approach to the quantum PCP conjecture. We note that many commonly studied interaction complexes can be mapped to a $1$-complex after removing a small fraction of sites. For commuting projector Hamiltonians on such complexes, in order to find low energy trivial states for the original Hamiltonian, it would suffice to find trivial ground states for the Hamiltonian with those sites removed. Such trivial states can act as a classical witness to the existence of a low energy state. While this result applies for commuting Hamiltonians and does not necessarily apply to other Hamiltonians, it suggests that to prove a quantum PCP conjecture for commuting Hamiltonians, it is worth investigating interaction complexes which cannot be mapped to $1$-complexes after removing a small fraction of points. We define this more precisely below; in some sense this generalizes the notion of an expander graph. Surprisingly, such complexes do exist as will be shown elsewhere\cite{fh}, and have useful properties in quantum coding theory.

DOI
10.26421/qic13.5-6-3

Related papers

Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians

Anurag Anshu, Chinmay Nirkhe

The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings, 2014 -- which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques, based on entropic and local indistinguishability arguments, that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate or nearly linear-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy o(n). Such codes are known to exist and are not necessarily locally testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.

arXiv:2011.02044•Leibniz international proceedings in informatics•Nov 3, 2020•6 citations

On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems

Dorit Aharonov, Lior Eldar

The local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory. Understanding the complexity of the intermediate case in which the constraints are quantum but all local terms in the Hamiltonian commute, is of importance for conceptual, physical and computational complexity reasons. Bravyi and Vyalyi showed in 2003 [10], using a clever application of the representation theory of C*-algebras, that if the terms in the Hamiltonian are all two-local, the problem is in NP, and the entanglement in the ground states is local. The general case remained open since then. In this paper we extend this result beyond the two-local case, to the case of three-qubit interactions. We then extend our results even further, and show that NP verification is possible for three-wise interaction between qutrits as well, as long as the interaction graph is planar and also "nearly Euclidean" in some well-defined sense. The proofs imply that in all such systems, the entanglement in the ground states is local. These extensions imply an intriguing sharp transition phenomenon in commuting Hamiltonian systems: the ground spaces of 3-local "physical" systems based on qubits and qutrits are diagonalizable by a basis whose entanglement is highly local, while even slightly more involved interactions (the particle dimensionality or the locality of the interaction is larger) already exhibit an important long-range entanglement property called Topological Order. Our results thus imply that Kitaev's celebrated Toric code construction is, in a well defined sense, optimal as a construction of Topological Order based on commuting Hamiltonians.

arXiv:1102.0770•Annual Symposium on Foundations of Computer Science•Oct 1, 2011•56 citations

Circuit lower bounds for quantum code Hamiltonians and an almost linear NLTS theorem

Anurag Anshu, Chinmay Nirkhe

The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation, 2014) -- which posits the existence of a local Hamiltonian with a super-constant circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this paper, we provide new techniques, based on entropic and local indistinguishability arguments, for proving circuit lower bounds for the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate and polynomial-distance LDPC stabilizer codes, we prove a super-constant circuit lower bounds for the complexity of all states of energy o(n) (which can be viewed as an almost linear NLTS theorem). Such codes are known to exist and, in general, are not locally-testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a constant-dimensional lattice, showing that complex entanglement at high energies can persist in physically relevant systems.

•Nov 3, 2020•0 citations

NLTM Hamiltonians from gauged sheaf quantum locally testable codes

Fuchuan Wei, Zhengyi Han, Zimu Li +1 more

Understanding the complexity of low-energy quantum states is a central problem in quantum complexity theory and many-body physics. Here we prove the no low-energy trivial magic (NLTM) conjecture, constructing a family of local Hamiltonians for which every state within a positive energy density window requires circuit depth $Ω(\log n)$ to prepare from arbitrary stabilizer state that may themselves be highly entangled. Notably, our result is intrinsic in the sense that the same Hamiltonian family and energy density threshold apply to arbitrary qudit stabilizer inputs with any bounded local dimensions. Our construction builds on non-Abelian gauged sheaf codes obtained using the cup product structure on good quantum locally testable codes. We establish constant operator soundness for the associated Hamiltonians, enabling their protected logical structure to constrain all states at sufficiently low energy density. By excluding shallow stabilizer-based classical witnesses, Our result substantially strengthens NLTS and advances our understanding of low-energy complexity relevant to quantum PCP.

quant-pharXiv:2609.40220•Oct 1, 2026•0 citations

Local Hamiltonians Whose Ground States Are Hard to Approximate

Lior Eldar, Aram W. Harrow

Ground states of local Hamiltonians can be generally highly entangled: any quantum circuit that generates them, even approximately, must be sufficiently deep to allow coupling (entanglement) between any pair of qubits. Until now this property was not known to be “robust” - the marginals of such states to a subset of the qubits containing all but a small constant fraction of them may be only locally entangled, and hence approximable by shallow quantum circuits. In this work we construct a family of 16-local Hamiltonians for which any marginal of a ground state to a fraction at least 1-10-8of the qubits must be globally entangled. This provides evidence that quantum entanglement is not very fragile, and perhaps our intuition about its instability is an artifact of considering local Hamiltonians which are not only local but spatially local. Formally, it provides positive evidence for two wide-open conjectures in condensed-matter physics and quantum complexity theory which are the qLDPC conjecture, positing the existence of “good” quantum LDPC codes, and the NLTS conjecture [1] positing the existence of local Hamiltonians in which any low-energy state is highly entangled. Our Hamiltonian is based on applying the hypergraph product by Tillich-Zemor [2] to the repetition code with checks from an expander graph. A key tool in our proof is a new lower bound on the vertex expansion of the output of low-depth quantum circuits, which may be of independent interest.

arXiv:1510.02082•Annual Symposium on Foundations of Computer Science•Oct 1, 2017•57 citations

Matrix product operators and central elements: classical description of a quantum state

Matthew B. Hastings

We study planar two-dimensional quantum systems on a lattice whose Hamiltonian is a sum of local commuting projectors of bounded range. We consider whether or not such a system has a zero energy ground state. To do this, we consider the problem as a one-dimensional problem, grouping all sites along a column into "supersites"; using $C^*$-algebraic methods (Bravyi and Vyalyi), we can solve this problem if we can characterize the central elements of the interaction algebra on these supersite. Unfortunately, these central elements may be very complex, making brute force impractical. Instead, we show a characterization of these elements in terms of matrix product operators with bounded bond dimension. This bound can be interpreted as a bound on the number of particle types in lattice theories with bounded Hilbert space dimension on each site. Topological order in this approach is related to the existence of certain central elements which cannot be "broken" into smaller pieces without creating an end excitation. Using this bound on bond dimension, we prove that several special cases of this problem are in NP, and we give part of a proof that the general case is in NP. Further, we characterize central elements that appear in certain specific models, including toric code and Levin-Wen models, as either product operators in the Abelian case or matrix product operators with low bond dimension in the non-Abelian case; this matrix product operator representation may have practical application in engineering the complicated multi-spin interactions in the Levin-Wen models.

arXiv:1207.1671•Geometry and topology monographs•Oct 14, 2012•12 citations
We consider the entanglement properties of ground states of Hamiltonians which are sums of commuting projectors (we call these commuting projector Hamiltonians), in particular whether or not they have trivial" ground states, where a state is trivial if it is constructed by a local quantum circuit of bounded depth and range acting on a product state. It is known that Hamiltonians such as the toric code only have nontrivial ground states in two dimensions. Conversely, commuting projector Hamiltonians which are sums of two-body interactions have trivial ground states\cite{bv}. Using a coarse-graining procedure, this implies that any such Hamiltonian with bounded range interactions in one dimension has a trivial ground state. In this paper, we further explore the question of which Hamiltonians have trivial ground states. We define an interaction complex" for a Hamiltonian, which generalizes the notion of interaction graph and we show that if the interaction complex can be continuously mapped to a 111-complex using a map with bounded diameter of pre-images then the Hamiltonian has a trivial ground state assuming one technical condition on the Hamiltonians holds (this condition holds for all stabilizer Hamiltonians, and we additionally prove the result for all Hamiltonians under one assumption on the 111-complex). While this includes the cases considered by Ref.\onlinecite{bv}, we show that it also includes a larger class of Hamiltonians whose interaction complexes cannot be coarse-grained into the case of Ref.\onlinecite{bv} but still can be mapped continuously to a 111-complex. One motivation for this study is an approach to the quantum PCP conjecture. We note that many commonly studied interaction complexes can be mapped to a 111-complex after removing a small fraction of sites. For commuting projector Hamiltonians on such complexes, in order to find low energy trivial states for the original Hamiltonian, it would suffice to find trivial ground states for the Hamiltonian with those sites removed. Such trivial states can act as a classical witness to the existence of a low energy state. While this result applies for commuting Hamiltonians and does not necessarily apply to other Hamiltonians, it suggests that to prove a quantum PCP conjecture for commuting Hamiltonians, it is worth investigating interaction complexes which cannot be mapped to 111-complexes after removing a small fraction of points. We define this more precisely below; in some sense this generalizes the notion of an expander graph. Surprisingly, such complexes do exist as will be shown elsewhere\cite{fh}, and have useful properties in quantum coding theory.
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings, 2014 -- which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques, based on entropic and local indistinguishability arguments, that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate or nearly linear-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy o(n). Such codes are known to exist and are not necessarily locally testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.
The local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory. Understanding the complexity of the intermediate case in which the constraints are quantum but all local terms in the Hamiltonian commute, is of importance for conceptual, physical and computational complexity reasons. Bravyi and Vyalyi showed in 2003 [10], using a clever application of the representation theory of C*-algebras, that if the terms in the Hamiltonian are all two-local, the problem is in NP, and the entanglement in the ground states is local. The general case remained open since then. In this paper we extend this result beyond the two-local case, to the case of three-qubit interactions. We then extend our results even further, and show that NP verification is possible for three-wise interaction between qutrits as well, as long as the interaction graph is planar and also "nearly Euclidean" in some well-defined sense. The proofs imply that in all such systems, the entanglement in the ground states is local. These extensions imply an intriguing sharp transition phenomenon in commuting Hamiltonian systems: the ground spaces of 3-local "physical" systems based on qubits and qutrits are diagonalizable by a basis whose entanglement is highly local, while even slightly more involved interactions (the particle dimensionality or the locality of the interaction is larger) already exhibit an important long-range entanglement property called Topological Order. Our results thus imply that Kitaev's celebrated Toric code construction is, in a well defined sense, optimal as a construction of Topological Order based on commuting Hamiltonians.
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation, 2014) -- which posits the existence of a local Hamiltonian with a super-constant circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this paper, we provide new techniques, based on entropic and local indistinguishability arguments, for proving circuit lower bounds for the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate and polynomial-distance LDPC stabilizer codes, we prove a super-constant circuit lower bounds for the complexity of all states of energy o(n) (which can be viewed as an almost linear NLTS theorem). Such codes are known to exist and, in general, are not locally-testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a constant-dimensional lattice, showing that complex entanglement at high energies can persist in physically relevant systems.
Understanding the complexity of low-energy quantum states is a central problem in quantum complexity theory and many-body physics. Here we prove the no low-energy trivial magic (NLTM) conjecture, constructing a family of local Hamiltonians for which every state within a positive energy density window requires circuit depth Ω(log⁡n)Ω(\log n)Ω(logn) to prepare from arbitrary stabilizer state that may themselves be highly entangled. Notably, our result is intrinsic in the sense that the same Hamiltonian family and energy density threshold apply to arbitrary qudit stabilizer inputs with any bounded local dimensions. Our construction builds on non-Abelian gauged sheaf codes obtained using the cup product structure on good quantum locally testable codes. We establish constant operator soundness for the associated Hamiltonians, enabling their protected logical structure to constrain all states at sufficiently low energy density. By excluding shallow stabilizer-based classical witnesses, Our result substantially strengthens NLTS and advances our understanding of low-energy complexity relevant to quantum PCP.
Ground states of local Hamiltonians can be generally highly entangled: any quantum circuit that generates them, even approximately, must be sufficiently deep to allow coupling (entanglement) between any pair of qubits. Until now this property was not known to be “robust” - the marginals of such states to a subset of the qubits containing all but a small constant fraction of them may be only locally entangled, and hence approximable by shallow quantum circuits. In this work we construct a family of 16-local Hamiltonians for which any marginal of a ground state to a fraction at least 1-10-8of the qubits must be globally entangled. This provides evidence that quantum entanglement is not very fragile, and perhaps our intuition about its instability is an artifact of considering local Hamiltonians which are not only local but spatially local. Formally, it provides positive evidence for two wide-open conjectures in condensed-matter physics and quantum complexity theory which are the qLDPC conjecture, positing the existence of “good” quantum LDPC codes, and the NLTS conjecture [1] positing the existence of local Hamiltonians in which any low-energy state is highly entangled. Our Hamiltonian is based on applying the hypergraph product by Tillich-Zemor [2] to the repetition code with checks from an expander graph. A key tool in our proof is a new lower bound on the vertex expansion of the output of low-depth quantum circuits, which may be of independent interest.
We study planar two-dimensional quantum systems on a lattice whose Hamiltonian is a sum of local commuting projectors of bounded range. We consider whether or not such a system has a zero energy ground state. To do this, we consider the problem as a one-dimensional problem, grouping all sites along a column into "supersites"; using C∗C^*C∗-algebraic methods (Bravyi and Vyalyi), we can solve this problem if we can characterize the central elements of the interaction algebra on these supersite. Unfortunately, these central elements may be very complex, making brute force impractical. Instead, we show a characterization of these elements in terms of matrix product operators with bounded bond dimension. This bound can be interpreted as a bound on the number of particle types in lattice theories with bounded Hilbert space dimension on each site. Topological order in this approach is related to the existence of certain central elements which cannot be "broken" into smaller pieces without creating an end excitation. Using this bound on bond dimension, we prove that several special cases of this problem are in NP, and we give part of a proof that the general case is in NP. Further, we characterize central elements that appear in certain specific models, including toric code and Levin-Wen models, as either product operators in the Abelian case or matrix product operators with low bond dimension in the non-Abelian case; this matrix product operator representation may have practical application in engineering the complicated multi-spin interactions in the Levin-Wen models.