Quantum annealing

For other uses, see Annealing (disambiguation).

In mathematics and applications, quantum annealing (QA) is a general method for finding the global minimum of a given objective function over a given set of candidate solutions (the search space), by a process analogous to quantum fluctuations. It is used mainly for problems where the search space is discrete (combinatorial optimization problems) with many local minima; such as finding the ground states of a glassy system.

In quantum annealing, a "current state" (the current candidate solution) is randomly replaced by a randomly selected neighbor state if the latter has a lower "energy" (value of the objective function). The process is controlled by the "tunneling field strength", a parameter that determines the extent of the neighborhood of states explored by the method (Kadowaki and Nishimori, 1998). The tunneling field starts high, so that the neighborhood extends over the whole search space; and is slowly reduced through the computation (adiabatically; Farhi et al., 2001), until the neighborhood shrinks to those few states that differ minimally from the current states. By that time, the system finds a very deep (hopefully, the global one) minimum and settles there. At the end, we are left with the classical system at its global minimum. Indeed, the possibility of this quantum tunneling across the width of the barriers, instead of scaling their heights (as in classical or simulated annealing), was first pointed out by Ray et al. (1989) in the context of the search of replica symmetry restoration and the consequent advantage in the search of ground state(s) in quantum spin glasses. An experimental demonstration of the success of quantum annealing for random magnets was first reported by Brooke et al. (1999).

Comparison to simulated annealing

Quantum annealing can be compared to simulated annealing (SA), whose "temperature" parameter plays a similar role to QA's tunneling field strength. However, in SA the neighborhood stays the same throughout the search, and the temperature determines the probability of moving to a state of higher "energy". In QA, the tunneling field strength determines instead the neighborhood radius, i.e. the mean distance between the next candidate state and the current candidate state.

In more elaborated SA variants (such as Adaptive simulated annealing), the neighborhood radius is also varied using acceptance rate percentages or the temperature value.

Quantum mechanics: Analogy & advantage

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 has 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 in certain cases, especially where the potential energy (cost) landscape consists of very high but thin barriers surrounding shallow local minima. Since thermal transition probabilities (~$\exp{(-\Delta/k_{B}T)}$; $T$ => Temperature, $k_{B}$ => Boltzmann constant) depend only on the height $\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 Ray et al. (1989), the quantum tunneling probability through the same barrier depends not only the height $\Delta$ of the barrier, but also on its width $w$ and is approximately given by $\exp{(- \Delta^{1/2}w/ \Gamma) }$; $\Gamma$=> Tunneling field. If the barriers are thin enough $( w << \Delta^{1/2})$, quantum fluctuations can surely bring the system out of the shallow local minima. This $O(N^{1/2})$ advantage in quantum search (compared to the classical effort growing linearly with $\Delta$ or $N$, the problem size) is well established.

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.

Implementations

Photograph of a chip constructed by D-Wave Systems Inc., mounted and wire-bonded in a sample holder. The D-Wave 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. The company claims this system uses a 128 qubit processor chipset. On May 25, 2011 D-Wave announced that Lockheed Martin Corporation entered into an agreement to purchase a D-Wave One system. On October 28, 2011 USC's Information Sciences Institute took delivery of Lockheed's D-Wave One, where it has become the first operational commercial "quantum computer".

D-Wave's architecture differs from traditional quantum computers in that it has noisy, high error-rate qubits, since it is designed specifically for quantum annealing.

References

• P. Ray, B. K. Chakrabarti and A. Chakrabarti, "Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations", Phys. Rev. B 39 11828 (1989)
• B. Apolloni, C. Caravalho, D. De Falco, "Quantum stochastic optimization", Stochastic Processes and their Applications, 33, 233-244 (1989).
• P. Amara, D. Hsu and J. E. Straub, "Global energy minimum searches using an approximate solution of the imaginary time Schroedinger equation", J. Phys. Chem. 97 6715 (1993)
• A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson and D. J. Doll, "Quantum annealing: A new method for minimizing multidimensional functions", Chem. Phys. Lett. 219 343 (1994)
• T. Kadowaki and H. Nishimori, "Quantum annealing in the transverse Ising model", Phys. Rev. E 58 5355 (1998)
• J. Brooke, D. Bitko, T. F. Rosenbaum and G. Aeppli, "Quantum annealing of a disordered magnet", Science 284 779 (1999)
• E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Ludgren and D. Preda, "A Quantum adiabatic evolution algorithm applied to random instances of an NP-Complete problem", Science 292 472 (2001)
• G. E. Santoro and E. Tosatti, "Optimization using quantum mechanics: Quantum annealing through adiabatic evolution", J. Phys. A 39 R393 (2006)
• A. Das and B. K. Chakrabarti, "Quantum annealing and analog quantum computation", Rev. Mod. Phys. 80 1061 (2008)
• M. W. Johnson et al. (D-Wave Group), "Quantum annealing with manufactured spins", Nature 473 194 (2011)
• Y. Seki and H. Nishimori, "Quantum annealing with antiferromagnetic fluctuations", Phys. Rev. E85 051112 (2012)
• For a recent review, see Quantum Ising Phases & Transitions in Transverse Ising Models, S. Suzuki, J.-i. Inoue & B. K. Chakrabarti, Springer, Heidelberg (2013)
• For a collection of reviews on the pioneering early developments, see: Arnab Das and Bikas K Chakrabarti (Eds.), Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005); Anjan K. Chandra, Arnab Das and Bikas K Chakrabarti (Eds.),Quantum Quenching, Annealing and Computation, Lecture Note in Physics, Vol. 802, Springer, Heidelberg (2010)