TY - JOUR

T1 - On entropy growth and the hardness of simulating time evolution

AU - Schuch, N.

AU - Wolf, M. M.

AU - Vollbrecht, K. G.H.

AU - Cirac, J. I.

PY - 2008/3/20

Y1 - 2008/3/20

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=46249129427&partnerID=8YFLogxK

U2 - 10.1088/1367-2630/10/3/033032

DO - 10.1088/1367-2630/10/3/033032

M3 - Article

AN - SCOPUS:46249129427

SN - 1367-2630

VL - 10

JO - New Journal of Physics

JF - New Journal of Physics

M1 - 033032

ER -