On entropy growth and the hardness of simulating time evolution
Authors:
Open Access
- 1 March 2008
- journal article
- Published by IOP Publishing in New Journal of Physics
- Vol. 10 (3)
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.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Simulation of Quantum Many-Body Systems with Strings of Operators and Monte Carlo Tensor ContractionsPhysical Review Letters, 2008
- Entropy Scaling and Simulability by Matrix Product StatesPhysical Review Letters, 2008
- Quantum Simulators, Continuous-Time Automata, and Translationally Invariant SystemsPhysical Review Letters, 2008
- Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systemsPhysical Review A, 2007
- Reversible universal quantum computation within translation-invariant systemsPhysical Review A, 2006
- The density-matrix renormalization groupReviews of Modern Physics, 2005
- Evolution of entanglement entropy in one-dimensional systemsJournal of Statistical Mechanics: Theory and Experiment, 2005
- Efficient Simulation of One-Dimensional Quantum Many-Body SystemsPhysical Review Letters, 2004
- Groundstate properties of a generalized VBS-modelZeitschrift für Physik B Condensed Matter, 1992
- Equivalence and solution of anisotropic spin-1 models and generalized t-J fermion models in one dimensionJournal of Physics A: General Physics, 1991