On entropy growth and the hardness of simulating time evolution
On entropy growth and the hardness of simulating time evolution
复制标题
论熵增长与模拟时间演化的难度
DOI：
10.1088/1367-2630/10/3/033032
复制
发表时间：
2008
影响因子：
3.3
通讯作者：
J. Cirac
中科院分区：
文献类型：
--
作者：
N. Schuch;M. Wolf;K. Vollbrecht;J. Cirac
量子系统的模拟是一项任务，量子计算机被认为比经典计算机具有指数级的速度。虽然一维系统的基态可以用矩阵乘积态(MPS)有效地近似，但它们的时间演化可以编码量子计算，因此很难经典地模拟后者。然而，人们可能相信，对于具有足够高对称性的系统，因此没有足够的参数来编码量子计算，高效的经典模拟是可能的。我们讨论了相反的证据：我们提供了一个严格的证据，证明了当作用于平移不变框架中的乘积态时，与时间无关的局域哈密顿量可以产生熵的线性增加。任何经典的模拟方法都必须满足这一标准，这特别意味着对于任何基于MPS的方法，进化的每个全局近似都需要指数级的资源。
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.