On entropy growth and the hardness of simulating time evolution

Abstract

The simulation of quantum systems is a task for which quantum computers are believed to give an exponential speedup as compared to 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.

15 pages. v2: Published version, Journal-Ref. added

References in corpus (19)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• The density-matrix renormalization group
• Efficient simulation of one-dimensional quantum many-body systems
• Improved Simulation of Stabilizer Circuits
• Evolution of Entanglement Entropy in One-Dimensional Systems
• An Area Law for One Dimensional Quantum Systems
• Effective quantum spin systems with ion traps
• Violation of the entropic area law for Fermions
• Exact relaxation in a class of non-equilibrium quantum lattice systems
• Entropy scaling and simulability by Matrix Product States
• A Sharp Fannes-type Inequality for the von Neumann Entropy
• Spin-spin interaction and spin-squeezing in an optical lattice
• Entropy and Entanglement in Quantum Ground States
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Strings, Projected Entangled Pair States, and variational Monte Carlo methods
• Quantum simulators, continuous-time automata, and translationally invariant systems
• Quantum computation via translation-invariant operations on a chain of qubits
• Reversible universal quantum computation within translation invariant systems
• A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems

Cited by in corpus (84)

• Area laws for the entanglement entropy - a review
• Entanglement entropy and conformal field theory
• Quantum many-body systems out of equilibrium
• Equilibration, thermalisation, and the emergence of statistical mechanics in closed quantum systems
• Quantum trajectories and open many-body quantum systems
• Measuring entanglement growth in quench dynamics of bosons in an optical lattice
• Quantum quenches in 1+1 dimensional conformal field theories
• Evolution of entanglement entropy following a quantum quench: Analytic results for the XY chain in a transverse magnetic field
• Can One Trust Quantum Simulators?
• Holographic Evolution of Entanglement Entropy
• Entanglement dynamics after quantum quenches in generic integrable systems
• Quantum discord and its allies: a review
• Scalable error mitigation for noisy quantum circuits produces competitive expectation values
• Entanglement spreading in a minimal model of maximal many-body quantum chaos
• Review on novel methods for lattice gauge theories
• Instantaneous Quantum Computation
• A short review on entanglement in quantum spin systems
• Exploring local quantum many-body relaxation by atoms in optical superlattices
• Quasiparticle dynamics of symmetry resolved entanglement after a quench: the examples of conformal field theories and free fermions
• Probing local relaxation of cold atoms in optical superlattices
• Entanglement evolution and generalised hydrodynamics: interacting integrable systems
• Quantum East model: localization, non-thermal eigenstates and slow dynamics
• Density Matrix Renormalization Group in the Heisenberg Picture
• Probing the anomalous dynamical phase in long-range quantum spin chains through Fisher-zero lines
• Quantum information dynamics in multipartite integrable systems
• Breaking the entanglement barrier: Tensor network simulation of quantum transport
• Time evolution of many-body localized systems in two spatial dimensions
• Time evolution of 1D gapless models from a domain-wall initial state: SLE continued?
• Time Evolution within a Comoving Window: Scaling of signal fronts and magnetization plateaus after a local quench in quantum spin chains
• Entangling power and quantum circuit complexity
• Quantum metrology for the Ising Hamiltonian with transverse magnetic field
• Supersonic quantum communication
• Exact matrix product solutions in the Heisenberg picture of an open quantum spin chain
• Lieb-Robinson bounds and the simulation of time evolution of local observables in lattice systems
• Towards a Generalized Hydrodynamics description of Rényi entropies in integrable systems
• Spreading of entanglement and correlations after a quench with intertwined quasiparticles
• Dynamical simulation of integrable and non-integrable models in the Heisenberg picture
• Entanglement and diagonal entropies after a quench with no pair structure
• Rényi entropies of generic thermodynamic macrostates in integrable systems
• Quantum time crystals with programmable disorder in higher dimensions
• Towards experimental quantum field tomography with ultracold atoms
• Measurement of Identical Particle Entanglement and the Influence of Antisymmetrisation
• Open System Tensor Networks and Kramers' Crossover for Quantum Transport
• Dynamical manifestation of Gibbs paradox after a quantum quench
• Concatenated tensor network states
• Growth of entanglement of generic states under dual-unitary dynamics
• Electron Dynamics with the Time-Dependent Density Matrix Renormalization Group
• How much entanglement is needed to reduce the energy variance?
• Entanglement measures of bipartite quantum gates and their thermalization under arbitrary interaction strength
• A beginner's guide to non-abelian iPEPS for correlated fermions
• Prethermalisation and Thermalisation in the Entanglement Dynamics
• The Computational Power of Symmetric Hamiltonians
• Efficient Large-Scale Many-Body Quantum Dynamics via Local-Information Time Evolution
• Condensed Matter Applications of Entanglement Theory
• Probing non-equilibrium topological order on a quantum processor
• Approximating the long time average of the density operator: Diagonal ensemble
• Converting long-range entanglement into mixture: tensor-network approach to local equilibration
• Boundary Chaos: Exact Entanglement Dynamics
• Rényi entanglement entropies for the compactified massless boson with open boundary conditions
• Tensor network methods with graph enhancement
• Particle number conservation in quantum many-body simulations with matrix product operators
• Quantum spin helices more stable than the ground state: onset of helical protection
• Complexity-constrained quantum thermodynamics
• Entanglement bounds on the performance of quantum computing architectures
• Gaussian-state Ansatz for the non-equilibrium dynamics of quantum spin lattices
• Partonic distribution functions and amplitudes using tensor network methods
• Quantum Complexity: restrictions on algorithms and architectures
• Quasi-particle spectrum and entanglement generation after a quench in the quantum Potts spin chain
• Introduction to quantum entanglement in many-body systems
• The dynamical $\alpha$-Rényi entropies of local Hamiltonians grow at most linearly in time
• Parameterized Hamiltonian simulation using quantum optimal control
• Wavefunction branching: when you can't tell pure states from mixed states
• Tensor networks and efficient descriptions of classical data
• Large-scale stochastic simulation of open quantum systems
• Dynamical quantum phase transition and thermal equilibrium in the lattice Thirring model
• Breaking global symmetries with locality-preserving operations
• Exact quench dynamics of symmetry resolved entanglement in a free fermion chain
• Gaining confidence on the correct realization of arbitrary quantum computations
• Preparation Circuits for Matrix Product States by Classical Variational Disentanglement
• Ab-Initio Approach to Many-Body Quantum Spin Dynamics
• Matrix product state simulations of quantum quenches and transport in Coulomb blockaded superconducting devices
• Harnessing Quantum Dynamics for Robust and Scalable Quantum Extreme Learning Machines
• Dynamics of charge-imbalance-resolved entanglement negativity after a quench in a free-fermion model
• Solving Sharp Bounded-error Quantum Polynomial Time Problem by Evolution methods