On entropy growth and the hardness of simulating time evolution
arXiv:0801.2078 · doi:10.1088/1367-2630/10/3/033032
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 (7)
- 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
- 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
Cited by in corpus (5)
- Evolution of entanglement entropy following a quantum quench: Analytic results for the XY chain in a transverse magnetic field
- Exploring local quantum many-body relaxation by atoms in optical superlattices
- Density Matrix Renormalization Group in the Heisenberg Picture
- Time evolution of 1D gapless models from a domain-wall initial state: SLE continued?
- The Computational Power of Symmetric Hamiltonians