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:2004.02850

Solving degenerate 2D frustration-free spin systems in sub-exponential time

Nilin Abrahamsen

Published Apr 6, 2020• 0 citations
arXivHTMLPDF

Abstract

We give an improved analysis of approximate ground space projectors (AGSPs) to obtain a sharp error reduction bound in the setting a degenerate ground space. The improved tools imply that the recently proven 2D area law directly extends to sub-exponentially degenerate ground spaces and also yields a sub-exponential-time classical algorithm to compute the ground states. This time complexity cannot be improved beyond sub-exponential, even for the special case of classical unfrustrated systems in 2D.

DOI
10.48550/arxiv.2004.02850

Related papers

Sub-exponential algorithm for 2D frustration-free spin systems with gapped subsystems

Nilin Abrahamsen

We show that in the setting of the subvolume law of [Anshu, Arad, Gosset '19] for 2D locally gapped frustration-free spin systems there exists a randomized classical algorithm which computes the ground states in sub-exponential time. The running time cannot be improved to polynomial unless SAT can be solved in randomized polynomial time, as even the special case of classical constraint satisfaction problems on the 2D grid is known to be NP-hard.

•Apr 6, 2020•1 citation

Sharp implications of AGSPs for degenerate ground spaces

Nilin Abrahamsen

We generalize the `off-the-rack' AGSP$\Rightarrow$entanglement bound implication of [Arad, Landau, and Vazirani '12] from unique ground states to degenerate ground spaces. Our condition $RΔ\le1/2$ on a $(Δ,R)$-AGSP matches the non-degenerate case, whereas existing tools in the literature of spin chains would only be adequate to prove a less natural implication which assumes $R^{\text{Const}}Δ\le c$. To show that $RΔ\le1/2$ still suffices in the degenerate case we prove an optimal error reduction bound which improves on the literature by a factor $δμ$ where $δ=1-μ$ is the viability. The generalized off-the-rack bound implies the generalization of a recent 2D subvolume law of [Anshu, Arad, and Gosset '19] from the non-degenerate case to the sub-exponentially degenerate case.

arXiv:2003.08406•Mar 18, 2020•3 citations

An area law for 2d frustration-free spin systems

Anurag Anshu, Itai Arad, David Gosset

We prove that the entanglement entropy of the ground state of a locally gapped frustration-free 2D lattice spin system satisfies an area law with respect to a vertical bipartition of the lattice into left and right regions. We first establish that the ground state projector of any locally gapped frustration-free 1D spin system can be approximated to within error є by a degree O(√nlog(є−1)) multivariate polynomial in the interaction terms of the Hamiltonian. This generalizes the optimal bound on the approximate degree of the boolean AND function, which corresponds to the special case of commuting Hamiltonian terms. For 2D spin systems we then construct an approximate ground state projector (AGSP) that employs the optimal 1D approximation in the vicinity of the boundary of the bipartition of interest. This AGSP has sufficiently low entanglement and error to establish the area law using a known technique.

arXiv:2103.02492•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2022•40 citations

Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time

Christopher T. Chubb, Steven T. Flammia

Given a gapped Hamiltonian of a spin chain, we give a polynomial-time algorithm for finding the degenerate ground space projector.The output is an orthonormal set of matrix product states that approximate the true ground space projector up to an inverse polynomial error in any Schatten norm, with a runtime exponential in the degeneracy.Our algorithm is an extension of the recent algorithm of Landau, Vazirani, and Vidick [17] for the nondegenerate case, and it includes the recent improvements due to Huang [13].The main new idea is to incorporate the local distinguishability of ground states on the half-chain to ensure that the algorithm returns a complete set of global ground states.

arXiv:1502.06967•Chicago Journal of Theoretical Computer Science•Jan 1, 2016•20 citations

Entanglement subvolume law for 2d frustration-free spin systems

Anurag Anshu, Itai Arad, David Gosset

Let H be a frustration-free Hamiltonian describing a 2D grid of qudits with local interactions, a unique ground state, and local spectral gap lower bounded by a positive constant. For any bipartition defined by a vertical cut of length L running from top to bottom of the grid, we prove that the corresponding entanglement entropy of the ground state of H is upper bounded by Õ(L 5/3). For the special case of a 1D chain, our result provides a new area law which improves upon prior work, in terms of the scaling with qudit dimension and spectral gap. In addition, for any bipartition of the grid into a rectangular region A and its complement, we show that the entanglement entropy is upper bounded as Õ(|∂ A|5/3) where ∂ A is the boundary of A. This represents a subvolume bound on entanglement in frustration-free 2D systems. In contrast with previous work, our bounds depend on the local (rather than global) spectral gap of the Hamiltonian. We prove our results using a known method which bounds the entanglement entropy of the ground state in terms of certain properties of an approximate ground state projector (AGSP). To this end, we construct a new AGSP which is based on a robust polynomial approximation of the AND function and we show that it achieves an improved trade-off between approximation error and entanglement.

ACM Symposium on Theory of Computing (STOC)•Jun 7, 2020•14 citations

An Area Law for the Maximally-Mixed Ground State in Arbitrarily Degenerate Systems with Good AGSP

Itai Arad, Raz Firanko, Rahul Jain

We show an area law in the mutual information for the maximally-mixed state Ω in the ground space of general Hamiltonians, which is independent of the underlying ground space degeneracy. Our result assumes the existence of a ‘good’ approximation to the ground state projector (a good AGSP), a crucial ingredient in former area-law proofs. Such approximations have been explicitly derived for 1D gapped local Hamiltonians and 2D frustration-free locally-gapped local Hamiltonians. As a corollary, we show that in 1D gapped local Hamiltonians, for any є>0 and any bi-partition L∪ Lc of the system,

ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•2 citations
We give an improved analysis of approximate ground space projectors (AGSPs) to obtain a sharp error reduction bound in the setting a degenerate ground space. The improved tools imply that the recently proven 2D area law directly extends to sub-exponentially degenerate ground spaces and also yields a sub-exponential-time classical algorithm to compute the ground states. This time complexity cannot be improved beyond sub-exponential, even for the special case of classical unfrustrated systems in 2D.
We generalize the `off-the-rack' AGSP⇒\Rightarrow⇒entanglement bound implication of [Arad, Landau, and Vazirani '12] from unique ground states to degenerate ground spaces. Our condition RΔ≤1/2RΔ\le1/2RΔ≤1/2 on a (Δ,R)(Δ,R)(Δ,R)-AGSP matches the non-degenerate case, whereas existing tools in the literature of spin chains would only be adequate to prove a less natural implication which assumes RConstΔ≤cR^{\text{Const}}Δ\le cRConstΔ≤c. To show that RΔ≤1/2RΔ\le1/2RΔ≤1/2 still suffices in the degenerate case we prove an optimal error reduction bound which improves on the literature by a factor δμδμδμ where δ=1−μδ=1-μδ=1−μ is the viability. The generalized off-the-rack bound implies the generalization of a recent 2D subvolume law of [Anshu, Arad, and Gosset '19] from the non-degenerate case to the sub-exponentially degenerate case.
We prove that the entanglement entropy of the ground state of a locally gapped frustration-free 2D lattice spin system satisfies an area law with respect to a vertical bipartition of the lattice into left and right regions. We first establish that the ground state projector of any locally gapped frustration-free 1D spin system can be approximated to within error є by a degree O(√nlog(є−1)) multivariate polynomial in the interaction terms of the Hamiltonian. This generalizes the optimal bound on the approximate degree of the boolean AND function, which corresponds to the special case of commuting Hamiltonian terms. For 2D spin systems we then construct an approximate ground state projector (AGSP) that employs the optimal 1D approximation in the vicinity of the boundary of the bipartition of interest. This AGSP has sufficiently low entanglement and error to establish the area law using a known technique.
Given a gapped Hamiltonian of a spin chain, we give a polynomial-time algorithm for finding the degenerate ground space projector.The output is an orthonormal set of matrix product states that approximate the true ground space projector up to an inverse polynomial error in any Schatten norm, with a runtime exponential in the degeneracy.Our algorithm is an extension of the recent algorithm of Landau, Vazirani, and Vidick [17] for the nondegenerate case, and it includes the recent improvements due to Huang [13].The main new idea is to incorporate the local distinguishability of ground states on the half-chain to ensure that the algorithm returns a complete set of global ground states.
Let H be a frustration-free Hamiltonian describing a 2D grid of qudits with local interactions, a unique ground state, and local spectral gap lower bounded by a positive constant. For any bipartition defined by a vertical cut of length L running from top to bottom of the grid, we prove that the corresponding entanglement entropy of the ground state of H is upper bounded by Õ(L 5/3). For the special case of a 1D chain, our result provides a new area law which improves upon prior work, in terms of the scaling with qudit dimension and spectral gap. In addition, for any bipartition of the grid into a rectangular region A and its complement, we show that the entanglement entropy is upper bounded as Õ(|∂ A|5/3) where ∂ A is the boundary of A. This represents a subvolume bound on entanglement in frustration-free 2D systems. In contrast with previous work, our bounds depend on the local (rather than global) spectral gap of the Hamiltonian. We prove our results using a known method which bounds the entanglement entropy of the ground state in terms of certain properties of an approximate ground state projector (AGSP). To this end, we construct a new AGSP which is based on a robust polynomial approximation of the AND function and we show that it achieves an improved trade-off between approximation error and entanglement.
We show an area law in the mutual information for the maximally-mixed state Ω in the ground space of general Hamiltonians, which is independent of the underlying ground space degeneracy. Our result assumes the existence of a ‘good’ approximation to the ground state projector (a good AGSP), a crucial ingredient in former area-law proofs. Such approximations have been explicitly derived for 1D gapped local Hamiltonians and 2D frustration-free locally-gapped local Hamiltonians. As a corollary, we show that in 1D gapped local Hamiltonians, for any є>0 and any bi-partition L∪ Lc of the system,