Cited by 113Quantum many-body systemsQuantum Computing Algorithms and ArchitectureQuantum Information and Cryptography

On entropy growth and the hardness of simulating time evolution

Open access
Schuch, N, Wolf, M M, Vollbrecht, K G H, Cirac, J I·2008·New Journal of Physics

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1088/1367-2630/10/3/033032

Cites

39 of 39 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • According to the Lieb-Robinson theorem, after a sufficiently large time, states can become strongly entangled.

    “Indeed, this fact is related to correlation and entanglement spreading according to the Lieb-Robinson theorem that states that, after a sufficiently large time, states can become strongly entangled ([91-96], see also [97]).”

    From Can one trust quantum simulators? (2012) · cites this paper as [94]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 3

  1. Latorre J I, Rico E and Vidal G 2004 Quantum Inf. Comput. 4 48 (Preprint quant-ph/0304098) · arXiv
  2. Fannes M, Haegeman B and Mosonyi M 2003 Preprint math-ph/0306055 · arXiv
  3. Bravyi S, DiVincenzo D and Loss D 2007 Preprint 0707.1894

Cited by

Sorted by citations

Authors
Schuch, N., Wolf, M. M., Vollbrecht, K. G. H., & Cirac, J. I.
Affiliations
Max Planck Society (DE)
Venue
New Journal of Physics
Published
2008-03-20
Volume
10
Issue
3
Pages
033032
ISSN
1367-2630 (ISSN-L)
OpenAlex
W1970054335
Cited by
113
References
36
Citations by year
2026: 5 · 2025: 11 · 2024: 6 · 2023: 8 · 2022: 4 · 2021: 11 · 2020: 13 · 2019: 10 · 2018: 9 · 2017: 2 · 2016: 2 · 2015: 4 · 2014: 4 · 2013: 2 · 2012: 2
FWCI
3.86
Type
journal article
Language
en
Open access
Licence
cc-by
Locations
  • New Journal of Physics (publishedVersion, cc-by)
  • arXiv (Cornell University) (publishedVersion)
  • Max Planck Institute for Plasma Physics (submittedVersion)
  • MPG.PuRe (Max Planck Society) (submittedVersion, cc-by)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
entropy increase, classical simulation of quantum dynamics, quantum advantage, matrix product states, local Hamiltonians, translation invariance, product states, ground state, one-dimensional systems

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review