Quantum versus classical annealing of Ising spin glasses

See allHide authors and affiliations

Science  10 Apr 2015:
Vol. 348, Issue 6231, pp. 215-217
DOI: 10.1126/science.aaa4170

Benchmarking quantum simulation

Finding a solution to a problem often amounts to an optimization problem and thus can be recast in terms of the lowest-energy state of a system. To find such ground states, mathematical methods based on annealing were developed. To reach the ground state more quickly than with the earlier classical methods, a quantum-mechanical approach was proposed; however, the evidence for quantum speed-up is contradictory. Heim et al. show that the results depend on how the problem is described and how the optimization routine is implemented. This development should be valuable for benchmarking quantum machines.

Science, this issue p. 215


Quantum annealers use quantum fluctuations to escape local minima and find low-energy configurations of a physical system. Strong evidence for superiority of quantum annealing (QA) has come from comparing QA implemented through quantum Monte Carlo (QMC) simulations to classical annealing. Motivated by recent experiments, we revisit the question of when quantum speedup may be expected. Although a better scaling is seen for QA in two-dimensional Ising spin glasses, this advantage is due to time discretization artifacts and measurements that are not possible on a physical quantum annealer. Simulations in the physically relevant continuous time limit, on the other hand, do not show superiority. Our results imply that care must be taken when using QMC simulations to assess the potential for quantum speedup.

View Full Text