Quantum Annealing by Hidetoshi Nishimori

Executive Summary Introduction Formulation Other approaches 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 useful methods to solve combinatorial optimization problems has enormous practical significance. Also of current target of research activities is applications of quantum annealing as sampling and quantum simulations. See here and here for examples of the latter.

  • D-Wave Systems has developed a device to realize quantum annealing. Google, NASA, and Lockheed-Martin, and Los Alamos National Laboratory introduced the device. Also, many private companies, universities, and public institutions are using the machines over the cloud. There exist projects to build prototype high-performance quantum annealers in Japan, the United States and the EU.

  • Researchers are studying if quantum annealing can solve optimization problems better than ordinary computers do. It is not easy to establish a general theory on this topic, and studies are going on using specific examples, approximate theories, and the real device. A recent paper by a team of D-Wave and Google showed that the D-Wave machine shows a scaling advantage against classical simulations for a hard simulation problem. For further information, see here and here for a list of recent papers on this and related topics of quantum annealing.

  • The speed of a gate-based quantum computer, if it is ever successfully built in an enormously large scale, is expected to far exceed that of usual (classical) computers for some problems. Gate-model quantum computers are universal and sometimes called "general purpose" because they can in principle process any computational tasks. However, the speed does not exceed that of classical computers except for a special set of problems. According to the report of the U.S. National Academies,
    "Quantum computers are unlikely to be useful as a direct replacement for conventional computers, or for all applications; rather, they are currently expected to be special-purpose devices operating in a complementary fashion with conventional processors, analogous to a coprocessor or accelerator." This comment applies to quantum annealing as well.

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. Many practically important problems can be formulated as combinatorial optimization problems, such as portfolio optimization and route optimization in logistics. Finding useful methods to solve optimization problems is of enormous social significance, which is a key reason why quantum annealing attracts much attention. Also of current research interest is simulations of quantum-mechanical systems and sampling.

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. Then, a term representing quantum-mechanical fluctuations is 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, a quantum-mechanical superposition of all possible states. This is a state easy to prepare in practice. 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. When the process is successful, 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 numerically to be better for several combinatorial optimization problems than the classical method of simulated annealing. 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 essentially classical similarly to [A6].

Reference [A7] focused attention 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 "adiabatic quantum computation" because, in their formulation, the system follows the instantaneous ground state adiabatically from the initial state to the final state. Notice that the conclusion of this reference, an exponential speedup by adiabatic quantum computing for a difficult optimization problem, is now known to be incorrect due to the smallness of the system size [A8].

[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).
[A8] A.P. Young, S. Knysh, V. Smelyanskiy, Phys. Rev. Lett. 104, 020502 (2010).

Quantum annealing is sometimes taken 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 [A1, A7] 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 thermal (or other) 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 [A9] for review. Also worth attention are simulations of many-body systems by quantum annealers [A10].

[A9] J. Biamonte et al., Nature 549, 195 (2017); V. Dunjko and H. J. Briegel, arXiv:1709.02779
[A10] A. King et al., Nature 560, 456 (2018); R. Harris et al., Science 361, 162 (2018); A. King et al, arXiv:1911.03446; Y. Bando et al., Phys. Rev. Res. 2, 03369 (2020); K. Nishimura et al., Phys. Rev. A 102, 042403 (2020).

Other approaches

Let us discuss a few related methods.

Further Readings

Listed below are recent reviews and videos.


E. K. Grant and T. S. Humble, Oxford Research Encyclopedia of Physics (2020)
Report by the U.S. National Academies of Sciences, Engineering, and Medicine, Quantum Computing: Progress and Prospects
P. Hauke, H. G. Katzgraber, H. Nishimori, and W. D. Oliver, Rep. Prog. Phys. 83, 054401 (2020).
T. Albash and D. A. Lidar, Rev. Mod. Phys. 90, 015002 (2018)
Webiner by Edward (Denny) Dahl of D-Wave Systems


Return to the top page