Quantum annealing

From Wikipedia, the free encyclopedia

Jump to navigation Jump to search
For other uses, see Annealing (disambiguation).

Quantum annealing (QA) is a metaheuristic for finding the global minimum of a given objective
function over a given set of candidate solutions (candidate states), by a process using quantum
fluctuations (in other words, a meta-procedure for finding a procedure that finds an absolute minimum
size/length/cost/distance from within a possibly very large, but nonetheless finite set of possible solutions
using quantum fluctuation-based computation instead of classical computation). Quantum annealing is
used mainly for problems where the search space is discrete (combinatorial optimization problems) with
many local minima; such as finding the ground state of a spin glass[1] or the traveling salesman problem.
It was formulated in its present form by T. Kadowaki and H. Nishimori (ja) in "Quantum annealing in the
transverse Ising model"[2] though a proposal in a different form had been made by A. B. Finnila, M. A.
Gomez, C. Sebenik and J. D. Doll, in "Quantum annealing: A new method for minimizing
multidimensional functions".[3]

Quantum annealing starts from a quantum-mechanical superposition of all possible states (candidate
states) with equal weights. Then the system evolves following the time-dependent Schrödinger equation,
a natural quantum-mechanical evolution of physical systems. The amplitudes of all candidate states keep
changing, realizing a quantum parallelism, according to the time-dependent strength of the transverse
field, which causes quantum tunneling between states. If the rate of change of the transverse field is slow
enough, the system stays close to the ground state of the instantaneous Hamiltonian (also see adiabatic
quantum computation).[4] If the rate of change of the transverse field is accelerated, the system may leave
the ground state temporarily but produce a higher likelihood of concluding in the ground state of the final
problem Hamiltonian, i.e., diabatic quantum computation.[5][6] The transverse field is finally switched off,
and the system is expected to have reached the ground state of the classical Ising model that corresponds
to the solution to the original optimization problem. An experimental demonstration of the success of
quantum annealing for random magnets was reported immediately after the initial theoretical proposal.[7]

Contents
1 Comparison to simulated annealing
2 Quantum mechanics: analogy and advantage
3 D-Wave implementations
4 References
5 Further reading

Comparison to simulated 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 [8] and numerical [9] evidence suggests that quantum annealing
outperforms simulated annealing under certain conditions (see [10] for a careful analysis).

Quantum mechanics: analogy and 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
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.[11]
Since thermal transition probabilities (proportional to , with the temperature and the
Boltzmann constant) depend only on the height 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 of the barrier, but also on its width and is
approximately given by , where is the tunneling field.[12] This additional handle through the
width , in presence of quantum tunneling, can be of major help: If the barriers are thin enough (i.e.
), quantum fluctuations can surely bring the system out of the shallow local minima. For an -
spin glass, the barrier height becomes of order . For constant value of one gets proportional to
for the annealing time (instead of proportional to for thermal annealing), while can even
become -independent for cases where decreases as .[13] [14]

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.[15]

D-Wave implementations
Further information: D-Wave Systems § Computer systems, and D-Wave Two
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.[16] The company claims this system
uses a 128 qubit processor chipset.[17] On May 25, 2011 D-Wave announced that Lockheed Martin
Corporation entered into an agreement to purchase a D-Wave One system.[18] 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.[19][20] An extensive study of its performance as quantum annealer, compared to some classical
annealing algorithms, is already available.[21]

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.[22] 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.[23]

With demonstrations of entanglement published,[24] 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"[25] 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.[26] 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[27] 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.[28]

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.[29]

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.[citation needed]

"A cross-disciplinary introduction to quantum annealing-based algorithms" [30] 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.

References

1. ^ a b Ray, P.; Chakrabarti, B. K.; Chakrabarti, Arunava (1989). "Sherrington-Kirkpatrick model in a

transverse field: Absence of replica symmetry breaking due to quantum fluctuations". Physical
Review B. 39 (16): 11828–11832. Bibcode:1989PhRvB..3911828R.
doi:10.1103/PhysRevB.39.11828. PMID 9948016.
2. ^ Kadowaki, T.; Nishimori, H. (1998). "Quantum annealing in the transverse Ising model". Phys.
Rev. E. 58: 5355. Bibcode:1998PhRvE..58.5355K. doi:10.1103/PhysRevE.58.5355.
3. ^ Finnila, A.B.; Gomez, M.A.; Sebenik, C.; Stenson, C.; Doll, J.D. (1994). "Quantum annealing: A
new method for minimizing multidimensional functions". Chemical Physics Letters. 219 (5–6):
343–348. arXiv:chem-ph/9404003. Bibcode:1994CPL...219..343F. doi:10.1016/0009-
2614(94)00117-0.
4. ^ Farhi, E.; Goldstone, J.; Gutmann, S.; Lapan, J.; Ludgren, A.; Preda, D. (2001). "A Quantum
adiabatic evolution algorithm applied to random instances of an NP-Complete problem". Science.
292: 472. arXiv:quant-ph/0104129. doi:10.1126/science.1057726.
5. ^ E. Crosson, E. Farhi, C.Y-Y. Lin, H-H. Lin, and P. Shor, "Different Strategies for Optimization
Using the Quantum Adiabatic Algorithm" arXiv:1401.7320
6. ^ D. Muthukrishnan, T. Albash, and D.A. Lidar, "When Diabatic Trumps Adiabatic in Quantum
Optimization" arXiv:1505.01249
7. ^ Brooke, J.; Bitko, D.; Rosenbaum, T. F.; Aeppli, G. (1999). "Quantum annealing of a disordered
magnet". Science. 284: 779. Bibcode:1999Sci...284..779B. doi:10.1126/science.284.5415.779.
8. ^ Morita, Satoshi; Nishimori, Hidetoshi (2008). "Mathematical foundation of quantum annealing".
Journal of Mathematical Physics. 49 (12): 125210. arXiv:0806.1859.
Bibcode:2008JMP....49l5210M. doi:10.1063/1.2995837.
9. ^ G. E. Santoro and E. Tosatti, "Optimization using quantum mechanics: quantum annealing
through adiabatic evolution" J. Phys. A 39, R393 (2006)
10. ^ Heim, B.; Rønnow, T. F.; Isakov, S. V.; Troyer, M. (2015). "Quantum versus classical annealing
of Ising spin glasses". Science. 348: 215–217. doi:10.1126/science.aaa4170.
11. ^ "local/global minima/maxima".
12. ^ A. Das, B.K. Chakrabarti, and R.B. Stinchcombe, "Quantum annealing in a kinetically
constrained system", Phys. Rev. E 72 art. 026701 (2005)
13. ^ See e.g., S. Mukherjee, and B. K. Chakrabarti "Multivariable Optimization: Quantum Annealing
& Computation", Eur. Phys. J. ST 224 pp 17–24 (2015) arXiv:1408.3262
14. ^ Das, A.; Chakrabarti, B. K. (2008). "Quantum Annealing and Analog Quantum Computation".
Rev. Mod. Phys. 80 (3): 1061–1081. arXiv:0801.2193. Bibcode:2008RvMP...80.1061D.
CiteSeerX 10.1.1.563.9990. doi:10.1103/RevModPhys.80.1061.
15. ^ F. Li; V. Y. Chernyak; N. A. Sinitsyn (2018). "Quantum annealing and thermalization: insights
from integrability". Physical Review Letters. 121 (19): 190601. arXiv:1804.00371.
Bibcode:2018arXiv180400371L. doi