Quantum Annealing by Hidetoshi Nishimori
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.
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).
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.
Simulated annealing and quantum Monte Carlo simulation
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 time t in the same manner as the temperature T(t) in simulated time [B1]. Recent extensive benchmark results indicate that quantum annealing has scaling advantages to reach the correct solutions than simulated annealing in several cases of spin glass type problems [B2]. It is also shown analytically for a simple problem that quantum annealing can be exponentially faster than simulated annealing [B3]
Quantum annealing in its naive formulation can often be simulated on a conventional computer using quantum Monte Carlo simulations. One of the advantages of the dedicated quantum-annealing device in its present form is to perform the annealing process much more quickly, in terms of the absolute time, than by simulations on the convetional computer. This is an advantage of a constant numerical factor, not necessarily in the scaling advantage which matters when the problem size increases. Nevertheless, when this constant numerical factor is large, it means practical usefulness. See [B2] for a recent benchmark.
[B1] S. Morita and H. Nishimori, J. Math. Phys. 49, 125210 (2008).
[B2] T. Albash and D. A. Lidar, Phys. Rev. X8, 031016 (2018).
[B3] Y. Susa, Y. Yamashiro, M. Yamamoto, I. Hen, D. A. Lidar, and H. Nishimori, Phys. Rev. A 98, 042326 (2018).
Gate (circuit) model
Many of the studies of quantum computation concern the gate model, in which one applies quantum gates one by one to the state of a system toward the desired solution of the problem. A large number of research papers have been published, but experiments have been plagued by decoherence, i.e., destruction of quantum states through interactions with the environment. It will take some more time before a device of practical usefulness is built. Also, practical applications of the gate-model quantum computer are relatively 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. For other problems, gate-model quantum computers are not known to be fast. Also of interest is quantum approximate optimization algorithm (QAOA) for combinatorial optimization [B4], though it is not known at present if this algorithm runs fast. Watch this excellent lecture by Peter Shor.
[B4] E. Farhi and J. Goldstone, arXiv:1411.4028
One of the realistic applications of gate model quantum computers is quantum simulation of small-size molecules [B5]. Also, methods to efficiently solve linear equations by gate model quantum computers may be applied to machine learning and related tasks [B6] though care must be taken [B7], e.g. one should devise an efficient method to load classical data on a quantum machine.
[B5] B. Bauer et al, Phys. Rev. X6, 031045 (2016); P.J.J. O'Malley et al, Phys. Rev. X6, 031007 (2016); Proc. Nat. Acad. Sci. USA., 114, 7555 (2017)
[B6] J. Biamonte et al, Nature 549, 195 (2017)
[B7] S. Aaronson, Nature Physics, 11, 291 (2015).
A quantum annealing machine can be used for combinatorial optimization, which has a wide range of practical applications. Also, it is known that an extended form of quantum annealing is theoretically equivalent to the circuit model [B8, B9]. It would also be remarkable that the same extention leads to an exponential speedup of quantum annealing in comparison with the conventional simple protocol, at least for a special problem [B10].
[B8] D. Aharonov et al, SIAM J. Comp. 37 (2007) 166.
[B9] J. D. Biamonte and P. J. Love, Phys. Rev. A78, 012352 (2008).
[B10] H. Nishimori and K. Takada, Front. ICT 4, 2 (2017), Y. Seki and H. Nishimori, Phys. Rev. E 85, 051112 (2012), J. Phys. A 48, 335301 (2015), B. Seoane and H. Nishimori, J. Phys. A 45, 435301 (2012).
Quantum annealing is less susceptible to decoherence than the circuit model is since the former follows the inherently-stable ground state and its low-excition neighbors.
Gate (circuit) model
Several algorithms of practical importance are proven to be exponentially faster than classical methods.
Many problems of practical importance, such as machine learning, can be represented as combinatorial optimization. Resilient against noise.
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 20 to 50 qubits （superconducting circuits）
About 2,000 qubits（superconducting circuits）
Needs extremely many qubits, tens of millions or more, if one implements error corrections for problems of pracitical size. Will take many decades to realize such. If an error correction is set aside for the moment, a machine with hundreds of qubits may be realized in several to ten years.
Applications by hybrid operation with conventional computers are starting to be reported.
Relation with 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 the gate-model quantum computer, 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 [B2, B3]. It is nevertheless unclear whether or not there exist problems of significant practical interest where quantum annealing achieves a significant speedup over conventional methods. Notice that there indeed exist a problem in which an exponential speedup by quantum annealing (not by adiabatic quantum computation) is proved although this problem is of limited practical usefulness.
Quantum annealing needs an exponentially long time to find the exact solution to most difficult problems among all combinatorial optimization problems.
Indeed, it is explicitly shown from the analysis of energy spectra that quantum annealing spends an exponentially long time to solve several specific problems.
It has nevertheless been well known from a number of numerical and analytical studies that quantum annealing improves the performance, if not exponentially, of solving many combinatorial optimization problems in comparison with classical simulated annealing.
It is unlikely that quantum annealing would drastically reduce the time to reach solutions for many problems for which only exponentially slow classical algorithms are known. It is also incorrect, on the other hand, that there would exist no such cases. Indeed this paper shows that an exponential speedup is reached for the binary-tree problem, though the problem is of limited practical interest.
It is not necessary for quantum annealing to follow the instantaneous ground state. Evaluation of computational complexity based on the energy-gap analysis would clarifly only part of the capabilities of quantum annealing. Indeed, the above-mentioned solution to the binary-tree problem does not follow the instantaneous ground state. In other words, adiabatic quantum computation (AQC) is a subset of quantum annealing (QA) but the converse is not true. Also, quantum annealing may be understood to allow for interactions with the environment including thermal noise.
Theoretical equivalence is proved between the circuit (gate) model and quantum annealing with extended interactions [B8, B9]. It is nevertheless difficult in practice to translate the language of one to that of the other, in particular from gate to annealing. A practical usefulness of the extension, called non-stoquastic Hamiltonians, is that it leads to a dramatic speedup for a special type of problem [B10].
Several papers show that the D-Wave machine operates under the principle of quantum mechanics, at least as long as a part of the system is involved [B11, B12].
It may seem counter-intuitive that data from the D-Wave machine shows quantumness when the coherence time is of the order of 10 nano seconds whereas the computation time is of the order of 10 micro seconds or longer. Nevertheless, a theoretical argument suggests that, when decoherence applies in the energy eigenbasis, noise is not as directly detrimental as one may naively expect [B13].
[B13] T. Albash and D. Lidar, Phys, Rev. A 91, 062320 (2015)
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