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)

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

Itai Arad, Raz Firanko, Rahul Jain

Published Jun 10, 2024• 2 citations
Publisher

Abstract

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,

DOI
10.1145/3618260.3649612

Related papers

Area laws and tensor networks for maximally mixed ground states

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 previous area-law proofs. Such approximations have been explicitly derived for 1D gapped local Hamiltonians and 2D frustration-free locally-gapped Hamiltonians. As a corollary, we show that in 1D gapped local Hamiltonians, for any $\varepsilon>0$ and any bi-partition $L\cup L^c$ of the system, \begin{align*} \mathrm I_{\max}^\varepsilon (L:L^c)_Ω \le \mathrm O \big( \log (|L|\log(d))+\log(1/\varepsilon)\big), \end{align*} where $|L|$ represents the number of sites in $L$, $d$ is the dimension of a site and $ \mathrm I_{\max}^\varepsilon (L:L^c)_Ω $ represents the $\varepsilon$-\emph{smoothed maximum mutual information} with respect to the $L:L^c$ partition in $Ω$. From this bound we then conclude $\mathrm I (L:L^c)_Ω \le \mathrm O\big(\log(|L|\log(d))\big)$ -- an area law for the mutual information in 1D systems with a logarithmic correction. In addition, we show that $Ω$ can be approximated in trace norm up to $\varepsilon$ with a state of Schmidt rank of at most $\mathrm{poly}(|L|/\varepsilon)$, leading to a good MPO approximation for $Ω$ with polynomial bond dimension. Similar corollaries are derived for the mutual information of 2D frustration-free and locally-gapped local Hamiltonians.

arXiv:2310.19028•Oct 29, 2023•0 citations

Area Laws and Tensor Networks for Maximally Mixed Ground States

Itai Arad, Raz Firanko, Rahul Jain

We show an area law in the mutual information for the maximally-mixed state $$\Omega $$ 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 previous area-law proofs. Such approximations have been explicitly derived for 1D gapped local Hamiltonians and 2D frustration-free locally-gapped Hamiltonians. As a corollary, we show that in 1D gapped local Hamiltonians, for any $$\epsilon >0$$ and any bipartition $$L\cup L^c$$ of the system, $$\begin{aligned} \textrm{I}^\epsilon _{\max } \, \! \! \left( L : L^c \right) _{\Omega } \le {\textrm{O}}\left( \log (|L|\log (d))+\log (1/\epsilon )\right) , \end{aligned}$$ where |L| represents the number of sites in L, d is the dimension of a site and $$ \textrm{I}^\epsilon _{\max } \, \! \! \left( L : L^c \right) _{\Omega }$$ represents the $$\epsilon $$ -smoothed maximum mutual information with respect to the $$L:L^c$$ partition in $$\Omega $$ . From this bound we then conclude $$ \textrm{I} \, \! \! \left( L : L^c \right) _\Omega \le {\textrm{O}}\left( \log (|L|\log (d))\right) $$ – an area law for the mutual information in 1D systems with a logarithmic correction. In addition, we show that $$\Omega $$ can be approximated in trace norm up to $$\epsilon $$ with a state of Schmidt rank of at most $$\textrm{poly}(|L|\log (d)/\epsilon )$$ , leading to a good MPO approximation for $$\Omega $$ with polynomial bond dimension. Similar corollaries are derived for the mutual information of 2D frustration-free and locally-gapped local Hamiltonians.

Communications in Mathematical Physics•Feb 5, 2026•0 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

1D area law with ground-state degeneracy

Yichen Huang

An area law is proved for the Renyi entanglement entropy of possibly degenerate ground states in one-dimensional gapped quantum systems. Suppose in a chain of $n$ spins the ground states of a local Hamiltonian with energy gap $\epsilon$ are constant-fold degenerate. Then, the Renyi entanglement entropy $R_\alpha(0<\alpha<1)$ of any ground state across any cut is upper bounded by $\tilde O(\alpha^{-3}/\epsilon)$, and any ground state can be well approximated by a matrix product state of subpolynomial bond dimension $2^{\tilde O(\epsilon^{-1/4}\log^{3/4}n)}$.

•Mar 3, 2014•1 citation

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

Approximating the ground state of gapped quantum spin systems

Eman Hamza, Spyridon Michalakis, Bruno Nachtergaele +1 more

We consider quantum spin systems defined on finite sets V equipped with a metric. In typical examples, V is a large, but finite subset of Zd. For finite range Hamiltonians with uniformly bounded interaction terms and a unique, gapped ground state, we demonstrate a locality property of the corresponding ground state projector. In such systems, this ground state projector can be approximated by the product of observables with quantifiable supports. In fact, given any subset X⊂V the ground state projector can be approximated by the product of two projections, one supported on X and one supported on Xc, and a bounded observable supported on a boundary region in such a way that as the boundary region increases, the approximation becomes better. This result generalizes to multidimensional models, a result of Hastings that was an important part of his proof of an area law in one dimension [“An area law for one dimensional quantum systems,” J. Stat. Mech.: Theory Exp. 2007, 08024].

arXiv:0904.4642•Journal of Mathematical Physics•Sep 1, 2009•15 citations
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,
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 previous area-law proofs. Such approximations have been explicitly derived for 1D gapped local Hamiltonians and 2D frustration-free locally-gapped Hamiltonians. As a corollary, we show that in 1D gapped local Hamiltonians, for any ε>0\varepsilon>0ε>0 and any bi-partition L∪LcL\cup L^cL∪Lc of the system, \begin{align*} \mathrm I_{\max}^\varepsilon (L:L^c)_Ω \le \mathrm O \big( \log (|L|\log(d))+\log(1/\varepsilon)\big), \end{align*} where ∣L∣|L|∣L∣ represents the number of sites in LLL, ddd is the dimension of a site and $ \mathrm I_{\max}^\varepsilon (L:L^c)_Ω $ represents the ε\varepsilonε-\emph{smoothed maximum mutual information} with respect to the L:LcL:L^cL:Lc partition in ΩΩΩ. From this bound we then conclude I(L:Lc)Ω≤O(log⁡(∣L∣log⁡(d)))\mathrm I (L:L^c)_Ω \le \mathrm O\big(\log(|L|\log(d))\big)I(L:Lc)Ω​≤O(log(∣L∣log(d))) -- an area law for the mutual information in 1D systems with a logarithmic correction. In addition, we show that ΩΩΩ can be approximated in trace norm up to ε\varepsilonε with a state of Schmidt rank of at most poly(∣L∣/ε)\mathrm{poly}(|L|/\varepsilon)poly(∣L∣/ε), leading to a good MPO approximation for ΩΩΩ with polynomial bond dimension. Similar corollaries are derived for the mutual information of 2D frustration-free and locally-gapped local Hamiltonians.
We show an area law in the mutual information for the maximally-mixed state Ω\Omega Ω 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 previous area-law proofs. Such approximations have been explicitly derived for 1D gapped local Hamiltonians and 2D frustration-free locally-gapped Hamiltonians. As a corollary, we show that in 1D gapped local Hamiltonians, for any ϵ>0\epsilon >0ϵ>0 and any bipartition L∪LcL\cup L^cL∪Lc of the system, Imax⁡ϵ  ⁣ ⁣(L:Lc)Ω≤O(log⁡(∣L∣log⁡(d))+log⁡(1/ϵ)),\begin{aligned} \textrm{I}^\epsilon _{\max } \, \! \! \left( L : L^c \right) _{\Omega } \le {\textrm{O}}\left( \log (|L|\log (d))+\log (1/\epsilon )\right) , \end{aligned}Imaxϵ​(L:Lc)Ω​≤O(log(∣L∣log(d))+log(1/ϵ)),​ where |L| represents the number of sites in L, d is the dimension of a site and Imax⁡ϵ  ⁣ ⁣(L:Lc)Ω \textrm{I}^\epsilon _{\max } \, \! \! \left( L : L^c \right) _{\Omega }Imaxϵ​(L:Lc)Ω​ represents the ϵ\epsilon ϵ -smoothed maximum mutual information with respect to the L:LcL:L^cL:Lc partition in Ω\Omega Ω . From this bound we then conclude I  ⁣ ⁣(L:Lc)Ω≤O(log⁡(∣L∣log⁡(d))) \textrm{I} \, \! \! \left( L : L^c \right) _\Omega \le {\textrm{O}}\left( \log (|L|\log (d))\right) I(L:Lc)Ω​≤O(log(∣L∣log(d))) – an area law for the mutual information in 1D systems with a logarithmic correction. In addition, we show that Ω\Omega Ω can be approximated in trace norm up to ϵ\epsilon ϵ with a state of Schmidt rank of at most poly(∣L∣log⁡(d)/ϵ)\textrm{poly}(|L|\log (d)/\epsilon )poly(∣L∣log(d)/ϵ) , leading to a good MPO approximation for Ω\Omega Ω with polynomial bond dimension. Similar corollaries are derived for the mutual information of 2D frustration-free and locally-gapped local Hamiltonians.
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.
An area law is proved for the Renyi entanglement entropy of possibly degenerate ground states in one-dimensional gapped quantum systems. Suppose in a chain of nnn spins the ground states of a local Hamiltonian with energy gap ϵ\epsilonϵ are constant-fold degenerate. Then, the Renyi entanglement entropy Rα(0<α<1)R_\alpha(0<\alpha<1)Rα​(0<α<1) of any ground state across any cut is upper bounded by O~(α−3/ϵ)\tilde O(\alpha^{-3}/\epsilon)O~(α−3/ϵ), and any ground state can be well approximated by a matrix product state of subpolynomial bond dimension 2O~(ϵ−1/4log⁡3/4n)2^{\tilde O(\epsilon^{-1/4}\log^{3/4}n)}2O~(ϵ−1/4log3/4n).
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 consider quantum spin systems defined on finite sets V equipped with a metric. In typical examples, V is a large, but finite subset of Zd. For finite range Hamiltonians with uniformly bounded interaction terms and a unique, gapped ground state, we demonstrate a locality property of the corresponding ground state projector. In such systems, this ground state projector can be approximated by the product of observables with quantifiable supports. In fact, given any subset X⊂V the ground state projector can be approximated by the product of two projections, one supported on X and one supported on Xc, and a bounded observable supported on a boundary region in such a way that as the boundary region increases, the approximation becomes better. This result generalizes to multidimensional models, a result of Hastings that was an important part of his proof of an area law in one dimension [“An area law for one dimensional quantum systems,” J. Stat. Mech.: Theory Exp. 2007, 08024].