Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2016 | Submitted
Book Section - Chapter Open

Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing

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.

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.

Attached Files

Submitted - 1601.03030v1.pdf

Files

1601.03030v1.pdf
Files (449.5 kB)
Name Size Download all
md5:bba81a779b5e0d215e18bf8c7fba9341
449.5 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 19, 2023