Hidetoshi Nishimori (Last updated: 23 March 2022)
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.
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
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.
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-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.|
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.