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) $s$ is randomly replaced by a randomly selected "neighbor state" $s\text{'}$ if the latter has a lower "energy" (value of the objective function). The process is controlled by the "tunneling field strength"$T$, a parameter that determines the extent of the neighborhood of states explored by the method. The tunneling field starts high, so that the neighborhood extends over the whole search space; and is slowly reduced through the computation, until the neighborhood shrinks to those few states that differ minimally from the current states.

Comparison to simulated annealing

Quantum annealing can be compared to simulated annealing (SA), whose "temperature" parameter plays a similar role to QA's tunneling field strength. However, in SA the neighborhood stays the same throughout the search, and the temperature determines the probability of moving to a state of higher "energy". In QA, the tunneling field strength determines instead the neighborhood radius, i.e. the mean distance between the next candidate $s\text{'}$ and the current candidate $s$.

In more elaborated SA variants (such as Adaptive simulated annealing), the neighbouhood radius is also varied using acceptance rate percentages or the temperature value.

Quantum mechanics analogy

The tunneling field is basically a kinetic energy term that does not commute with the classical potential energy part of the original glass. The whole process can be simulated in a computer using quantum Monte Carlo (or other stochastic technique), and thus obtain a heuristic algorithm for finding the ground state of the classical glass. It is speculated that in a quantum computer, such simulations would be much more efficient and exact than that done in a classical computer, due to "quantum parallelism" realized by the actual superposition of all the classical configurations at any instant.

By that time, the system finds a very deep (likely, the global one) minimum and settle there. At the end, we are left with the classical system at its global minimum.

In the case of annealing a purely mathematical "objective function", one may consider the variables in the problem to be classical degrees of freedom, and the cost functions to be the potential energy function (classical Hamiltonian). Then a suitable term consisting of non-commuting variable(s) (i.e. variables that has non-zero commutator with the variables of the original mathematical problem) has to be introduced artificially in the Hamiltonian to play the role of the tunneling field (kinetic part). Then one may carry out the simulation with the quantum Hamiltonian thus constructed (the original function + non-commuting part) just as described above. Here, there is a choice in selecting the non-commuting term and the efficiency of annealing may depend on that.

It has been demonstrated experimentally as well as theoretically, that quantum annealing can indeed out rate thermal annealing in certain cases, specially, where the potential energy (cost) landscape consists of very high but thin barriers surrounding shallow local minima. Since thermal transition probabilities (~$exp\{(-Delta/k\_\{B\}T)\}$; $T$ => Temperature, $k\_\{B\}$ => Boltzmann constant) depend only on the height $Delta$ of the barriers, it is very difficult for thermal fluctuations to get the system out from such local minima. But quantum tunneling probabilities through a barrier depend not only the height $Delta$ of the barrier, but also on its width $w$; if the barriers are thin enough, quantum fluctuations may bring the system out of the shallow local minima surrounded by them.

References

*T. Kadowaki and H. Nishimori, Phys. Rev. E 58 5355 (1998)
*E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Ludgren and D. Preda, Science 292 472 (2001)
*G. E. Santoro and E. Tosatti, J. Phys. A 39 R393 (2006)
*A. Das and B. K. Chakrabarti, Rev. Mod. Phys. 80 1061 (2008)
*Apolloni B., C. Caravalho, D. De Falco "Quantum stochastic optimization", Stochastic Processes and their Applications, 33, 233-244 (1989).
* Arnab Das and Bikas K. Chakrabarti (Eds.), "Quantum Annealing and Related Optimization Methods", Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)