Quantum Annealing by Hidetoshi Nishimori

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. E

58, 5355 (1998) .

[A2] J. Brooke, D. Bitko, T.F. Rosenbaum and G. Aeppli, Science284, 779 (1999) .

[A3] G. E. Santoro, R. Martonak, E. Tosatti, and R. Car, Science295, 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, Science292, 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., Nature549, 195 (2017); V. Dunjko and H. J. Briegel, arXiv:1709.02779

[A10] A. Kinget al., Nature560, 456 (2018); R. Harriset al., Science361, 162 (2018); A. King et al, arXiv:1911.03446; Y. Bandoet al., Phys. Rev. Res.2, 03369 (2020); K. Nishimuraet al., Phys. Rev. A102, 042403 (2020).Other approaches

Let us discuss a few related methods.

Simulated annealing

Simulated annealing is a generic method to solve optimization problems using classical probability, or thermal effects in analogy with statistical mechanics. It has been shown that quantum annealing, in theory, allows the system to approach the correct solution more quickly than simulated annealing if we control the coefficient of the transverse field

Γ(t) as a function of timetin the same manner as the temperatureT(t) in simulated time [Ba1]. Recent extensive benchmark results indicate that quantum annealing has scaling advantages to reach the correct solutions than simulated annealing in several cases [Ba2]. It is also shown that quantum annealing can be exponentially efficient under certain conditions [Ba3]

[Ba1] S. Morita and H. Nishimori, J. Math. Phys.

49, 125210 (2008).

[Ba2] A. Kinget al., Nature Commun. 12, 1113 (2021). T. Albash and D. A. Lidar, Phys. Rev. X8, 031016 (2019)

[Ba3] M. Hastings, arXiv:2005.03791.Gate model quantum computer

Gate-model quantum computers are studied extensively, in which one applies quantum gates one by one to the state of a quatum system toward the desired solution of a problem. A large number of research papers have been published, but efforts to build real machines have been plagued by decoherence, destruction of quantum states through interactions with the environment. It will take a few decades before a device of practical usefulness is built if it is ever possible. A recent paper by Google [Bb1] shows evidence of superiority of their quantum chip over classical simulations for a theoretical problem of random-number generation although the same chip still has difficulties in solving more practically-relevant problems [Bb2].

Also, the number of practically-relevant applications of the gate-model quantum computer is limited: e.g., integer factoring, simulations of quantum systems, and solving a class of linear algebra problems. Quantum algorithms for these problems have been proven to show an exponential speedup over classical algorithms if the problem of data loading is solved [Bb3]. For other problems, gate-model quantum computers are not known to be fast.

NISQ (Noisy Intermediate-Scale Quantum) computers are expected to be used on optimization and quantum-chemistry problems through quantum-classical hybrid algorithms athough the current stage of development still has a distance from practical usefulness[Bb2, Bb4]. Also, it is unknown generally if hybrid algothms lead to a quantum speedup.

[Bb1] F. Arute

et al., Nature574, 505 (2019)

[Bb2] F. Aruteet al., Nature Phys.17, 332 (2021)

[Bb3] S. Aaronson, Nature Phys.11, 291 (2015)

[Bb4] F. Aruteet al., Science369, 1084 (2020); M. Streifet al., arXiv:2011.03403

Gate (circuit) model

Quantum annealing

Strengths

Several algorithms of practical importance are proven to run exponentially faster than classical methods.

Many problems of practical importance can be represented as combinatorial optimization. Resilient against noise.

Weaknesses

Qubits are very susceptible to decoherence, i.e. easily destroyed by noise. Error correction needs a very heavy overhead. Faster than conventional machines only for a few problems as long as practical relevance is concerned.

Problems are yet to be found that are proved to be solved exponentially more efficiently than by classical methods and are of practical significance. Error-correction scheme yet to be established.

Current Status of Implementation

About 50 qubits （superconducting circuits and trapped ions）

About 5,000 qubits（superconducting circuit）

Classical (conventional) computers

The goal of quantum annealing is to solve combinatorial optimization and related problems. Quantum annealing machines will not replace conventional computers for other problems. This aspect is shared by gate-model quantum computers, which is very powerful for a set of specific problems but not for others.

As long as optimization problems are concerned, there exists evidence that, for some special problems, quantum annealing outperforms classical simulated annealing or classical simulations of quantum annealing [Ba2]. It is nevertheless unclear whether or not there exist problems of practical benefit where quantum annealing achieves a significant speedup over conventional methods. Notice that there indeed exist problems in which an exponential/superpolynomial speedup by quantum annealing over classical algorithms is achieved [Ba3, Bc1] although these problems have a distance from practical usefulness. Also known is that quantum annealing performs universal computation if it makes appropriate use of excited states or non-stoquastic Hamiltonians [Bc2].[Bc1] R. D. Somma

et al., Phys. Rev. Lett. 109, 050501 (2012); M. B. Hastings, arXiv:2005.03791.

[Bc2] E. Crosson and D. A. Lidar, arXiv:2008.09913; J. D. Biamonte and P. J. Love, Phys. Rev. A78, 012352 (2008).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