![]()
QUANTUM ANNEALING:
FROM VIEWPOINTS OF STATISTICAL PHYSICS,
CONDENSED MATTER PHYSICS,
AND COMPUTATIONAL PHYSICS
SHU TANAKA
Department of Chemistry, University of Tokyo,
7-3-1, Hongo, Bunkyo-ku, Tokyo, 113-0033, JapanE-mail: [email protected] RYO TAMURA
Institute for Solid State Physics, University of Tokyo,
5-1-5, Kashiwanoha, Kashiwa-shi, Chiba, 277-8501, Japan
International Center for Young Scientists,
National Institute for Materials Science,
1-2-1, Sengen, Tsukuba-shi, Ibaraki, 305-0047, JapanE-mail: [email protected] In this paper, we review some features of quantum annealing and related topics from viewpoints of statistical physics, condensed matter physics, and computational physics. We can obtain a better solution of optimization problems in many cases by using the quantum annealing. Actually the efficiency of the quantum annealing has been demonstrated for problems based on statistical physics. Then the quantum annealing has been expected to be an efficient and generic solver of optimization problems. Since many implementation methods of the quantum annealing have been developed and will be proposed in the future, theoretical frameworks of wide area of science and experimental technologies will be evolved through studies of the quantum annealing.
Keywords: Quantum annealing; Quantum information; Ising model; Optimization problem
1. Introduction
Optimization problems are present almost everywhere, for example, designing of integrated circuit, staff assignment, and selection of a mode of transportation. To find the best solution of optimization problems is difficult in general. Then, it is a significant issue to propose and to develop a method for obtaining the best solution (or a better solution) of optimization problems in information science. In order to obtain the best solution, a couple of algorithms according to type of optimization problems have been formulated in information science and these methods have yielded practical applications. Furthermore, since optimization problem is to find the state where a real-valued function takes the minimum value, it can be regarded as problem to obtain the ground state of the corresponding Hamiltonian. Thus, if we can map optimization problem to well-defined Hamiltonian, we can use knowledge and methodologies of physics. Actually, in computational physics, generic and powerful algorithms which can be adopted for wide application have been proposed. One of famous methods is simulated annealing which was proposed by Kirkpatrick et al.1,2 In the simulated annealing, we introduce a temperature (thermal fluctuation) in the considered optimization problems. We can obtain a better solution of the optimization problem by decreasing temperature gradually since thermal fluctuation effect facilitates transition between states. It is guaranteed that we can obtain the best solution definitely if we decrease temperature slow enough.3 Then, the simulated annealing has been used in many cases because of easy implementation and guaranty.
The quantum annealing was proposed as an alternative method of the simulated annealing.4–11 In the quantum annealing, we introduce a quantum field which is appropriate for the considered Hamiltonian. For instance, if the considered optimization problem can be mapped onto the Ising model, the simplest form of the quantum fluctuation is transverse field. In the quantum annealing, we gradually decrease quantum field (quantum fluctuation) instead of temperature (thermal fluctuation). The efficiency of the quantum annealing has been demonstrated by a number of researchers, and it has been reported that a better solution can be obtained by the quantum annealing comparison with the simulated annealing in many cases. Figure 1 shows schematic picture of the simulated annealin...
