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:0705.0292 · Physical Review Letters

Entropy Scaling and Simulability by Matrix Product States

Norbert Schuch, Michael M. Wolf, Frank Verstraete, J. I. Cirac

Published Jan 25, 2008• 407 citations
arXivHTMLPDF

Abstract

We investigate the relation between the scaling of block entropies and the efficient simulability by matrix product states (MPSs) and clarify the connection both for von Neumann and Rényi entropies. Most notably, even states obeying a strict area law for the von Neumann entropy are not necessarily approximable by MPSs. We apply these results to illustrate that quantum computers might outperform classical computers in simulating the time evolution of quantum systems, even for completely translational invariant systems subject to a time-independent Hamiltonian.

DOI
10.1103/physrevlett.100.030504

Related papers

On entropy growth and the hardness of simulating time evolution

Norbert Schuch, Michael M. Wolf, K. G. H. Vollbrecht +1 more

The simulation of quantum systems is a task for which quantum computers are believed to give an exponential speed up as compared with classical ones. While ground states of one-dimensional systems can be efficiently approximated using matrix product states (MPS), their time evolution can encode quantum computations, so that simulating the latter should be hard classically. However, one might believe that for systems with high enough symmetry, and thus insufficient parameters to encode a quantum computation, efficient classical simulation is possible. We discuss supporting evidence to the contrary: we provide a rigorous proof of the observation that a time-independent local Hamiltonian can yield a linear increase of the entropy when acting on a product state in a translational invariant framework. This criterion has to be met by any classical simulation method, which in particular implies that every global approximation of the evolution requires exponential resources for any MPS-based method.

arXiv:0801.2078•New Journal of Physics•Mar 20, 2008•113 citations

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,088 citations

Comparing bipartite entropy growth in open-system matrix-product simulation methods

Guillermo Preisser, David Wellnitz, Thomas Botzung +1 more

The dynamics of one-dimensional quantum many-body systems is often numerically simulated with matrix-product states (MPSs). The computational complexity of MPS methods is known to be related to the growth of entropies of reduced density matrices for bipartitions of the chain. While for closed systems the entropy relevant for the complexity is uniquely defined by the entanglement entropy, for open systems it depends on the choice of the representation. Here, we systematically compare the growth of different entropies relevant to the complexity of matrix-product representations in open-system simulations. We simulate an $XXZ$ spin-1/2 chain in the presence of spontaneous emission and absorption and dephasing. We compare simulations using a representation of the full density matrix as a matrix-product density operator (MPDO) with a quantum trajectory unraveling, where each trajectory is itself represented by an MPS (QT + MPS). We show that the bipartite entropy in the MPDO description (operator entanglement, OE) generally scales more favorably with time than the entropy in QT + MPS (trajectory entanglement, TE): (i) For spontaneous emission and absorption the OE vanishes while the TE grows and reaches a constant value for large dissipative rates and sufficiently long times; (ii) for dephasing the OE exhibits only logarithmic growth while the TE grows polynomially. Although QT + MPS requires a smaller local state space, the more favorable entropy growth can thus make MPDO simulations fundamentally more efficient than QT + MPS. Furthermore, MPDO simulations allow for easier exploitation of higher-order Trotter decompositions and translational invariance, allowing for larger time steps and system sizes.

arXiv:2303.09426•Physical Review A•Jul 18, 2023•18 citations

Area laws and efficient descriptions of quantum many-body states

Yimin Ge, Jens Eisert

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.

New Journal of Physics•Aug 5, 2016•53 citations

Classical Simulability from Operator Entanglement Scaling

Neil Dowling

Local-operator entanglement (LOE) quantifies the nonlocal structure of Heisenberg operators and serves as a diagnostic of many-body chaos. We provide rigorous bounds showing when an operator can be well-approximated by a matrix-product operator (MPO), given asymptotic scaling of its LOE $α$-Rényi entropies. Specifically, we prove that a volume law scaling for $α\geq 1$ implies that the operator cannot be approximated efficiently as an MPO while faithfully reproducing all expectation values. On the other hand, if we restrict to correlations over a relevant sub-class of (ensembles of) states, then logarithmic scaling of the $α< 1$ entropies implies MPO simulability. This result covers a range of relevant quantities, including infinite temperature autocorrelation functions, out-of-time-ordered correlators, and average-case expectation values over ensembles of computational basis states. Beyond this regime, we provide numerical evidence together with a random matrix model to argue that this simulability result also typically holds for arbitrary states. Our results put on firm footing the heuristic expectation that a low operator entanglement implies efficient tensor network representability, extending celebrated foundational results from the theory of matrix-product states and providing a formal link between quantum chaos and classical simulability.

quant-pharXiv:2603.05656•Physical Review A•Mar 9, 2026•0 citations

Area laws and efficient descriptions of quantum many-body states

Yimin Ge, Jens Eisert

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.

arXiv:1411.2995•Nov 11, 2014•5 citations
We investigate the relation between the scaling of block entropies and the efficient simulability by matrix product states (MPSs) and clarify the connection both for von Neumann and Rényi entropies. Most notably, even states obeying a strict area law for the von Neumann entropy are not necessarily approximable by MPSs. We apply these results to illustrate that quantum computers might outperform classical computers in simulating the time evolution of quantum systems, even for completely translational invariant systems subject to a time-independent Hamiltonian.
The simulation of quantum systems is a task for which quantum computers are believed to give an exponential speed up as compared with classical ones. While ground states of one-dimensional systems can be efficiently approximated using matrix product states (MPS), their time evolution can encode quantum computations, so that simulating the latter should be hard classically. However, one might believe that for systems with high enough symmetry, and thus insufficient parameters to encode a quantum computation, efficient classical simulation is possible. We discuss supporting evidence to the contrary: we provide a rigorous proof of the observation that a time-independent local Hamiltonian can yield a linear increase of the entropy when acting on a product state in a translational invariant framework. This criterion has to be met by any classical simulation method, which in particular implies that every global approximation of the evolution requires exponential resources for any MPS-based method.
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 dynamics of one-dimensional quantum many-body systems is often numerically simulated with matrix-product states (MPSs). The computational complexity of MPS methods is known to be related to the growth of entropies of reduced density matrices for bipartitions of the chain. While for closed systems the entropy relevant for the complexity is uniquely defined by the entanglement entropy, for open systems it depends on the choice of the representation. Here, we systematically compare the growth of different entropies relevant to the complexity of matrix-product representations in open-system simulations. We simulate an XXZXXZXXZ spin-1/2 chain in the presence of spontaneous emission and absorption and dephasing. We compare simulations using a representation of the full density matrix as a matrix-product density operator (MPDO) with a quantum trajectory unraveling, where each trajectory is itself represented by an MPS (QT + MPS). We show that the bipartite entropy in the MPDO description (operator entanglement, OE) generally scales more favorably with time than the entropy in QT + MPS (trajectory entanglement, TE): (i) For spontaneous emission and absorption the OE vanishes while the TE grows and reaches a constant value for large dissipative rates and sufficiently long times; (ii) for dephasing the OE exhibits only logarithmic growth while the TE grows polynomially. Although QT + MPS requires a smaller local state space, the more favorable entropy growth can thus make MPDO simulations fundamentally more efficient than QT + MPS. Furthermore, MPDO simulations allow for easier exploitation of higher-order Trotter decompositions and translational invariance, allowing for larger time steps and system sizes.
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.
Local-operator entanglement (LOE) quantifies the nonlocal structure of Heisenberg operators and serves as a diagnostic of many-body chaos. We provide rigorous bounds showing when an operator can be well-approximated by a matrix-product operator (MPO), given asymptotic scaling of its LOE ααα-Rényi entropies. Specifically, we prove that a volume law scaling for α≥1α\geq 1α≥1 implies that the operator cannot be approximated efficiently as an MPO while faithfully reproducing all expectation values. On the other hand, if we restrict to correlations over a relevant sub-class of (ensembles of) states, then logarithmic scaling of the α<1α< 1α<1 entropies implies MPO simulability. This result covers a range of relevant quantities, including infinite temperature autocorrelation functions, out-of-time-ordered correlators, and average-case expectation values over ensembles of computational basis states. Beyond this regime, we provide numerical evidence together with a random matrix model to argue that this simulability result also typically holds for arbitrary states. Our results put on firm footing the heuristic expectation that a low operator entanglement implies efficient tensor network representability, extending celebrated foundational results from the theory of matrix-product states and providing a formal link between quantum chaos and classical simulability.
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.