Eur. Phys. J. Special Topics 224, 75–88 (2015)
https://doi.org/10.1140/epjst/e2015-02344-2

Review

Quantum annealing: The fastest route to quantum computation?

¹ Department of Physics, University of Washington, Seattle, WA 98195, USA
² Perimeter Institute for Theoretical Physics, Waterloo, Ontario N2L 2Y5, Canada
³ Max-Planck-Institut fur Physik komplexer System, 01187 Dresden, Germany
⁴ Physics Department, Princeton University, Princeton, NJ 08542, USA
⁵ Physics Department, Columbia University, New York, NY 10027, USA
⁶ ITS, Graduate Center, City University of New York, New York, NY 10016, USA
⁷ INFN, Sezione di Trieste, Via Valerio 2, 34127 Trieste, Italy
⁸ On leave from Abdus Salam ICTP, Strada Costiera 11, 34151 Trieste, Italy

Received: 30 September 2014
Revised: 16 December 2014
Published online: 5 February 2015

Abstract

In this review we consider the performance of the quantum adiabatic algorithm for the solution of decision problems. We divide the possible failure mechanisms into two sets: small gaps due to quantum phase transitions and small gaps due to avoided crossings inside a phase. We argue that the thermodynamic order of the phase transitions is not predictive of the scaling of the gap with the system size. On the contrary, we also argue that, if the phase surrounding the problem Hamiltonian is a Many-Body Localized (MBL) phase, the gaps are going to be typically exponentially small and that this follows naturally from the existence of local integrals of motion in the MBL phase.