Quantum Annealing by Hidetoshi Nishimori

Executive Summary Introduction Formulation Strengths and Weaknesses Further Readings

Executive Summary

  • Quantum annealing is a quantum-mechanical metaheuristic (generic and approximate method) to solve combinatorial optimization and sampling problems. It was proposed by Kadowaki and Nishimori in 1998 in the form now widely used.

  • Many problems of practical importance can be formulated as combinatorial optimization, and the development of efficient methods to solve combinatorial optimization problems has enormous practical significance.

  • Also of recent focus of research activities are to use quantum annealing for Boltzmann machine learning and to simulate quantum magnets by quantum annealing devices.

  • A Canadian company D-Wave Systems has developed a hardware to realize quantum annealing. Google, NASA, and Lockheed-Martin, and Los Alamos National Laboratory are among their customers. Also, many corporations and organizations, including Oak Ridge National Laboratory, Volkswagen, Recruit Communications, and Denso are using the machine over the cloud.

  • Researchers are discussing if the D-Wave machine can solve optimization problems more quickly/efficiently than ordinary computers do. The answer depends on the problem and criteria of speed. For more details, see here for a list of recent papers on this and related topics of quantum annealing.

  • The speed of gate model (circuit model) quantum computers far exceeds that of usual (classical) computers for some problems. Gate-model quantum computers are universal because they can in principle process any computational tasks. Notice that the speed does not exceed that of classical computers except for a special set of problems. An important example is the simulation of small molecules. In this sense, gate-model quantum computers are better regarded as special-purpose machines in practice.

  • Several projects are running worldwide to develop key technologies for high-performance quantum annealers, including IARPA QEO and NEDO (in Japanese).

Introduction

Quantum annealing is a generic approximate method to search for the minimum of a cost function (multivariable function to be minimized) through a control of quantum fluctuations. Quantum annealing is used mainly for combinatorial optimization problems with discrete variables. Many practically important problems can be formulated as combinatorial optimization, including machine learning for clustering, distribution of components in factories, and route optimization in traffic. Finding efficient methods to solve such optimization problems is of enormous social significance, which is the key reason why quantum annealing attracts much attention. Also of current research interest are the sampling problem for machine learning and simulation of quantum magnets.

To perform quantum annealing, one writes the cost function in terms of the Ising model of magnetism. The Hamiltonian (energy function) of the Ising model should be chosen such that its lowest-energy state (ground state) represents the solution to the combinatorial optimization problem. A term representing quantum-mechanical fluctuations is then added to the Hamiltonian to induce quantum transitions between states.

One first chooses a very large value for the coefficient for the quantum term, large relative to the coefficient of the cost function. This leads to a uniform probability of the existence of states over all states as in the left panel (blue line) of the figure. This is a trivial state and can be realized easily. Then one gradually decreases the magnitude of the coefficient of the quantum term. The state of the system follows the time-dependent Schrödinger equation, the natural time evolution of a physical system. The coefficient of the quantum term finally reaches zero, and only the classical term of the Hamiltonian, the Ising model whose ground state is to be identified, remains at the end of the process. It is expected that the probability is by far largest for the solution (the right-most panel of the figure) to the combinatorial optimization problem at the end of the annealing process.



Figure: The process starts from the state on the left-most figure with a uniform probability distribution over all classical states. The system follows the Schrödinger equation to reach the final state on the right, in which the probability focuses on the solution to the combinatorial optimization problem. The abscissa represents the classical state, and the ordinate is for the value of the cost function or the classical Ising Hamiltonian to be minimized (black) and the quantum-mechanical probability of states (blue).

Formulation

The Hamiltonian of the Ising model with a transverse field (the transverse-field Ising model) is written as follows,


where σ is the Pauli matrix. The first term on the right side is the (classical) Ising model. The second term, the transverse-field term, causes quantum fluctuations between classical states. The coefficient Γ(t) starts with a very large value and decreases toward zero at the end of the annealing process, following the natural time evolution of the Schrödinger equation.

Historical note
This prescription of quantum annealing as presently widely used was first proposed in 1998 [A1], where the method was shown to be very effective for several combinatorial optimization problems. An experiment for a magnetic system soon followed [A2] as well as large-scale numerical studies of complex systems [A3]. Read also Kadowaki's thesis [A4]. A continuous-space formulation, different from the Ising-model formulation for combinatorial optimization, had appeared in [A5], where the imaginary-time version of the Schrödinger equation was used, which makes the method classical essentially similarly to [A6].

Reference [A7] focused attetion to the computational complexity of a typical optimization problem and used the following Hamiltonian, under which the system evolution terminates after a finite time T ,

It was proposed in [A7] to use the term "quantum adiabatic evolution" because the system is supposed to follow the instantaneou ground state adiabatically from the initial state to the final state.

[A1] T. Kadowaki and H. Nishimori, Phys. Rev. E58, 5355 (1998) .
[A2] J. Brooke, D. Bitko, T.F. Rosenbaum and G. Aeppli, Science 284, 779 (1999) .
[A3] G. E. Santoro, R. Martonak, E. Tosatti, and R. Car, Science 295, 2427 (2002).
[A4] T. Kadowaki, Thesis, Tokyo Inst. Technology; arXiv:quant-ph/0205020
[A5] A. B. Finnila, M. A. Gomez, C. Sebenik. C. Stenson, and J. D. Doll, Chem. Phys. Lett. 219 (1994) 343.
[A6] B. Apolloni, C. Carvalho, and D. de Falco, Stoc, Proc, Their Appl. 33, 233 (1989); P. Amara, D. Hsu, and J. Straub, J. Phys, Chem. 97, 6715 (1993)
[A7] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292, 472 (2001). See also arXiv:quant-ph/0007071.

Quantum annealing is sometimes understood as a "noisy version" of quantum adiabatic computation in the sense that the former allows for environmental noise as well as diabatic transitions in contrast to the latter. A careful scrutiny of the above-listed papers reveals that these two ideas are essentially the same, at least in their initial formulations. Nevertheless, they differ in several aspects including the strict imposition of adiabaticity in quantum adiabatic computation. Quantum annealing, in contrast, allows for a diabatic time evolution under the expectation that the system reaches the target state with a non-vanishing probability even without the adiabatic condition. Notice that noise is not intrinsic in quantum annealing, although it is not excluded.

Recent studies show that quantum annealing is also useful to sample the Boltzmann-Gibbs distribution for machine learning. See [A8] for review. Also worth attention are simulations of quantum magnets by quantum annealers [A9].

[A8] J. Biamonte et al, Nature 549, 195 (2017); V. Dunjko and H. J. Briegel, arXiv:1709.02779
[A9] A. King et al, Nature 560, 456 (2018); R. Harris et al, Science 361, 162 (2018).

Strengths and Weaknesses

Let us compare quantum annealing with a few related methods.

Further Readings

Listed below are review articles. I refer the reader to papers cited therein for original papers. Contributions from our group at Tokyo Institute of Technology are shown in my list of papers.

T. Albash and D. A. Lidar, Rev. Mod. Phys. 90, 015002 (2018)
A. Das and B. K. Chakrabarti, Rev. Mod. Phys. 80, 1061 (2008)
G.E. Santoro and E. Tosatti, J. Phys A 39, R393 (2006)
S. Suzuki, J. Inoue, and B. K. Chakrabarti, Springer, 2012
A. Ghosh and S. Mukherjee, arXiv:1310.1339

Lecture by Richard Harris of D-Wave Systems


Return to the top page