Article of Masayuki Ohzeki Kyoto University

Simulated Annealing/ Book 2

Optimization by use of nature in physics beyond classical simulated annealing
InTech- ISBN 980-953-307-447-9
Masayuki Ohzeki


In this chapter, we would like to review the original method in short and alternatives of simulated annealing in context of statistical physics.
The simulated annealing introduces and exploits artificial degrees of freedom to drive the system inspired by statistical mechanics, namely the thermal fluctuations.
The original version of the technique, one simulates the stochastic dynamics of the system and drive it for a sufficiently long time.
To realize speed up of the simulated annealing, we simultaneously drive a number of systems and take their average to evaluate the correct behavior in the stochastic dynamics.
If we take a special biased average during the process, we can reproduce the results in the satisfactory level as given by the original simulated annealing without driving the system for such a long time.
We show an essential idea of such an alternative with parallel computation.

Instead of usage of the thermal fluctuations, its quantum version can be implemented to search for the desired state corresponding to the optimum of the optimization problem.
That is the quantum annealing.
In order to introduce another direction of the development associated with the simulated annealing, we explain how to perform the quantum annealing and consider its improvements according to several theories in statistical mechanics.

LinkIconSimulated Annealing - Advances, Applications and Hybridizations

Kindai Lecture Note Series

Lectures on Quantum Computing, Thermodynamics and Statistical Physics
Masayuki Ohzeki


In this chapter, we show two fascinating topics lying between quantum information processing and statistical mechanics.
First, we introduce an elaborated technique, the surface code, to prepare the particular quantum state with robustness against decoherence. Interestingly, the theoretical limitation of the surface code, accuracy threshold, to restore the quantum state has a close connection with the problem on the phase transition in a
special model known as spin glasses, which is one of the most activeresearches in statistical mechanics. The phase transition in spin glasses is an intractable problem, since we must strive many-body system with complicated interactions with change of their signs depending on the distance between spins. Fortunately, recent progress in spin-glass theory enables us to predict the precise location of the critical point, at which the phase transition occurs. It means that statistical mechanics is available for revealing one of the most interesting parts in quantum information processing. We show how to import the special tool in statistical mechanics into the problem on the accuracy threshold in quantum computation.

Second, we show another interesting technique to employ quantum nature, quantum annealing. The purpose of quantum annealing is to search for the most favored solution of a multivariable function, namely optimization problem. The most typical instance is the traveling salesman problem to find the minimum tour while visiting all the cities. In quantum annealing, we introduce quantum fluctuation to drive a particular system with the artificial Hamiltonian, in which the ground state represents the optimal solution of the specific problem we desire to solve. Induction of the
quantum fluctuation gives rise to the quantum tunneling effect, which allows nontrivial hopping from state to state. We then sketch a strategy to control the quantum fluctuation efficiently reaching the ground state. Such a generic framework is called quantum annealing. The most typical instance is quantum adiabatic computation based on the adiabatic theorem. The quantum adiabatic computation as discussed in the other chapter, unfortunately, has a crucial bottleneck for a part of the optimization problems. We here introduce several recent trials to overcome such a weakpoint by use of developments in statistical mechanics.

Through both of the topics, we would shed light on the birth of the interdisciplinary field between quantum mechanics and statistical mechanics.

article: LinkIconarXiv:1204.2865