© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2004.15009

From communication complexity to an entanglement spread area law in the ground state of gapped local Hamiltonians

Anurag Anshu, Aram W. Harrow, Mehdi Soleimanifar

Published Apr 30, 2020• 2 citations

Abstract

In this work, we make a connection between two seemingly different problems. The first problem involves characterizing the properties of entanglement in the ground state of gapped local Hamiltonians, which is a central topic in quantum many-body physics. The second problem is on the quantum communication complexity of testing bipartite states with EPR assistance, a well-known question in quantum information theory. We construct a communication protocol for testing (or measuring) the ground state and use its communication complexity to reveal a new structural property for the ground state entanglement. This property, known as the entanglement spread, roughly measures the ratio between the largest and the smallest Schmidt coefficients across a cut in the ground state. Our main result shows that gapped ground states possess limited entanglement spread across any cut, exhibiting an "area law" behavior. Our result quite generally applies to any interaction graph with an improved bound for the special case of lattices. This entanglement spread area law includes interaction graphs constructed in [Aharonov et al., FOCS'14] that violate a generalized area law for the entanglement entropy. Our construction also provides evidence for a conjecture in physics by Li and Haldane on the entanglement spectrum of lattice Hamiltonians [Li and Haldane, PRL'08]. On the technical side, we use recent advances in Hamiltonian simulation algorithms along with quantum phase estimation to give a new construction for an approximate ground space projector (AGSP) over arbitrary interaction graphs.

DOI: 10.48550/arxiv.2004.15009

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•40 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

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

On the hardness of learning ground state entanglement of geometrically local Hamiltonians

Adam Bouland, Chenyi Zhang, Zixin Zhou

Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In this work we study the computational complexity of this problem, given the Hamiltonian as input. Our main result is that to show it is cryptographically hard to determine if the ground state of a geometrically local, polynomially gapped Hamiltonian on qudits ($d=O(1)$) has near-area law vs near-volume law entanglement. This improves prior work of Bouland et al. (arXiv:2311.12017) showing this for non-geometrically local Hamiltonians. In particular we show this problem is roughly factoring-hard in 1D, and LWE-hard in 2D. Our proof works by constructing a novel form of public-key pseudo-entanglement which is highly space-efficient, and combining this with a modification of Gottesman and Irani's quantum Turing machine to Hamiltonian construction. Our work suggests that the problem of learning so-called "gapless" quantum phases of matter might be intractable.

arXiv:2411.04353•Nov 7, 2024•1 citation

Quantum complexity and generalized area law in fully connected models

Donghoon Kim, Tomotaka Kuwahara

The area law for entanglement entropy captures a fundamental constraint on the complexity of quantum many-body ground states and enables their efficient description. While the area law is rigorously established in one dimension, its status in higher-dimensional local systems remains unresolved, and it does not hold in general for geometrically non-local systems. Here, we establish a generalized area law for gapped ground states of fully connected Hamiltonians. We show that the bipartite entanglement entropy grows at most logarithmically with system size despite the absence of geometric locality. In the ground state, each site is only weakly entangled with the rest, while configurations with extensive local fluctuations are strongly suppressed, effectively restricting the accessible Hilbert space. As a consequence, the ground state admits a matrix product state approximation with polynomial bond dimension with respect to the system size at fixed accuracy. In the permutation-invariant setting, we further prove a constant entanglement bound and demonstrate that the gapped ground state can be computed in time polylogarithmic in the system size. These results show that low entanglement complexity need not rely on geometric locality, broadening the conceptual and computational scope of area laws.

arXiv:2411.02140•Nov 4, 2024•1 citation

Entanglement area law for 1D gauge theories and bosonic systems

Nilin Abrahamsen, Tong Yu, Bao, Ning +2 more

We prove an entanglement area law for a class of 1D quantum systems involving infinite-dimensional local Hilbert spaces. This class of quantum systems include bosonic models such as the Hubbard-Holstein model, and both U(1) and SU(2) lattice gauge theories in one spatial dimension. Our proof relies on new results concerning the robustness of the ground state and spectral gap to the truncation of Hilbert space, applied within the approximate ground state projector (AGSP) framework from previous work. In establishing this area law, we develop a system-size independent bound on the expectation value of local observables for Hamiltonians without translation symmetry, which may be of separate interest. Our result provides theoretical justification for using tensor network methods to study the ground state properties of quantum systems with infinite local degrees of freedom.

arXiv:2203.16012•Mar 30, 2022•3 citations

In this work, we make a connection between two seemingly different problems. The first problem involves characterizing the properties of entanglement in the ground state of gapped local Hamiltonians, which is a central topic in quantum many-body physics. The second problem is on the quantum communication complexity of testing bipartite states with EPR assistance, a well-known question in quantum information theory. We construct a communication protocol for testing (or measuring) the ground state and use its communication complexity to reveal a new structural property for the ground state entanglement. This property, known as the entanglement spread, roughly measures the ratio between the largest and the smallest Schmidt coefficients across a cut in the ground state. Our main result shows that gapped ground states possess limited entanglement spread across any cut, exhibiting an "area law" behavior. Our result quite generally applies to any interaction graph with an improved bound for the special case of lattices. This entanglement spread area law includes interaction graphs constructed in [Aharonov et al., FOCS'14] that violate a generalized area law for the entanglement entropy. Our construction also provides evidence for a conjecture in physics by Li and Haldane on the entanglement spectrum of lattice Hamiltonians [Li and Haldane, PRL'08]. On the technical side, we use recent advances in Hamiltonian simulation algorithms along with quantum phase estimation to give a new construction for an approximate ground space projector (AGSP) over arbitrary interaction graphs.

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.

The Rényi area law conjecture is false below

α=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<α<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.

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.

Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In this work we study the computational complexity of this problem, given the Hamiltonian as input. Our main result is that to show it is cryptographically hard to determine if the ground state of a geometrically local, polynomially gapped Hamiltonian on qudits (

d=O(1)

) has near-area law vs near-volume law entanglement. This improves prior work of Bouland et al. (arXiv:2311.12017) showing this for non-geometrically local Hamiltonians. In particular we show this problem is roughly factoring-hard in 1D, and LWE-hard in 2D. Our proof works by constructing a novel form of public-key pseudo-entanglement which is highly space-efficient, and combining this with a modification of Gottesman and Irani's quantum Turing machine to Hamiltonian construction. Our work suggests that the problem of learning so-called "gapless" quantum phases of matter might be intractable.

The area law for entanglement entropy captures a fundamental constraint on the complexity of quantum many-body ground states and enables their efficient description. While the area law is rigorously established in one dimension, its status in higher-dimensional local systems remains unresolved, and it does not hold in general for geometrically non-local systems. Here, we establish a generalized area law for gapped ground states of fully connected Hamiltonians. We show that the bipartite entanglement entropy grows at most logarithmically with system size despite the absence of geometric locality. In the ground state, each site is only weakly entangled with the rest, while configurations with extensive local fluctuations are strongly suppressed, effectively restricting the accessible Hilbert space. As a consequence, the ground state admits a matrix product state approximation with polynomial bond dimension with respect to the system size at fixed accuracy. In the permutation-invariant setting, we further prove a constant entanglement bound and demonstrate that the gapped ground state can be computed in time polylogarithmic in the system size. These results show that low entanglement complexity need not rely on geometric locality, broadening the conceptual and computational scope of area laws.

We prove an entanglement area law for a class of 1D quantum systems involving infinite-dimensional local Hilbert spaces. This class of quantum systems include bosonic models such as the Hubbard-Holstein model, and both U(1) and SU(2) lattice gauge theories in one spatial dimension. Our proof relies on new results concerning the robustness of the ground state and spectral gap to the truncation of Hilbert space, applied within the approximate ground state projector (AGSP) framework from previous work. In establishing this area law, we develop a system-size independent bound on the expectation value of local observables for Hamiltonians without translation symmetry, which may be of separate interest. Our result provides theoretical justification for using tensor network methods to study the ground state properties of quantum systems with infinite local degrees of freedom.