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

WORLD SCIENTIFIC eBooks

AN IMPROVED AREA-LAW FOR THE GROUND STATES OF 1D GAPPED HAMILTONIANS

Itai Arad

Published Oct 1, 2013• 0 citations
Publisher

Abstract

Originating from the works of Bekenstein and Hawking on the entropy of black holes, area laws constitute a central tool for understanding entanglement and locality properties in quantum systems. Essentially, in a system that obeys an area law, the entanglement entropy of a bounded region scales like its boundary area, rather than its volume. In 2007, in a seminal paper, Hastings proved that all 1D quantum spin systems with a constant spectral gap obey an area law in their ground state. The proof was based on the analytical tool of Lieb-Robinson velocity. A major open problem is whether an area law holds also in 2 or more dimensions. In this talk I will present a line of research of the past couple of years culminating in an alternative, entirely combinatorial proof for the 1D area law. The proof uses the Chebyshev polynomial to describe the structure of entanglement in the ground state, yielding an exponentially better bound on the entanglement entropy compared to Hastings' bound. Just a slight improvement of our parameters would give a sub-volume law for the 2D case; the combinatorial approach raises hopes that such improvements might be doable. Joint work with Alexei Kitaev, Caltech, Zeph Landau and Umesh Vazirani, both at University of California at Berkeley. Note from Publisher: This article contains the abstract only.

DOI
10.1142/9789814449243_0051

Related papers

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

The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach

Dorit Aharonov, Itai Arad, Zeph A. Landau +1 more

The classical description of quantum states is in general exponential in the number of qubits. Can we get polynomial descriptions for more restricted sets of states such as ground states of interesting subclasses of local Hamiltonians? This is the basic problem in the study of the complexity of ground states, and requires an understanding of multi-particle entanglement and quantum correlations in such states. Area laws provide a fundamental ingredient in the study of the complexity of ground states, since they offer a way to bound in a quantitative way the entanglement in such states. Although they have long been conjectured for many body systems in arbitrary dimensions, a general rigorous was only recently proved in Hastings' seminal paper [8] for ID systems. In this paper, we give a combinatorial proof of the ID area law for the special case of frustration free systems, improving by an exponential factor the scaling in terms of the inverse spectral gap and the dimensionality of the particles. The scaling in terms of the dimension of the particles is a potentially important issue in the context of resolving the 2D case and higher dimensions, which is one of the most important open questions in Hamiltonian complexity. Our proof is based on a reformulation of the detectability lemma, introduced by us in the context of quantum gap amplification [1]. We give an alternative proof of the detectability lemma, which is not only simpler and more intuitive than the original proof, but also removes a key restriction in the original statement, making it more suitable for this new context. We also give a one page proof of Hastings' proof that the correlations in the ground states of gapped Hamiltonians decay exponentially with the distance, demonstrating the simplicity of the combinatorial approach for those problems.

Annual Symposium on Foundations of Computer Science•Oct 1, 2011•36 citations

Improved one-dimensional area law for frustration-free systems

Itai Arad, Zeph A. Landau, Umesh V. Vazirani

We present a new proof for the 1D area law for frustration-free systems with a constant gap, which exponentially improves the entropy bound in Hastings\^a 1D area law and which is tight to within a polynomial factor. For particles of dimension $d$, spectral gap $\ensuremath{\epsilon}>0$, and interaction strength at most $J$, our entropy bound is ${S}_{1D}\ensuremath{\le}\mathcal{O}(1)\ifmmode\cdot\else\textperiodcentered\fi{}{X}^{3}{\mathrm{log}}^{8}X$, where $X\stackrel{\mathrm{def}}{=}(J\mathrm{log}d)/\ensuremath{\epsilon}$. Our proof is completely combinatorial, combining the detectability lemma with basic tools from approximation theory. In higher dimensions, when the bipartitioning area is $|\ensuremath{\partial}L|$, we use additional local structure in the proof and show that $S\ensuremath{\le}\mathcal{O}(1)\ifmmode\cdot\else\textperiodcentered\fi{}{|\ensuremath{\partial}L|}^{2}{\mathrm{log}}^{6}|\ensuremath{\partial}L|\ifmmode\cdot\else\textperiodcentered\fi{}{X}^{3}{\mathrm{log}}^{8}X$. This is at the cusp of being nontrivial in the 2D case, in the sense that any further improvement would yield a subvolume law.

arXiv:1111.2970•Physical Review B•May 29, 2012•84 citations

The Rényi area law conjecture is false below $α=1$ in high dimensions

Tomotaka Kuwahara

Area laws express the expectation that entanglement in gapped quantum ground states scales with a boundary rather than a volume. In one dimension this holds for every Rényi entropy, and the Rényi area-law conjecture asserts the same in higher dimensions for each fixed $0<α<1$. Here we disprove this conjecture in every spatial dimension two and higher. We construct finite-range Hamiltonians with fixed local dimension, bounded interaction strength, unique ground states and a uniform spectral gap, whose ground states exhibit volume-law Rényi entanglement while obeying a von Neumann area law and remaining connected to product states through uniformly gapped local paths. The mechanism is error-space complexity: locally identifiable components of arbitrarily small weight can encode states with high entanglement complexity. We also establish the worst-case rank-error trade-off for approximate ground-state projectors, a key tool in one-dimensional area-law proofs. At fixed gap, the optimal Schmidt rank at projection error $ε$ across a planar cut of cross-section $A$ scales as $\exp[\tildeΘ((A\logε^{-1})^{2/3})]$ when $\logε^{-1}\gtrsim A$. Thus $α=1$ is the sharp threshold for a universal Rényi area law within this adiabatically connected class.

quant-pharXiv:2610.15199•Oct 13, 2026•0 citations

Stability of the Area Law for the Entropy of Entanglement

Spyridon Michalakis

Recent results on the stability of the spectral gap under general perturbations for frustration-free Hamiltonians, have motivated the following question: Does the entanglement entropy of quantum states that are connected to states satisfying an area law along gapped Hamiltonian paths, also satisfy an area law? We answer this question in the affirmative, combining recent advances in quasi-adiabatic evolution and Lieb-Robinson bounds with ideas from the proof of the 1D area law.

arXiv:1206.6900•Jun 28, 2012•37 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
Originating from the works of Bekenstein and Hawking on the entropy of black holes, area laws constitute a central tool for understanding entanglement and locality properties in quantum systems. Essentially, in a system that obeys an area law, the entanglement entropy of a bounded region scales like its boundary area, rather than its volume. In 2007, in a seminal paper, Hastings proved that all 1D quantum spin systems with a constant spectral gap obey an area law in their ground state. The proof was based on the analytical tool of Lieb-Robinson velocity. A major open problem is whether an area law holds also in 2 or more dimensions. In this talk I will present a line of research of the past couple of years culminating in an alternative, entirely combinatorial proof for the 1D area law. The proof uses the Chebyshev polynomial to describe the structure of entanglement in the ground state, yielding an exponentially better bound on the entanglement entropy compared to Hastings' bound. Just a slight improvement of our parameters would give a sub-volume law for the 2D case; the combinatorial approach raises hopes that such improvements might be doable. Joint work with Alexei Kitaev, Caltech, Zeph Landau and Umesh Vazirani, both at University of California at Berkeley. Note from Publisher: This article contains the abstract only.
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})}).
The classical description of quantum states is in general exponential in the number of qubits. Can we get polynomial descriptions for more restricted sets of states such as ground states of interesting subclasses of local Hamiltonians? This is the basic problem in the study of the complexity of ground states, and requires an understanding of multi-particle entanglement and quantum correlations in such states. Area laws provide a fundamental ingredient in the study of the complexity of ground states, since they offer a way to bound in a quantitative way the entanglement in such states. Although they have long been conjectured for many body systems in arbitrary dimensions, a general rigorous was only recently proved in Hastings' seminal paper [8] for ID systems. In this paper, we give a combinatorial proof of the ID area law for the special case of frustration free systems, improving by an exponential factor the scaling in terms of the inverse spectral gap and the dimensionality of the particles. The scaling in terms of the dimension of the particles is a potentially important issue in the context of resolving the 2D case and higher dimensions, which is one of the most important open questions in Hamiltonian complexity. Our proof is based on a reformulation of the detectability lemma, introduced by us in the context of quantum gap amplification [1]. We give an alternative proof of the detectability lemma, which is not only simpler and more intuitive than the original proof, but also removes a key restriction in the original statement, making it more suitable for this new context. We also give a one page proof of Hastings' proof that the correlations in the ground states of gapped Hamiltonians decay exponentially with the distance, demonstrating the simplicity of the combinatorial approach for those problems.
We present a new proof for the 1D area law for frustration-free systems with a constant gap, which exponentially improves the entropy bound in Hastings\^a 1D area law and which is tight to within a polynomial factor. For particles of dimension ddd, spectral gap $\ensuremath{\epsilon}>0$, and interaction strength at most JJJ, our entropy bound is ${S}_{1D}\ensuremath{\le}\mathcal{O}(1)\ifmmode\cdot\else\textperiodcentered\fi{}{X}^{3}{\mathrm{log}}^{8}X$, where $X\stackrel{\mathrm{def}}{=}(J\mathrm{log}d)/\ensuremath{\epsilon}$. Our proof is completely combinatorial, combining the detectability lemma with basic tools from approximation theory. In higher dimensions, when the bipartitioning area is $|\ensuremath{\partial}L|$, we use additional local structure in the proof and show that $S\ensuremath{\le}\mathcal{O}(1)\ifmmode\cdot\else\textperiodcentered\fi{}{|\ensuremath{\partial}L|}^{2}{\mathrm{log}}^{6}|\ensuremath{\partial}L|\ifmmode\cdot\else\textperiodcentered\fi{}{X}^{3}{\mathrm{log}}^{8}X$. This is at the cusp of being nontrivial in the 2D case, in the sense that any further improvement would yield a subvolume law.
The Rényi area law conjecture is false below α=1α=1α=1 in high dimensions
Area laws express the expectation that entanglement in gapped quantum ground states scales with a boundary rather than a volume. In one dimension this holds for every Rényi entropy, and the Rényi area-law conjecture asserts the same in higher dimensions for each fixed 0<α<10<α<10<α<1. Here we disprove this conjecture in every spatial dimension two and higher. We construct finite-range Hamiltonians with fixed local dimension, bounded interaction strength, unique ground states and a uniform spectral gap, whose ground states exhibit volume-law Rényi entanglement while obeying a von Neumann area law and remaining connected to product states through uniformly gapped local paths. The mechanism is error-space complexity: locally identifiable components of arbitrarily small weight can encode states with high entanglement complexity. We also establish the worst-case rank-error trade-off for approximate ground-state projectors, a key tool in one-dimensional area-law proofs. At fixed gap, the optimal Schmidt rank at projection error εεε across a planar cut of cross-section AAA scales as exp⁡[Θ~((Alog⁡ε−1)2/3)]\exp[\tildeΘ((A\logε^{-1})^{2/3})]exp[Θ~((Alogε−1)2/3)] when log⁡ε−1≳A\logε^{-1}\gtrsim Alogε−1≳A. Thus α=1α=1α=1 is the sharp threshold for a universal Rényi area law within this adiabatically connected class.
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).