Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing
Open accessThe DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Abstract
Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width nζ and height nαfor ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.
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
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339 · cited 1×
“A particularly compelling heuristic proposal for optimization problems is quantum annealing (QA), also known as quantum adiabatic optimization [3], [4] (in this work we use the term “quantum annealing” to mean adiabatic optimization in thermal equilibrium at a low but non-zero temperature, though in some other context…”
MethodMarkov Chains and Mixing Times
Levin, D., Peres, Y., & Wilmer, E. (2008) · doi:10.1090/mbk/058 · Cited by 2,241
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 1×
“Studies comparing QA to SA and SQA have also emerged since [18] found the success probabilities of SQA are highly correlated with the results of QA performed on D-Wave quantum hardware with hundreds of qubits, while the distribution of success probabilities for SA on the same set of instances bears little resemblance…”
ResultWhat is the Computational Value of Finite-Range Tunneling?
Denchev, V. S., Boixo, S., Isakov, S. V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., & Neven, H. (2016) · Physical Review X · doi:10.1103/physrevx.6.031015 · Cited by 399 · cited 1×
“More recently, the performance of QA, SQA, and SA was empirically compared on an ensemble of spin glass instances with were designed to have tall, thin barriers [19], as a step towards understanding the kinds of instances for which QA has an advantage over SA.”
BackgroundThe quantum adiabatic optimization algorithm and local minima
Reichardt, B. W. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007428 · Cited by 110 · cited 5×
“In contrast, for any α+ζ < 1/2 it can be shown that QA finds the global minimum with high probability in time O(n) [2], showing that an exponential separation in the perfomance of SA and QA is possible.”
BackgroundMethodResultInfluentialHow "Quantum" is the D-Wave Machine?
Shin, S. W., Smith, G., Smolin, J. A., & Vazirani, U. (2014) · arXiv · doi:10.48550/arxiv.1401.7087 · Cited by 89
Classical signature of quantum annealing
Smolin, J. A., & Smith, G. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00052 · Cited by 79 · cited 1×
“Another classical algorithm which has been compared with QA is spin vector dynamics (SVD), which approximates the state of the system by a collection of classical spin vectors, which are updated through either a nonlinear system of differential equations [20] or with Monte Carlo updates [21].”
MethodAdiabatic 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
Spectral-gap analysis for efficient tunneling in quantum adiabatic optimization
Brady, L. T., & van Dam, W. (2016) · Physical Review A · doi:10.1103/physreva.94.032309 · Cited by 17 · cited 2×
“We remark that the spike and related objective functions have the subject of recent analytic work [23], [24], and that there have also been numerical studies of SQA [25], [26], with findings that are consistent with our main result.”
BackgroundResult
Cited by
Machine learning & artificial intelligence in the quantum domain: a review of recent progress
Dunjko, V., & Briegel, H. J. (2018) · Reports on Progress in Physics · doi:10.1088/1361-6633/aab406 · Cited by 1,055
Ising machines as hardware solvers of combinatorial optimization problems
Mohseni, N., McMahon, P. L., & Byrnes, T. (2022) · Nature Reviews Physics · doi:10.1038/s42254-022-00440-8 · Cited by 543
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518
Li, R. Y., Di Felice, R., Rohs, R., & Lidar, D. A. (2018) · npj Quantum Information · doi:10.1038/s41534-018-0060-8 · Cited by 202
“SQA is a (classical) path integral Monte Carlo method that has performed very similarly to quantum annealing and captures some of its main advantages [53].”
MethodBenchmarking Quantum Annealing Controls with Portfolio Optimization
Grant, E., Humble, T. S., & Stump, B. (2021) · Physical Review Applied · doi:10.1103/physrevapplied.15.014012 · Cited by 90
Metadata
- Authors
- Crosson, E., & Harrow, A. W.
- Venue
- 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
- Publisher
- IEEE
- Published
- 2016-10
- Pages
- 714-723
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2238514032
- Cited by
- 76
- References
- 9
- FWCI
- 3.27
- Type
- conference paper
- Language
- en
- Open access
- green
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: Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing. https://app.cochat.ai/papers/10.1109/focs.2016.81
- The paper
- Crosson, E., & Harrow, A. W. (2016). Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). https://doi.org/10.1109/focs.2016.81
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.