APS March Meeting 2016
Volume 61, Number 2
Monday–Friday, March 14–18, 2016;
Baltimore, Maryland
Session B13: Adiabatic Quantum Computation and Quantum Annealing
11:15 AM–2:15 PM,
Monday, March 14, 2016
Room: 309
Sponsoring
Unit:
GQI
Chair: Tameem Albash, Univ of Southern California
Abstract ID: BAPS.2016.MAR.B13.1
Abstract: B13.00001 : Simulated annealing versus quantum annealing
11:15 AM–11:51 AM
Preview Abstract
View Presentation
Abstract
Author:
Matthias Troyer
(ETH Zurich)
Based on simulated classical annealing and simulated quantum annealing using quantum Monte Carlo (QMC) simulations I will explore the question where physical or simulated quantum annealers may outperform classical optimization algorithms. Although the stochastic dynamics of QMC simulations is not the same as the unitary dynamics of a quantum system, I will first show that for the problem of quantum tunneling between two local minima both QMC simulations and a physical system exhibit the same scaling of tunneling times with barrier height. The scaling in both cases is $O(\Delta^2)$, where $\Delta$ is the tunneling splitting. An important consequence is that QMC simulations can be used to predict the performance of a quantum annealer for tunneling through a barrier. Furthermore, by using open instead of periodic boundary conditions in imaginary time, equivalent to a projector QMC algorithm, one obtains a quadratic speedup for QMC, and achieve linear scaling in $\Delta$ [1]. I will then address the apparent contradiction between experiments on a D-Wave 2 system that failed to see evidence of quantum speedup [2] and previous QMC results [3] that indicated an advantage of quantum annealing over classical annealing for spin glasses. We find that this contradiction is resolved by taking the continuous time limit in the QMC simulations which then agree with the experimentally observed behavior and show no speedup for 2D spin glasses. However, QMC simulations with large time steps gain further advantage: they ``cheat” by ignoring what happens during a (large) time step, and can thus outperform both simulated quantum annealers and classical annealers [4].
I will then address the question how to optimally run a simulated or physical quantum annealer. Investigating the behavior of the tails of the distribution of runtimes for very hard instances we find that adiabatically slow annealing is far from optimal. On the contrary, many repeated relatively fast annealing runs can be orders of magnitude faster for hard sin glass problems. The intuitive explanation is that hard instances, which are stuck in the “wrong” minimum can be solved faster by perturbing them [5]. I will finally discuss the consequences of these findings for designing better quantum annealers.
[1] S.V. Isakov, G. Mazzola, V.N. Smelyanskiy, Z. Jiang, S. Boixo, H. Neven, and M. Troyer, arXiv:1510.08057.
[2] T.F. R{\o}nnow, Z. Wang, J. Job, S. Boixo, S.V. Isakov, D. Wecker, J.M. Martinis, D.A. Lidar, M. Troyer, Science {\bf 345}, 420 (2014).
[3] G.E. Santoro, R. Martonak, E. Tosatti, and R. Car, Science {\bf 295}, 2427 (2002).
[4] B. Heim, T. F. R{\o}nnow, S. V. Isakov, and M. Troyer, Science {\bf 348}, 215 (2015)
(2015).
[5] D.S. Steiger, T.F. R{\o}nnow, M. Troyer, Phys. Rev. Lett. (in press); arXiv:1504.07991
To cite this abstract, use the following reference: http://meetings.aps.org/link/BAPS.2016.MAR.B13.1