Optimization using quantum mechanics: quantum annealing through adiabatic evolution

TLDR

Quantum annealing optimizes by adiabatically evolving a time‑dependent Hamiltonian toward its ground state. The paper reviews recent quantum annealing work and discusses its application to hard optimization problems such as the random Ising model, the travelling salesman problem, and Boolean satisfiability. Quantum annealing is implemented via deterministic Schrödinger evolution for toy models and via path‑integral or Green’s function Monte Carlo for hard optimization problems, illustrated on toy double‑well and disordered one‑dimensional systems. The examples reveal clear differences between classical and quantum annealing, highlighting the crucial role of disorder and non‑trivial Landau–Zener tunnelling.

Abstract

We review here some recent work in the field of quantum annealing, alias adiabatic quantum computation. The idea of quantum annealing is to perform optimization by a quantum adiabatic evolution which tracks the ground state of a suitable time-dependent Hamiltonian, where 'ℏ' is slowly switched off. We illustrate several applications of quantum annealing strategies, starting from textbook toy-models—double-well potentials and other one-dimensional examples, with and without disorder. These examples display in a clear way the crucial differences between classical and quantum annealing. We then discuss applications of quantum annealing to challenging hard optimization problems, such as the random Ising model, the travelling salesman problem and Boolean satisfiability problems. The techniques used to implement quantum annealing are either deterministic Schrödinger's evolutions, for the toy models, or path-integral Monte Carlo and Green's function Monte Carlo approaches, for the hard optimization problems. The crucial role played by disorder and the associated non-trivial Landau–Zener tunnelling phenomena is discussed and emphasized.