Obstructions to classically simulating the quantum adiabatic algorithm
The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Abstract
We consider the adiabatic quantum algorithm for systems with ``no sign problem", such as the transverse field Ising model, and analyze the equilibration time for quantum Monte Carlo (QMC) on these systems. We ask: if the spectral gap is only inverse polynomially small, will equilibration methods based on slowly changing the Hamiltonian parameters in the QMC simulation succeed in a polynomial time? We show that this is {\it not} true, by constructing counter-examples. In some examples, the space of configurations where the wavefunction has non-negligible amplitude has a nontrivial fundamental group, causing the space of trajectories in imaginary time to break into disconnected components with only negligible probability outside these components. For the simplest example we give with an abelian fundamental group, QMC does not equilibrate but still solves the optimization problem. More severe effects leading to failure to solve the optimization can occur when the fundamental group is a free group on two generators. Other examples where QMC fails have a {\it trivial} fundamental group, but still use ideas from topology relating group presentations to simplicial complexes. We define gadgets to realize these Hamiltonians as the effective low-energy dynamics of a transverse field Ising model. We present some analytic results on equilibration times which may be of some independent interest in the theory of equilibration of Markov chains. Conversely, we show that a small spectral gap implies slow equilibration at low temperature for some initial conditions and for a natural choice of local QMC updates.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056
Evidence for quantum annealing with more than one hundred qubits
Boixo, S., Rønnow, T. F., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M., & Troyer, M. (2014) · Nature Physics · doi:10.1038/nphys2900 · Cited by 810
Cited by
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Quantum Supremacy through the Quantum Approximate Optimization Algorithm
Farhi, E., & Harrow, A. W. (2016) · arXiv · doi:10.48550/arxiv.1602.07674 · Cited by 331
Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator
Pagano, G., Bapat, A., Becker, P., Collins, K. S., De, A., Hess, P. W., Kaplan, H. B., Kyprianidis, A., Tan, W. L., Baldwin, C., et al. (2020) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2006373117 · Cited by 262
Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing
Albash, T., & Lidar, D. A. (2018) · Physical Review X · doi:10.1103/physrevx.8.031016 · Cited by 238
“The fact that SQAperforms sowell for the logical-planted instance class is in itself a significant and novel finding about the class of logical-planted problem instances, since one might reasonably expect that as hardware quantum annealers continue to improve, SQA will become a lower bound on the performance of such h…”
BackgroundAdiabatic optimization versus diffusion Monte Carlo methods
Jarret, M., Jordan, S. P., & Lackey, B. (2016) · Physical Review A · doi:10.1103/physreva.94.042318 · Cited by 36
Metadata
- Authors
- Hastings, M. B.
- Venue
- Quantum Information and Computation
- Publisher
- Rinton Press
- Published
- 2013-11
- Volume
- 13
- Issue
- 11&12
- Pages
- 1038-1076
- ISSN
- 1533-7146 (ISSN-L)
- OpenAlex
- W2949480312
- Cited by
- 32
- References
- 2
- FWCI
- 3.31
- Type
- journal article
- Language
- en
- Open access
- closed
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Obstructions to classically simulating the quantum adiabatic algorithm. https://app.cochat.ai/papers/10.26421/qic13.11-12-8
- The paper
- Hastings, M. B. (2013). Obstructions to classically simulating the quantum adiabatic algorithm. Quantum Information and Computation. https://doi.org/10.26421/qic13.11-12-8
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.