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

Quantum complexity and generalized area law in fully connected models

Donghoon Kim, Tomotaka Kuwahara

Published Nov 4, 2024• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2411.02140

Related papers

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

Colloquium : Area laws for the entanglement entropy

Jens Eisert, M. Cramer, Martin Bodo Plenio

Physical interactions in quantum many-body systems are typically local: Individual constituents interact mainly with their few nearest neighbors. This locality of interactions is inherited by a decay of correlation functions, but also reflected by scaling laws of a quite profound quantity: the entanglement entropy of ground states. This entropy of the reduced state of a subregion often merely grows like the boundary area of the subregion, and not like its volume, in sharp contrast with an expected extensive behavior. Such ``area laws'' for the entanglement entropy and related quantities have received considerable attention in recent years. They emerge in several seemingly unrelated fields, in the context of black hole physics, quantum information science, and quantum many-body physics where they have important implications on the numerical simulation of lattice models. In this Colloquium the current status of area laws in these fields is reviewed. Center stage is taken by rigorous results on lattice models in one and higher spatial dimensions. The differences and similarities between bosonic and fermionic models are stressed, area laws are related to the velocity of information propagation in quantum lattice models, and disordered systems, nonequilibrium situations, and topological entanglement entropies are discussed. These questions are considered in classical and quantum systems, in their ground and thermal states, for a variety of correlation measures. A significant proportion is devoted to the clear and quantitative connection between the entanglement content of states and the possibility of their efficient numerical simulation. Matrix-product states, higher-dimensional analogs, and variational sets from entanglement renormalization are also discussed and the paper is concluded by highlighting the implications of area laws on quantifying the effective degrees of freedom that need to be considered in simulations of quantum states.

arXiv:0808.3773•Reviews of Modern Physics•Feb 4, 2010•3,081 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

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 for one-dimensional quantum systems

M. B. Hastings

We prove an area law for the entanglement entropy in gapped one-dimensional quantum systems. The bound on the entropy grows surprisingly rapidly with the correlation length; we discuss this in terms of properties of quantum expanders and present a conjecture on matrix product states which may provide an alternate way of arriving at an area law. We also show that, for gapped, local systems, the bound on Von Neumann entropy implies a bound on Rényi entropy for sufficiently large α<1 and implies the ability to approximate the ground state by a matrix product state.

arXiv:0705.2024•Journal of Statistical Mechanics Theory and Experiment•Aug 20, 2007•1,263 citations

Entanglement area law in interacting bosons from the Bose-Hubbard model to ϕ4 theory and beyond

Donghoon Kim, Tomotaka Kuwahara

The entanglement area law is a universal principle that characterizes quantum many-body phases and underpins tensor network algorithms. Traditionally, its validity has been limited to systems with short-range interactions and bounded local energy. Achieving a complete generalization that removes both of these constraints has been a longstanding goal in quantum many-body theory, especially for interacting boson systems where unbounded energy presents intrinsic difficulties. In this work, we rigorously prove the area law for one-dimensional interacting boson systems with long-range interactions, covering broad models including the Bose-Hubbard and ϕ4 classes. Furthermore, we establish an efficiency guarantee for Matrix-Product-State approximations of the ground states, offering a practical route to numerical simulation. One of our main technical contributions is a general method for Hilbert space dimension reduction, whose applicability extends to arbitrary spatial dimensions. These results address two major challenges simultaneously and provide important foundations for simulating long-range cold atomic systems. Entanglement area law has been established in systems with short range interactions and bounded local energy. Here the authors extend the proof to 1D bosonic systems with long-range interactions and unbounded local energy and outline implications for matrix product state approximations of the ground states.

arXiv:2411.02157•Nature Communications•May 20, 2026•3 citations
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.
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.
Physical interactions in quantum many-body systems are typically local: Individual constituents interact mainly with their few nearest neighbors. This locality of interactions is inherited by a decay of correlation functions, but also reflected by scaling laws of a quite profound quantity: the entanglement entropy of ground states. This entropy of the reduced state of a subregion often merely grows like the boundary area of the subregion, and not like its volume, in sharp contrast with an expected extensive behavior. Such ``area laws'' for the entanglement entropy and related quantities have received considerable attention in recent years. They emerge in several seemingly unrelated fields, in the context of black hole physics, quantum information science, and quantum many-body physics where they have important implications on the numerical simulation of lattice models. In this Colloquium the current status of area laws in these fields is reviewed. Center stage is taken by rigorous results on lattice models in one and higher spatial dimensions. The differences and similarities between bosonic and fermionic models are stressed, area laws are related to the velocity of information propagation in quantum lattice models, and disordered systems, nonequilibrium situations, and topological entanglement entropies are discussed. These questions are considered in classical and quantum systems, in their ground and thermal states, for a variety of correlation measures. A significant proportion is devoted to the clear and quantitative connection between the entanglement content of states and the possibility of their efficient numerical simulation. Matrix-product states, higher-dimensional analogs, and variational sets from entanglement renormalization are also discussed and the paper is concluded by highlighting the implications of area laws on quantifying the effective degrees of freedom that need to be considered in simulations of quantum states.
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).
We prove an area law for the entanglement entropy in gapped one-dimensional quantum systems. The bound on the entropy grows surprisingly rapidly with the correlation length; we discuss this in terms of properties of quantum expanders and present a conjecture on matrix product states which may provide an alternate way of arriving at an area law. We also show that, for gapped, local systems, the bound on Von Neumann entropy implies a bound on Rényi entropy for sufficiently large α<1 and implies the ability to approximate the ground state by a matrix product state.
The entanglement area law is a universal principle that characterizes quantum many-body phases and underpins tensor network algorithms. Traditionally, its validity has been limited to systems with short-range interactions and bounded local energy. Achieving a complete generalization that removes both of these constraints has been a longstanding goal in quantum many-body theory, especially for interacting boson systems where unbounded energy presents intrinsic difficulties. In this work, we rigorously prove the area law for one-dimensional interacting boson systems with long-range interactions, covering broad models including the Bose-Hubbard and ϕ4 classes. Furthermore, we establish an efficiency guarantee for Matrix-Product-State approximations of the ground states, offering a practical route to numerical simulation. One of our main technical contributions is a general method for Hilbert space dimension reduction, whose applicability extends to arbitrary spatial dimensions. These results address two major challenges simultaneously and provide important foundations for simulating long-range cold atomic systems. Entanglement area law has been established in systems with short range interactions and bounded local energy. Here the authors extend the proof to 1D bosonic systems with long-range interactions and unbounded local energy and outline implications for matrix product state approximations of the ground states.