Quantum Adiabatic Computation with a Constant Gap Is Not Useful in One Dimension
Open accessAbstract
We show that it is possible to use a classical computer to efficiently simulate the adiabatic evolution of a quantum system in one dimension with a constant spectral gap, starting the adiabatic evolution from a known initial product state. The proof relies on a recently proven area law for such systems, implying the existence of a good matrix product representation of the ground state, combined with an appropriate algorithm to update the matrix product state as the Hamiltonian is changed. This implies that adiabatic evolution with such Hamiltonians is not useful for universal quantum computation. Therefore, adiabatic algorithms which are useful for universal quantum computation either require a spectral gap tending to zero or need to be implemented in more than one dimension (we leave open the question of the computational power of adiabatic simulation with a constant gap in more than one dimension).
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.
Integrity signals
Registry
Cites
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.
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?
The first step toward large-scale QSs with ions was recently achieved.
“The first step toward large-scale QSs with ions was, however, recently achieved [139].”
From Can one trust quantum simulators? (2012) · cites this paper as [139]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
The citation lists haven’t been fetched yet
References 18 · Cited by 22
Research works printed but not linked: 3
- [5]D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, Proc. 45th FOCS , 32, IEEE, 2004.
- [6]D. Aharonov and M. Ben-Or, Proc. 29th STOC , 176, ACM, 1998; A. Kitaev, Russ. Math. Surv. 52 , 1191 (1997); E. Knill, R. Laflamme, and W. Zurek, Proc. R. Soc. Lond. A 454 , 365 (1998).
- [15]F. Verstraete and J. I. Cirac, Phys. Rev. B 73, 094423 (2006).
- Authors
- Hastings, M. B.
- Affiliations
- Microsoft (United States) (US)
- Corresponding author
- Hastings, M. B.
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2009-07-27
- Volume
- 103
- Issue
- 5
- Pages
- 050502-050502
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W1974109128
- Cited by
- 22
- References
- 18
- Citations by year
- 2026: 1 · 2025: 1 · 2021: 2 · 2018: 1 · 2016: 6 · 2015: 2 · 2014: 5 · 2012: 1
- FWCI
- 1.44
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- University of North Texas Digital Library (University of North Texas) (submittedVersion)
- arXiv (Cornell University)
- Funders
- U.S. Department of Energy (DE-AC52-06NA2-5396, AC52-06NA25396)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- one-dimensional quantum systems, classical simulation of quantum computation, area law, matrix product states, ground state representation
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
