Quantum annealing
From Wikipedia, the free encyclopedia
In mathematics and applications, quantum annealing is a method for finding solutions to combinatorial optimization problems and ground states of glassy systems using quantum fluctuations.
Unlike simulated annealing, which employs the strategy of slow cooling (physically, or in simulation) to find the ground state of glassy systems (physical glass with a rugged potential energy landscape or a mathematical objective function with many local minima), Quantum annealing is basically annealing of glassy systems down to their global minimum (at least to a good approximation) using quantum fluctuations instead of thermal ones.
Quantum fluctuations are introduced in a physical system by applying a tunneling field that mixes the configurations (classical) of the glass, and allows the system to traverse the configuration space to seek the global minimum of the potential energy landscape. The tunneling field is kept high enough at the beginning (so that the system effectively get delocalized over the whole configuration space) and slowly reduced with time until finally it is muted completely. 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. 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.
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( − Δ / kBT); T => Temperature, kB => Boltzmann constant) depend only on the height Δ of the barriers, it is very difficult for thermal flutuations to get the system out from such local minima. But quantum tunneling probabilities through a barrier depend not only the height Δ 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.
[edit] References
- Arnab Das and Bikas K. Chakrabarti (Eds.), Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005).
