Quantum Annealing

Hidetoshi Nishimori (Last updated: 23 March 2022)


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.
D-Wave Systems has developed a device to realize quantum annealing. Google, NASA, and Lockheed-Martin, Los Alamos National Laboratory, and Forschungszentrum Jülich 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 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. This problem will be discussed below, see the bottom of this page. For further information, see here and here for a list of recent papers on this and related topics of quantum annealing.
Gate model
Speed of a gate-based quantum computer, if it is successfully built at a very large scale, is expected to far exceed that of usual (classical) computers for some problems. Gate-model quantum computers are universal and sometimes called universal 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.

Review articles and Webinar

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)
E. K. Grant and T. S. Humble, Oxford Research Encyclopedia of Physics (2020)
Webinar by Dr. Edward (Denny) Dahl

Working principle


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 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 panel 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 horizontal axis represents the classical state, and the vertical axis is for the value of the cost function 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 hand side represents the transverse field to induce quantum fluctuations, and the second trem is the classical Ising model, the cost function, whose lowest-energy state is to be identified. The parameter s is for time: If the total computation time is T and the real time is t , then s is defined as s=t/T.The function A(s) decreases with s from a finite value to zero, and B(s) is an increasing function. See the figure. Initially, the first term for transverse field (with A(s)) dominates and all possible states are in quantum superposition with almost equal probabilities. Then, the relative wegitht of the second term (cost funtion) is increased toward the end where only the right solution (lowest-energy state) has a finite probability.

Related methods

Simulated annealing

Simulated annealing is a widely used classical metaheuristic (generic and approximate algorithm) based on stochastic search processes. This paper and this paper shows that quantum annealing is more efficient to solve certain problems. See also this paper for another example.

Gate-based 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 ever is. Google claimed to have found evidence of superiority of their quantum chip over classical simulations for a theoretical problem of random-number generation, which has been refuted by a group of Chinese scientists, who received the prestigeous Gordon Bell prize for this work. Also, Google's same chip has difficulties in solving more practically-relevant problems.

Also, the number of practically-relevant applications of the gate-model quantum computer is limited: e.g., integer factorization, 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. For other problems, gate-model quantum computers are not known to be fast.

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

  Gate-based system Quantum annealing
Strengths Several algorithms of practical importance are proven to run exponentially faster than classical methods. Protocols of error correction are established theoretically. Many problems of practical importance can be represented as combinatorial optimization. Relatively resilient against noise.
Weaknesses Qubits are very susceptible to decoherence and easily destroyed by noise. Error correction needs a very heavy overhead. 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.

Conventional (classical) computers

The goal of quantum annealing is specifically designed to solve combinatorial optimization and related problems, and quantum annealing machines will not replace conventional computers. 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, quantum annealing outperforms classical simulated annealing or classical simulations of quantum annealing for a few specially-designed problems, see here and here. It is unclear whether or not there exist problems of practical benefit where quantum annealing achieves a significant speedup over conventional methods. Also known is that quantum annealing performs universal computation if it makes appropriate use of excited states or non-stoquastic Hamiltonians.