Quantum annealing of disordered spin systems

Quantum annealing is a general purpose optimization algorithm, whose goal is to find the ground state of a given "problem" Hamiltonian. This is accomplished by starting from the ground state of a simple Hamiltonian and slowly deforming the Hamiltonian to the one of interest. If this is carried out adiabatically, the system will end up in the desired ground state. For a broad class of hard optimization problems it is known that the minimal gap between the ground state and the first excited state is exponentially small in the system size, and passing this gap adiabatically is unfeasible for large systems. However, even if the quantum state at the end of an annealing protocol is not the desired ground state but a superposition of not-too-highly excited states, it might still give a useful approximation to the solution of the original optimization problem. In our work, we investigate how good of an approximation one can expect to get. We build on recent advances in the understanding of the structure of excited states and the spectral properties of disordered spin systems (i.e., random optimization problems). In particular, we show that the two generic paradigms of ergodic and many-body localized phases entail surprisingly different behavior under quantum annealing.