World Library  
Flag as Inappropriate
Email this Article

Quantum annealing

 

Quantum annealing

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. 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] It was formulated in its present form by T. Kadowaki and H. Nishimori in "Quantum annealing in the transverse Ising model"[2] though a proposal in a different form had been proposed by A. B. Finilla, 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, i.e., adiabatic quantum computation.[4] 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.[5]

Contents

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

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 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. 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 1989 by Ray, Chakrabarti & Chakrabarti in Ref. [1], the quantum tunneling probability through the same barrier depends not only on the height \Delta of the barrier, but also on its width w and is approximately given by \exp{(- \Delta^{1/2}w/ \Gamma) }, where \Gamma is the tunneling field.[9] If the barriers are thin enough ( w \ll \Delta^{-1/2}), quantum fluctuations can surely bring the system out of the shallow local minima. For N-spin glasses, \Delta~N, and with a linear annealing schedule for the transverse field, one gets \tau~ \exp{(N^{1/2})} for the annealing time (instead of \tau ~ \exp {(N)} for thermal annealing).[10] 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.[11]

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 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 [12] on its performance. The company claims this system uses a 128 qubit processor chipset.[13] On May 25, 2011 D-Wave announced that Lockheed Martin Corporation entered into an agreement to purchase a D-Wave One system.[14] 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.[15][16] An extensive study of its performance as quantum annealer, compared to some classical annealing algorithms, is already available.[17]

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.[18] 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.[19]

With demonstrations of entanglement published,[20] 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"[21] 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.[22] 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."

D-Wave's architecture differs from traditional quantum computers (none of which exist in practice as of today). It is unable to simulate a universal quantum computer and, in particular, cannot execute Shor's algorithm.

References

  1. ^ P Ray, BK Chakrabarti, A Chakrabarti "Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations" , 11828 (1989)39Phys. Rev. B
  2. ^ T. Kadowaki and H. Nishimori, "Quantum annealing in the transverse Ising model" , 5355 (1998)58Phys. Rev. E
  3. ^ A. B. Finilla, M. A. Gomez, C. Sebenik and J. D. Doll, "Quantum annealing: A new method for minimizing multidimensional functions" , 343 (1994)219Chem. Phys. Lett.
  4. ^ 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" , 472 (2001)292Science
  5. ^ J. Brooke, D. Bitko, T. F. Rosenbaum and G. Aeppli, "Quantum annealing of a disordered magnet", 779 (1999)284Science
  6. ^ S. Morita and H. Nishimori, "Mathematical foundation of quantum annealing", , 125210 (2008)49J.Math. Phys.
  7. ^ G. E. Santoro and E. Tosatti, "Optimization using quantum mechanics: quantum annealing through adiabatic evolution" , R393 (2006)39J. Phys. A
  8. ^ B. Heim, T. F. Rønnow, S. V. Isakov and M. Troyer, "Quantum versus classical annealing of Ising spin glasses" , pp. 215-217 (2015)348Science
  9. ^ A. Das, B.K. Chakrabarti, and R.B. Stinchcombe, "Quantum annealing in a kinetically constrained system", art. 026701 (2005)72Phys. Rev. E
  10. ^ 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
  11. ^ J. Roland and N.J. Cerf, "Quantum search by local adiabatic evolution",, 042308 (2002)65Phys. Rev. A
  12. ^ M. W. Johnson et al., "Quantum annealing with manufactured spins", 194 (2011)473Nature
  13. ^ "Learning to program the D-Wave One". Retrieved 11 May 2011. 
  14. ^ "D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation". 2011-05-25. Retrieved 2011-05-30. 
  15. ^ N. Jones, Google and NASA snap up quantum computer, Nature (2013), doi: 10.1038/nature.2013.12999
  16. ^ V. N. Smelyanskiy, E. G. Rieffel, S. I. Knysh, C. P. Williams, M. W. Johnson, M. C. Thom, W. G. Macready, K. L. Pudenz, "A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration", arXiv:1204.2821
  17. ^ S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, M. Troyer, "Evidence for quantum annealing with more than one hundred qubits, Nature Physics, vol. 10, pp. 218–224 (2014)", [2]
  18. ^ "D-Wave Systems Building Quantum Application Ecosystem, Announces Partnerships with DNA-SEQ Alliance and 1QBit". D-Wave Systems. Retrieved 22 June 2014. 
  19. ^ "1QBit Research". 1QBit. Retrieved 22 June 2014. 
  20. ^ "Entanglement in a quantum annealing processor". prx. 2014-05-29. 
  21. ^ Helmut Katzgraber, quoted in (Cho 2014).
  22. ^ Cho, Adrian (20 June 2014), "Quantum or not, controversial computer yields no speedup", Science 344 (6190): 1330–1331,  .

General review articles and books

  • G. E. Santoro and E. Tosatti, "Optimization using quantum mechanics: quantum annealing through adiabatic evolution" , R393 (2006)39J. Phys. A .
  • Arnab Das and B. K. Chakrabarti, "Colloquium: Quantum annealing and analog quantum computation" , 1061 (2008)80Rev. Mod. Phys. .
  • S. Suzuki, J.-i. Inoue & B. K. Chakrabarti,"Quantum Ising Phases & Transitions in Transverse Ising Models", Springer, Heidelberg (2013), Chapter 8 on Quantum Annealing.
  • V. Bapst, L. Foini, F. Krzakala, G. Semerjian and F. Zamponi, "The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective", 127 (2013)523Physics Reports .
  • Arnab Das and Bikas K Chakrabarti (Eds.), , Springer, Heidelberg (2005)679"Quantum Annealing and Related Optimization Methods", Lecture Note in Physics, Vol. .
  • Anjan K. Chandra, Arnab Das and Bikas K Chakrabarti (Eds.),, Springer, Heidelberg (2010)802"Quantum Quenching, Annealing and Computation", Lecture Note in Physics, Vol. .
  • A. Ghosh and S. Mukherjee, "Quantum Annealing and Computation: A Brief Documentary Note", arXiv:1310.1339.
  • 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, Delhi (2015).
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.