A Caltech Library Service

Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing

Crosson, Elizabeth and Harrow, Aram W. (2016) Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing. In: IEEE 57th Annual Symposium on Foundations of Computer Science. IEEE , Piscataway, NJ, pp. 714-723. ISBN 978-1-5090-1838-3.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2016 IEEE. We thank Dave Bacon, Wim van Dam and Alistair Sinclair for helpful conversations. Elizabeth Crosson gratefully acknowledges funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028), and is also grateful for support received while completing a portion of this work at the MIT Center for Theoretical Physics with funding from NSF grant number CCF-1111382. Aram Harrow was funded by NSF grants CCF-1111382 and CCF-1452616 and ARO contract W911NF-12-1-0486.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Gordon and Betty Moore FoundationGBMF-12500028
Army Research Office (ARO)W911NF-12-1-0486
Record Number:CaltechAUTHORS:20160622-152913947
Persistent URL:
Official Citation:E. Crosson and A. W. Harrow, "Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing," 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), New Brunswick, NJ, 2016, pp. 714-723. doi: 10.1109/FOCS.2016.81 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:68611
Deposited By: Jacquelyn O'Sullivan
Deposited On:27 Jun 2016 17:10
Last Modified:11 Nov 2021 04:02

Repository Staff Only: item control page