It is commonly believed that area laws for entanglement entropies imply that a quantum many-body state can be faithfully represented by efficient tensor network states—a conjecture frequently stated in the context of numerical simulations and analytical considerations. In this work, we show that this is in general not the case, except in one-dimension. We prove that the set of quantum many-body states that satisfy an area law for all Renyi entropies contains a subspace of exponential dimension. We then show that there are states satisfying area laws for all Renyi entropies but cannot be approximated by states with a classical description of small Kolmogorov complexity, including polynomial projected entangled pair states or states of multi-scale entanglement renormalisation. Not even a quantum computer with post-selection can efficiently prepare all quantum states fulfilling an area law, and we show that not all area law states can be eigenstates of local Hamiltonians. We also prove translationally and rotationally invariant instances of these results, and show a variation with decaying correlations using quantum error-correcting codes.
It is commonly believed that area laws for entanglement entropies imply that a quantum many-body state can be faithfully represented by efficient tensor network states—a conjecture frequently stated in the context of numerical simulations and analytical considerations. In this work, we show that this is in general not the case, except in one-dimension. We prove that the set of quantum many-body states that satisfy an area law for all Renyi entropies contains a subspace of exponential dimension. We then show that there are states satisfying area laws for all Renyi entropies but cannot be approximated by states with a classical description of small Kolmogorov complexity, including polynomial projected entangled pair states or states of multi-scale entanglement renormalisation. Not even a quantum computer with post-selection can efficiently prepare all quantum states fulfilling an area law, and we show that not all area law states can be eigenstates of local Hamiltonians. We also prove translationally and rotationally invariant instances of these results, and show a variation with decaying correlations using quantum error-correcting codes.
It is commonly believed that area laws for entanglement entropies imply that a quantum many-body state can be faithfully represented by efficient tensor network states - a conjecture frequently stated in the context of numerical simulations and analytical considerations. In this work, we show that this is in general not the case, except in one dimension. We prove that the set of quantum many-body states that satisfy an area law for all Renyi entropies contains a subspace of exponential dimension. Establishing a novel link between quantum many-body theory and the theory of communication complexity, we then show that there are states satisfying area laws for all Renyi entropies but cannot be approximated by states with a classical description of small Kolmogorov complexity, including polynomial projected entangled pair states (PEPS) or states of multi-scale entanglement renormalisation (MERA). Not even a quantum computer with post-selection can efficiently prepare all quantum states fulfilling an area law, and we show that not all area law states can be eigenstates of local Hamiltonians. We also prove translationally invariant and isotropic instances of these results, and show a variation with decaying correlations using quantum error-correcting codes.
Classical simulation of quantum many-body systems is a fundamental challenge due to their exponentially large Hilbert spaces. Tensor network states are a powerful ansatz to efficiently represent many physically relevant quantum states. A key question is the bond dimension—which determines the number of parameters in the ansatz—required to approximate all local properties to accuracy δ. In one dimension, we prove that an area law for the Rényi entanglement entropyRαwith index αRα(αeO(1/δ). In both one and two dimensions, analogous results are obtained for states with logarithmic corrections to the area law. These findings rigorously justify the common practice of using a system-size-independent bond dimension in tensor network simulations.
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.
Tensor networks [1] and in particular matrix-product states [2] have proven extremely useful for the investigation of quantum many-body states, such as, e.g., ground states of local many-body Hamiltonians. They provide an efficient description of these states, avoiding the exponential increase of Hilbert space with particle number at the cost of limiting the entanglement. In particular for matrix-product states, the relation between area laws of Rényi entanglement entropies and efficient simulability of quantum states is nowadays well understood [3]. However, it is not always clear a priori whether or not the relevant states of a given quantum system (e.g., its eigenstates) fulfil such an area law and can thus efficiently be represented by matrix-product states. By investigating specific states of relevance for many-body quantum dynamics, in particular symmetric states and Fock states, we here aim to derive criteria beyond the area law to assess for which quantum systems a description by matrix-product states or more general tensor networks is beneficial. [1] S. Montangero, Introduction to Tensor Networks (Springer, Cham, 2018) [2] J. I. Cirac, D. Pérez-García, N. Schuch, and F. Verstraete, Rev. Mod. Phys 93, 045003 (2021) [3] N. Schuch, M. W. Wolf, F. Verstraete, and J. I. Cirac, Phys. Rev. Lett. 100, 030504 (2008)
Nonstabilizerness is a necessary resource for quantum systems to lie beyond the classically simulable regime. With the advent of stabilizer α-Rényi entropies, nonstabilizerness has also become a many-body diagnostic, complementary to entanglement. While deciding whether an arbitrary quantum state has nonstabilizerness is provably hard, such states already require a description exponentially large in the number of qubits and are thus out of reach for many-body physics. Here we instead consider 2D tensor network (TN) states, which compactly capture states obeying an entanglement area law, and ask whether they admit a simpler algorithm for the same task. In contrast to the 1D case, we prove that, even at small, constant bond dimension, computing the stabilizer entropy of 2D TN states is #P-hard for any integer α≥2, and deciding stabilizer membership is C=P-complete. The corresponding constant-accuracy problems remain C=P-hard. We further prove that deciding whether a PEPS can be transformed into a stabilizer state by local unitaries over a specified bipartition is C=P-hard. Under standard complexity assumptions, these results rule out classical or quantum algorithms with polynomial resources for all three tasks in the worst case.
Classical simulation of quantum many-body systems is in general a challenging problem for the simple reason that the dimension of the Hilbert space grows exponentially with the system size. In particular, merely encoding a generic quantum many-body state requires an exponential number of bits. However, condensed matter physicists are mostly interested in local Hamiltonians and especially their ground states, which are highly non-generic. Thus, we might hope that at least some physical systems allow efficient classical simulation.Starting with one-dimensional (1D) quantum systems (i.e., the simplest nontrivial case), the first basic question is: Which classes of states have efficient classical representations? It turns out that this question is quantitatively related to the amount of entanglement in the state, for states with ``little entanglement'' are well approximated by matrix product states (a data structure that can be manipulated efficiently on a classical computer). At a technical level, the mathematical notion for ``little entanglement'' is area law, which has been proved for unique ground states in 1D gapped systems. We establish an area law for constant-fold degenerate ground states in 1D gapped systems and thus explain the effectiveness of matrix-product-state methods in (e.g.) symmetry breaking phases. This result might not be intuitively trivial as degenerate ground states in gapped systems can be long-range correlated.Suppose an efficient classical representation exists. How can one find it efficiently? The density matrix renormalization group is the leading numerical method for computing ground states in 1D quantum systems. However, it is a heuristic algorithm and the possibility that it may fail in some cases cannot be completely ruled out. Recently, a provably efficient variant of the density matrix renormalization group has been developed for frustration-free 1D gapped systems. We generalize this algorithm to all (i.e., possibly frustrated) 1D gapped systems. Note that the ground-state energy of 1D gapless Hamiltonians is computationally intractable even in the presence of translational invariance.It is tempting to extend methods and tools in 1D to two and higher dimensions (2+D), e.g., matrix product states are generalized to tensor network states. Since an area law for entanglement (if formulated properly) implies efficient matrix product state representations in 1D, an interesting question is whether a similar implication holds in 2+D. Roughly speaking, we show that an area law for entanglement (in any reasonable formulation) does not always imply efficient tensor network representations of the ground states of 2+D local Hamiltonians even in the presence of translational invariance. It should be emphasized that this result does not contradict with the common sense that in practice quantum states with more entanglement usually require more space to be stored classically; rather, it demonstrates that the relationship between entanglement and efficient classical representations is still far from being well understood.Excited eigenstates participate in the dynamics of quantum systems and are particularly relevant to the phenomenon of many-body localization (absence of transport at finite temperature in strongly correlated systems). We study the entanglement of excited eigenstates in random spin chains and expect that its singularities coincide with dynamical quantum phase transitions. This expectation is confirmed in the disordered quantum Ising chain using both analytical and numerical methods.Finally, we study the problem of generating ground states (possibly with topological order) in 1D gapped systems using quantum circuits. This is an interesting problem both in theory and in practice. It not only characterizes the essential difference between the entanglement patterns that give rise to trivial and nontrivial topological order, but also quantifies the difficulty of preparing quantum states with a quantum computer (in experiments).