# Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing

arXiv: https://arxiv.org/abs/1601.03030 · HTML: https://mlsanity.com/paper/1601.03030/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jan 2016.

## Built on by (most cited first, 11 of 11)

- [Recent Advances for Quantum Neural Networks in Generative Learning](https://mlsanity.com/paper/2206.03066/) (2022)
- [The Complexity of NISQ](https://mlsanity.com/paper/2210.07234/) (2022)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Quantum-enhanced Computer Vision: Going Beyond Classical Algorithms](https://mlsanity.com/paper/2510.07317/) (2025)
- [Financial Risk Management on a Neutral Atom Quantum Processor](https://mlsanity.com/paper/2212.03223/) (2022)
- [Towards Transfer Learning for Large-Scale Image Classification Using Annealing-based Quantum Boltzmann Machines](https://mlsanity.com/paper/2311.15966/) (2023)
- [Physics-inspired Generative AI models via real hardware-based noisy quantum diffusion](https://mlsanity.com/paper/2505.22193/) (2025)
- [Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing](https://mlsanity.com/paper/2301.05146/) (2023)
- [Transfer Learning for Deep-Unfolded Combinatorial Optimization Solver with Quantum Annealer](https://mlsanity.com/paper/2501.03518/) (2025)
- [Performance Analysis of Convolutional Neural Network By Applying Unconstrained Binary Quadratic Programming](https://mlsanity.com/paper/2506.00247/) (2025)
- [Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization](https://mlsanity.com/paper/2601.17570/) (2026)

## Abstract (arXiv)

Simulated Quantum Annealing (SQA) is a Markov Chain Monte-Carlo algorithm that samples the equilibrium thermal state of a Quantum Annealing (QA) Hamiltonian. In addition to simulating quantum systems, SQA has also been proposed as another physics-inspired classical algorithm for combinatorial optimization, alongside classical simulated annealing. However, in many cases it remains an open challenge to determine the performance of both QA and SQA. One piece of evidence for the strength of QA over classical simulated annealing comes from an example by Farhi, Goldstone and Gutmann . There a bit-symmetric cost function with a thin, high energy barrier was designed to show an exponential seperation between classical simulated annealing, for which thermal fluctuations take exponential time to climb the barrier, and quantum annealing which passes through the barrier and reaches the global minimum in poly time, arguably by taking advantage of quantum tunneling. In this work we apply a comparison method to rigorously show that the Markov chain underlying SQA efficiently samples the target distribution and finds the global minimum of this spike cost function in polynomial time. Our work provides evidence for the growing consensus that SQA inherits at least some of the advantages of tunneling in QA, and so QA is unlikely to achieve exponential speedups over classical computing solely by the use of quantum tunneling. Since we analyze only a particular model this evidence is not decisive. However, techniques applied here---including warm starts from the adiabatic path and the use of the quantum ground state probability distribution to understand the stationary distribution of SQA---may be valuable for future studies of the performance of SQA on cost functions for which QA is efficient.