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

ACM Symposium on Theory of Computing (STOC)

Entanglement subvolume law for 2d frustration-free spin systems

Anurag Anshu, Itai Arad, David Gosset

Published Jun 7, 2020• 14 citations
Publisher

Abstract

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.

DOI
10.1145/3357713.3384292

Related papers

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•64 citations

An area law and sub-exponential algorithm for 1D systems

Arad, Itai, Kitaev, Alexei, Landau, Zeph +1 more

We give a new proof for the area law for general 1D gapped systems, which exponentially improves Hastings' famous result \cite{ref:Has07}. Specifically, we show that for a chain of d-dimensional spins, governed by a 1D local Hamiltonian with a spectral gap \eps>0, the entanglement entropy of the ground state with respect to any cut in the chain is upper bounded by $O{\frac{\log^3 d}{\eps}}$. Our approach uses the framework Arad et al to construct a Chebyshev-based AGSP (Approximate Ground Space Projection) with favorable factors. However, our construction uses the Hamiltonian directly, instead of using the Detectability lemma, which allows us to work with general (frustrated) Hamiltonians, as well as slightly improving the $1/\eps$ dependence of the bound in Arad et al. To achieve that, we establish a new, "random-walk like", bound on the entanglement rank of an arbitrary power of a 1D Hamiltonian, which might be of independent interest: \ER{H^\ell} \le (\ell d)^{O(\sqrt{\ell})}. Finally, treating d as a constant, our AGSP shows that the ground state is well approximated by a matrix product state with a sublinear bond dimension $B=e^{O(\log^{3/4}n/\eps^{1/4})}. Using this in conjunction with known dynamical programing algorithms, yields an algorithm for a 1/\poly(n) approximation of the ground energy with a subexponential running time T\le \exp(e^{O(\log^{3/4}n/\eps^{1/4})}).

arXiv:1301.1162•Jan 7, 2013•215 citations

Entanglement versus gap for one-dimensional spin systems

Daniel Gottesman, M. B. Hastings

We study the relationship between entanglement and spectral gap for local Hamiltonians in one dimension (1D). The area law for a 1D system states that for the ground state, the entanglement of any interval is upper bounded by a constant independent of the size of the interval. However, the possible dependence of the upper bound on the spectral gap Δ is not known, as the best known general upper bound is asymptotically much larger than the largest possible entropy of any model system previously constructed for small Δ. To help resolve this asymptotic behavior, we construct a family of 1D local systems for which some intervals have entanglement entropy, which is polynomial in 1/Δ, whereas previously studied systems, such as free fermion systems or systems described by conformal field theory, had the entropy of all intervals bounded by a constant time log(1/Δ).

arXiv:0901.1108•New Journal of Physics•Feb 26, 2010•70 citations

Local gap threshold for frustration-free spin systems

David Gosset, Evgeny Mozgunov

We improve Knabe’s spectral gap bound for frustration-free translation-invariant local Hamiltonians in 1D. The bound is based on a relationship between global and local gaps. The global gap is the spectral gap of a size-m chain with periodic boundary conditions, while the local gap is that of a subchain of size n < m with open boundary conditions. Knabe proved that if the local gap is larger than the threshold value 1/(n − 1) for some n > 2, then the global gap is lower bounded by a positive constant in the thermodynamic limit m → ∞. Here we improve the threshold to 6n(n+1), which is better (smaller) for all n > 3 and which is asymptotically optimal. As a corollary we establish a surprising fact about 1D translation-invariant frustration-free systems that are gapless in the thermodynamic limit: for any such system the spectral gap of a size-n chain with open boundary conditions is upper bounded as O(n−2). This contrasts with gapless frustrated systems where the gap can be Θ(n−1). It also limits the extent to which the area law is violated in these frustration-free systems, since it implies that the half-chain entanglement entropy is O(1/ϵ) as a function of spectral gap ϵ. We extend our results to frustration-free systems on a 2D square lattice.

arXiv:1512.00088•Journal of Mathematical Physics•Sep 1, 2016•61 citations

Entanglement vs. gap for one-dimensional spin systems

Matthew B. Hastings, Dorit Aharonov, Daniel Gottesman

We study the relationship between entanglement and spectral gap for local Hamiltonians in one dimension. The area law for a one-dimensional system states that for the ground state, the entanglement of any interval is upper-bounded by a constant independent of the size of the interval. However, the possible dependence of the upper bound on the spectral gap {Delta} is not known, as the best known general upper bound is asymptotically much larger than the largest possible entropy of any model system previously constructed for small {Delta}. To help resolve this asymptotic behavior, we construct a family of one-dimensional local systems for which some intervals have entanglement entropy which is polynomial in 1/{Delta}, whereas previously studied systems had the entropy of all intervals bounded by a constant times log(1/{Delta}).

Journal of Mathematical Physics•Jan 1, 2008•1 citation

Ground state entanglement in one-dimensional translationally invariant quantum systems

Sandy Irani

We examine whether it is possible for one-dimensional translationally invariant Hamiltonians to have ground states with a high degree of entanglement. We present a family of translationally invariant Hamiltonians {Hn} for the infinite chain. The spectral gap of Hn is Ω(1/poly(n)). Moreover, for any state in the ground space of Hn and any m, there are regions of size m with entanglement entropy Ω(min{m,n}). A similar construction yields translationally invariant Hamiltonians for finite chains that have unique ground states exhibiting high entanglement. The area law proven by Hastings [“An area law for one dimensional quantum systems,” J. Stat. Mech.: Theory Exp. 2007 (08024)] gives a constant upper bound on the entanglement entropy for one-dimensional ground states that is independent of the size of the region but exponentially dependent on 1/Δ, where Δ is the spectral gap. This paper provides a lower bound, showing a family of Hamiltonians for which the entanglement entropy scales polynomially with 1/Δ. Previously, the best known such bound was logarithmic in 1/Δ.

arXiv:0901.1107•Journal of Mathematical Physics•Feb 1, 2010•45 citations
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 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.
We give a new proof for the area law for general 1D gapped systems, which exponentially improves Hastings' famous result \cite{ref:Has07}. Specifically, we show that for a chain of d-dimensional spins, governed by a 1D local Hamiltonian with a spectral gap \eps>0, the entanglement entropy of the ground state with respect to any cut in the chain is upper bounded by $O{\frac{\log^3 d}{\eps}}$. Our approach uses the framework Arad et al to construct a Chebyshev-based AGSP (Approximate Ground Space Projection) with favorable factors. However, our construction uses the Hamiltonian directly, instead of using the Detectability lemma, which allows us to work with general (frustrated) Hamiltonians, as well as slightly improving the $1/\eps$ dependence of the bound in Arad et al. To achieve that, we establish a new, "random-walk like", bound on the entanglement rank of an arbitrary power of a 1D Hamiltonian, which might be of independent interest: \ER{H^\ell} \le (\ell d)^{O(\sqrt{\ell})}. Finally, treating d as a constant, our AGSP shows that the ground state is well approximated by a matrix product state with a sublinear bond dimension $B=e^{O(\log^{3/4}n/\eps^{1/4})}. Using this in conjunction with known dynamical programing algorithms, yields an algorithm for a 1/\poly(n) approximation of the ground energy with a subexponential running time T\le \exp(e^{O(\log^{3/4}n/\eps^{1/4})}).
We study the relationship between entanglement and spectral gap for local Hamiltonians in one dimension (1D). The area law for a 1D system states that for the ground state, the entanglement of any interval is upper bounded by a constant independent of the size of the interval. However, the possible dependence of the upper bound on the spectral gap Δ is not known, as the best known general upper bound is asymptotically much larger than the largest possible entropy of any model system previously constructed for small Δ. To help resolve this asymptotic behavior, we construct a family of 1D local systems for which some intervals have entanglement entropy, which is polynomial in 1/Δ, whereas previously studied systems, such as free fermion systems or systems described by conformal field theory, had the entropy of all intervals bounded by a constant time log(1/Δ).
We improve Knabe’s spectral gap bound for frustration-free translation-invariant local Hamiltonians in 1D. The bound is based on a relationship between global and local gaps. The global gap is the spectral gap of a size-m chain with periodic boundary conditions, while the local gap is that of a subchain of size n < m with open boundary conditions. Knabe proved that if the local gap is larger than the threshold value 1/(n − 1) for some n > 2, then the global gap is lower bounded by a positive constant in the thermodynamic limit m → ∞. Here we improve the threshold to 6n(n+1), which is better (smaller) for all n > 3 and which is asymptotically optimal. As a corollary we establish a surprising fact about 1D translation-invariant frustration-free systems that are gapless in the thermodynamic limit: for any such system the spectral gap of a size-n chain with open boundary conditions is upper bounded as O(n−2). This contrasts with gapless frustrated systems where the gap can be Θ(n−1). It also limits the extent to which the area law is violated in these frustration-free systems, since it implies that the half-chain entanglement entropy is O(1/ϵ) as a function of spectral gap ϵ. We extend our results to frustration-free systems on a 2D square lattice.
We study the relationship between entanglement and spectral gap for local Hamiltonians in one dimension. The area law for a one-dimensional system states that for the ground state, the entanglement of any interval is upper-bounded by a constant independent of the size of the interval. However, the possible dependence of the upper bound on the spectral gap {Delta} is not known, as the best known general upper bound is asymptotically much larger than the largest possible entropy of any model system previously constructed for small {Delta}. To help resolve this asymptotic behavior, we construct a family of one-dimensional local systems for which some intervals have entanglement entropy which is polynomial in 1/{Delta}, whereas previously studied systems had the entropy of all intervals bounded by a constant times log(1/{Delta}).
We examine whether it is possible for one-dimensional translationally invariant Hamiltonians to have ground states with a high degree of entanglement. We present a family of translationally invariant Hamiltonians {Hn} for the infinite chain. The spectral gap of Hn is Ω(1/poly(n)). Moreover, for any state in the ground space of Hn and any m, there are regions of size m with entanglement entropy Ω(min{m,n}). A similar construction yields translationally invariant Hamiltonians for finite chains that have unique ground states exhibiting high entanglement. The area law proven by Hastings [“An area law for one dimensional quantum systems,” J. Stat. Mech.: Theory Exp. 2007 (08024)] gives a constant upper bound on the entanglement entropy for one-dimensional ground states that is independent of the size of the region but exponentially dependent on 1/Δ, where Δ is the spectral gap. This paper provides a lower bound, showing a family of Hamiltonians for which the entanglement entropy scales polynomially with 1/Δ. Previously, the best known such bound was logarithmic in 1/Δ.