Quantum Annealing

In mathematics and applications, quantum annealing (QA) is a general method for finding the global minimum of a given objective function over a given set of candidate solutions (the search space), by a process analogous to quantum fluctuations. It is used mainly for problems where the search space is discrete (combinatorial optimization problems) with many local minima; such as finding the ground states of a glassy system.

In quantum annealing, a "current state" (the current candidate solution) is randomly replaced by a randomly selected neighbor state if the latter has a lower "energy" (value of the objective function). The process is controlled by the "tunneling field strength", a parameter that determines the extent of the neighborhood of states explored by the method (Kadowaki and Nishimori, 1998). The tunneling field starts high, so that the neighborhood extends over the whole search space; and is slowly reduced through the computation (adiabatically; Farhi et al., 2001), until the neighborhood shrinks to those few states that differ minimally from the current states. By that time, the system finds a very deep (hopefully, the global one) minimum and settles there. At the end, we are left with the classical system at its global minimum. Indeed, the possibility of this quantum tunneling across the width of the barriers, instead of scaling their heights (as in classical or simulated annealing), was first pointed out by Ray et al. (1989) in the context of the search of replica symmetry restoration and the consequent advantage in the search of ground state(s) in quantum spin glasses. An experimental demonstration of the success of quantum annealing for random magnets was first reported by Brooke et al. (1999).