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.
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.
Quantum Hamiltonian complexity studies computational complexity aspects of local Hamiltonians and ground states; these questions can be viewed as generalizations of classical computational complexity problems related to local constraint satisfaction (such as SAT), with the additional ingredient of multi-particle entanglement. This additional ingredient of course makes generalizations of celebrated theorems such as the PCP theorem from classical to the quantum domain highly non-trivial; it also raises entirely new questions such as bounds on entanglement and correlations in ground states, and in particular area laws. We propose a simple combinatorial tool that helps to handle such questions: it is a simplified, yet more general version of the detectability lemma introduced by us in the more restricted context on quantum gap amplification a year ago. Here, we argue that this lemma is applicable in much more general contexts. We use it to provide a simplified and more combinatorial proof of Hastings' 1D area law, together with a less than 1 page proof of the decay of correlations in gapped local Hamiltonian systems in any constant dimension. We explain how the detectability lemma can replace the Lieb-Robinson bound in various other contexts, and argue that it constitutes a basic tool for the study of local Hamiltonians and their ground states in relation to various questions in quantum Hamiltonian complexity.
Quantum Hamiltonian complexity, an emerging area at the intersection of condensed matter physics and quantum complexity theory, studies the properties of local Hamiltonians and their ground states. In this paper we focus on a seemingly specialized technical tool, the detectability lemma (DL), introduced in the context of the quantum PCP challenge (Aharonov et al 2009 arXiv:0811.3412), which is a major open question in quantum Hamiltonian complexity. We show that a reformulated version of the lemma is a versatile tool that can be used in place of the celebrated Lieb-Robinson (LR) bound to prove several important results in quantum Hamiltonian complexity. The resulting proofs are much simpler, more combinatorial and provide a plausible path toward tackling some fundamental open questions in Hamiltonian complexity. We provide an alternative simpler proof of the DL that removes a key restriction in the original statement (Aharonov et al 2009 arXiv:0811.3412), making it more suitable for the broader context of quantum Hamiltonian complexity. Specifically, we first use the DL to provide a one-page proof of Hastings' result that the correlations in the ground states of gapped Hamiltonians decay exponentially with distance (Hastings 2004 Phys. Rev. B 69 104431). We then apply the DL to derive a simpler and more intuitive proof of Hastings' seminal one-dimensional (1D) area law (Hastings 2007 J. Stat. Mech. (2007) P8024) (both these proofs are restricted to frustration-free systems). Proving the area law for two and higher dimensions is one of the most important open questions in the field of Hamiltonian complexity, and the combinatorial nature of the
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 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.
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 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[Θ~((Alogε−1)2/3)] when logε−1≳A. Thus α=1 is the sharp threshold for a universal Rényi area law within this adiabatically connected class.