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

Sharp implications of AGSPs for degenerate ground spaces

Nilin Abrahamsen

Published Mar 18, 2020• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2003.08406

Related papers

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

Nilin Abrahamsen

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.

arXiv:2004.02850•Apr 6, 2020•0 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

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

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

Polynomial-time degenerate ground state approximation of gapped 1D Hamiltonians.

Christopher T. Chubb, Steven T. Flammia

In spite of a plethora of no-go results that prevent classically efficient simulation of quantum systems in general, heuristic methods[1] have seen great success, proving typically efficient in practice. The downside of these heuristic methods is that we lack a rigorous understanding of how, and for which systems, they fail[2]. Provably efficient algorithms – even if practically surpassed by heuristic methods – are of key importance for understanding the true worst-case complexity of simulation. The cutting edge for provably efficient simulation is the ground state approximation of 1D spin systems. Under the assumption of a gap, there exists a provably efficient algorithm[3, 4] for approximation of a unique ground state of such systems; we present ongoing work to extend this algorithm to work for degenerate systems. This result comes in the wake of a recent degenerate extension of the area law[5], an important structural bound on the complexity of ground states. In practice this algorithm is no match for heuristic analogues such as the density matrix renormalisation group. However, it does add to the increasing understanding of the systems for which provably efficient simulation is attainable, and might hopefully lead to a future algorithm that is both provably and practically efficient.

•Jan 1, 2014•0 citations
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 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.
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,
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.
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})}).
In spite of a plethora of no-go results that prevent classically efficient simulation of quantum systems in general, heuristic methods[1] have seen great success, proving typically efficient in practice. The downside of these heuristic methods is that we lack a rigorous understanding of how, and for which systems, they fail[2]. Provably efficient algorithms – even if practically surpassed by heuristic methods – are of key importance for understanding the true worst-case complexity of simulation. The cutting edge for provably efficient simulation is the ground state approximation of 1D spin systems. Under the assumption of a gap, there exists a provably efficient algorithm[3, 4] for approximation of a unique ground state of such systems; we present ongoing work to extend this algorithm to work for degenerate systems. This result comes in the wake of a recent degenerate extension of the area law[5], an important structural bound on the complexity of ground states. In practice this algorithm is no match for heuristic analogues such as the density matrix renormalisation group. However, it does add to the increasing understanding of the systems for which provably efficient simulation is attainable, and might hopefully lead to a future algorithm that is both provably and practically efficient.