Quantum annealing

Quantum annealing can be compared to simulated annealing, whose "temperature" parameter plays a similar role to QA's tunneling field strength. In simulated annealing, the temperature determines the probability of moving to a state of higher "energy" from a single current state. In quantum annealing, the strength of transverse field determines the quantum-mechanical probability to change the amplitudes of all states in parallel. Analytical [10] and numerical [11] evidence suggests that quantum annealing outperforms simulated annealing under certain conditions (see [12] for a careful analysis).

The tunneling field is basically a kinetic energy term that does not commute with the classical potential energy part of the original glass. The whole process can be simulated in a computer using quantum Monte Carlo (or other stochastic technique), and thus obtain a heuristic algorithm for finding the ground state of the classical glass.

In the case of annealing a purely mathematical objective function, one may consider the variables in the problem to be classical degrees of freedom, and the cost functions to be the potential energy function (classical Hamiltonian). Then a suitable term consisting of non-commuting variable(s) (i.e. variables that have non-zero commutator with the variables of the original mathematical problem) has to be introduced artificially in the Hamiltonian to play the role of the tunneling field (kinetic part). Then one may carry out the simulation with the quantum Hamiltonian thus constructed (the original function + non-commuting part) just as described above. Here, there is a choice in selecting the non-commuting term and the efficiency of annealing may depend on that.

It has been demonstrated experimentally as well as theoretically, that quantum annealing can indeed outperform thermal annealing (simulated annealing) in certain cases, especially where the potential energy (cost) landscape consists of very high but thin barriers surrounding shallow local minima.[13] Since thermal transition probabilities (proportional to ${\displaystyle e^{-{\frac {\Delta }{k_{B}T}}}}$, with ${\displaystyle T}$ the temperature and ${\displaystyle k_{B}}$ the Boltzmann constant) depend only on the height ${\displaystyle \Delta }$ of the barriers, for very high barriers, it is extremely difficult for thermal fluctuations to get the system out from such local minima. However, as argued earlier in 1989 by Ray, Chakrabarti & Chakrabarti,[1] the quantum tunneling probability through the same barrier (considered in isolation) depends not only on the height ${\displaystyle \Delta }$ of the barrier, but also on its width ${\displaystyle w}$ and is approximately given by ${\displaystyle e^{-{\frac {{\sqrt {\Delta }}w}{\Gamma }}}}$, where ${\displaystyle \Gamma }$ is the tunneling field.[14] This additional handle through the width ${\displaystyle w}$, in presence of quantum tunneling, can be of major help: If the barriers are thin enough (i.e. ${\displaystyle w\ll {\sqrt {\Delta }}}$), quantum fluctuations can surely bring the system out of the shallow local minima. For an ${\displaystyle N}$-spin glass, the barrier height ${\displaystyle \Delta }$ becomes of order ${\displaystyle N}$. For constant value of ${\displaystyle w}$ one gets ${\displaystyle \tau }$ proportional to ${\displaystyle e^{\sqrt {N}}}$ for the annealing time (instead of ${\displaystyle \tau }$ proportional to ${\displaystyle e^{N}}$ for thermal annealing), while ${\displaystyle \tau }$ can even become ${\displaystyle N}$-independent for cases where ${\displaystyle w}$ decreases as ${\displaystyle 1/{\sqrt {N}}}$.[15] [16]

It is speculated that in a quantum computer, such simulations would be much more efficient and exact than that done in a classical computer, because it can perform the tunneling directly, rather than needing to add it by hand. Moreover, it may be able to do this without the tight error controls needed to harness the quantum entanglement used in more traditional quantum algorithms. Some confirmation of this is found in exactly solvable models.[17]

Photograph of a chip constructed by D-Wave Systems, mounted and wire-bonded in a sample holder. The D-Wave One's processor is designed to use 128 superconducting logic elements that exhibit controllable and tunable coupling to perform operations.

In 2011, D-Wave Systems announced the first commercial quantum annealer on the market by the name D-Wave One and published a paper in Nature on its performance.[18] The company claims this system uses a 128 qubit processor chipset.[19] On May 25, 2011 D-Wave announced that Lockheed Martin Corporation entered into an agreement to purchase a D-Wave One system.[20] On October 28, 2011 USC's Information Sciences Institute took delivery of Lockheed's D-Wave One.

In May 2013 it was announced that a consortium of Google, NASA Ames and the non-profit Universities Space Research Association purchased an adiabatic quantum computer from D-Wave Systems with 512 qubits.[21][22] An extensive study of its performance as quantum annealer, compared to some classical annealing algorithms, is already available.[23]

In June 2014, D-Wave announced a new quantum applications ecosystem with computational finance firm 1QB Information Technologies (1QBit) and cancer research group DNA-SEQ to focus on solving real-world problems with quantum hardware.[24] As the first company dedicated to producing software applications for commercially available quantum computers, 1QBit's research and development arm has focused on D-Wave's quantum annealing processors and has successfully demonstrated that these processors are suitable for solving real-world applications.[25]

With demonstrations of entanglement published,[26] the question of whether or not the D-Wave machine can demonstrate quantum speedup over all classical computers remains unanswered. A study published in Science in June 2014, described as "likely the most thorough and precise study that has been done on the performance of the D-Wave machine"[27] and "the fairest comparison yet", attempted to define and measure quantum speedup. Several definitions were put forward as some may be unverifiable by empirical tests, while others, though falsified, would nonetheless allow for the existence of performance advantages. The study found that the D-Wave chip "produced no quantum speedup" and did not rule out the possibility in future tests.[28] The researchers, led by Matthias Troyer at the Swiss Federal Institute of Technology, found "no quantum speedup" across the entire range of their tests, and only inconclusive results when looking at subsets of the tests. Their work illustrated "the subtle nature of the quantum speedup question". Further work[29] has advanced understanding of these test metrics and their reliance on equilibrated systems, thereby missing any signatures of advantage due to quantum dynamics.

There are many open questions regarding quantum speedup. The ETH reference in the previous section is just for one class of benchmark problems. Potentially there may be other classes of problems where quantum speedup might occur. Researchers at Google, LANL, USC, Texas A&M, and D-Wave are working hard to find such problem classes.[30]

In December 2015, Google announced that the D-Wave 2X outperforms both simulated annealing and Quantum Monte Carlo by up to a factor of 100,000,000 on a set of hard optimization problems.[31]

D-Wave's architecture differs from traditional quantum computers. It is not known to be polynomially equivalent to a universal quantum computer and, in particular, cannot execute Shor's algorithm because Shor's algorithm is not a hillclimbing process. Shor's algorithm requires a universal quantum computer. D-Wave claims only to do quantum annealing.

"A cross-disciplinary introduction to quantum annealing-based algorithms" [32] presents an introduction to combinatorial optimization (NP-hard) problems, the general structure of quantum annealing-based algorithms and two examples of this kind of algorithms for solving instances of the max-SAT and Minimum Multicut problems, together with an overview of the quantum annealing systems manufactured by D-Wave Systems. Hybrid quantum-classic algorithms for large-scale discrete-continuous optimization problems were reported to illustrate the quantum advantage.[33]

• Venegas-Andraca, Salvador E.; Cruz-Santos, William; McGeoch, Catherine; Lanzagorta, Marco (2018). "A cross-disciplinary introduction to quantum annealing-based algorithms". Contemporary Physics. 59 (2): 174–197. arXiv:1803.03372. Bibcode:2018ConPh..59..174V. doi:10.1080/00107514.2018.1450720. S2CID 118974781.
• http://iopscience.iop.org/0305-4470/39/36/R01. Cite journal requires |journal= (help); Missing or empty |title= (help)
• S. Suzuki, J.-i. Inoue & B. K. Chakrabarti, Quantum Ising Phases & Transitions in Transverse Ising Models, Springer, Heidelberg (2013), Chapter 8 on Quantum Annealing.
• Bapst, V.; Foini, L.; Krzakala, F.; Semerjian, G.; Zamponi, F. (2013). "The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective". Physics Reports. 523 (3): 127–205. arXiv:1210.0811. Bibcode:2013PhR...523..127B. doi:10.1016/j.physrep.2012.10.002. S2CID 19019744.
• Arnab Das and Bikas K Chakrabarti (Eds.), Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, 679, Springer, Heidelberg (2005).
• Anjan K. Chandra, Arnab Das and Bikas K Chakrabarti (Eds.), Quantum Quenching, Annealing and Computation, Lecture Note in Physics, 802, Springer, Heidelberg (2010).
• Li, Fuxiang; Chernyak, V. Y.; Sinitsyn, N. A. (2013). "Quantum Annealing and Computation: A Brief Documentary Note". arXiv:1310.1339. Bibcode:2013arXiv1310.1339G. Cite journal requires |journal= (help).
• A. Dutta, G. Aeppli, B. K. Chakrabarti, U. Divakaran, T.F. Rosenbaum & D. Sen, "Quantum Phase Transitions in Transverse Field Spin Models: From Statistical Physics to Quantum Information, Cambridge University Press, Cambridge & Delhi (2015).
• S. Tanaka, R. Tamura & B. K. Chakrabarti, Quantum Spin Glasses, Annealing & Computation, Cambridge University Press, Cambridge & Delhi (2017).
• Indian Science News Association, Special Issue of "Science & Culture" on 'A Quantum Jump in Computation', Vol. 85 (5-6), May-June (2019)