An introduction to quantum annealing

Diego de Falco; Dario Tamascelli

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2011)

  • Volume: 45, Issue: 1, page 99-116
  • ISSN: 0988-3754

Abstract

top
Quantum annealing, or quantum stochastic optimization, is a classical randomized algorithm which provides good heuristics for the solution of hard optimization problems. The algorithm, suggested by the behaviour of quantum systems, is an example of proficuous cross contamination between classical and quantum computer science. In this survey paper we illustrate how hard combinatorial problems are tackled by quantum computation and present some examples of the heuristics provided by quantum annealing. We also present preliminary results about the application of quantum dissipation (as an alternative to imaginary time evolution) to the task of driving a quantum system toward its state of lowest energy.

How to cite

top

de Falco, Diego, and Tamascelli, Dario. "An introduction to quantum annealing." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 45.1 (2011): 99-116. <http://eudml.org/doc/273078>.

@article{deFalco2011,
abstract = {Quantum annealing, or quantum stochastic optimization, is a classical randomized algorithm which provides good heuristics for the solution of hard optimization problems. The algorithm, suggested by the behaviour of quantum systems, is an example of proficuous cross contamination between classical and quantum computer science. In this survey paper we illustrate how hard combinatorial problems are tackled by quantum computation and present some examples of the heuristics provided by quantum annealing. We also present preliminary results about the application of quantum dissipation (as an alternative to imaginary time evolution) to the task of driving a quantum system toward its state of lowest energy.},
author = {de Falco, Diego, Tamascelli, Dario},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {combinatorial optimization; adiabatic quantum computation; quantum annealing; dissipative dynamics},
language = {eng},
number = {1},
pages = {99-116},
publisher = {EDP-Sciences},
title = {An introduction to quantum annealing},
url = {http://eudml.org/doc/273078},
volume = {45},
year = {2011},
}

TY - JOUR
AU - de Falco, Diego
AU - Tamascelli, Dario
TI - An introduction to quantum annealing
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2011
PB - EDP-Sciences
VL - 45
IS - 1
SP - 99
EP - 116
AB - Quantum annealing, or quantum stochastic optimization, is a classical randomized algorithm which provides good heuristics for the solution of hard optimization problems. The algorithm, suggested by the behaviour of quantum systems, is an example of proficuous cross contamination between classical and quantum computer science. In this survey paper we illustrate how hard combinatorial problems are tackled by quantum computation and present some examples of the heuristics provided by quantum annealing. We also present preliminary results about the application of quantum dissipation (as an alternative to imaginary time evolution) to the task of driving a quantum system toward its state of lowest energy.
LA - eng
KW - combinatorial optimization; adiabatic quantum computation; quantum annealing; dissipative dynamics
UR - http://eudml.org/doc/273078
ER -

References

top
  1. [1] D. Aharonov et al., Adiabatic quantum computation is equivalent to standard quantum computation. SIAM J. Comput. 37 (2007) 166. Zbl1134.81009MR2306288
  2. [2] S. Albeverio, R. Hoeg-Krohn and L. Streit, Energy forms, Hamiltonians and distorted Brownian paths. J. Math. Phys. 18 (1977) 907–917. Zbl0368.60091MR446236
  3. [3] B. Altshuler, H. Krovi and J. Roland, Anderson localization casts clouds over adiabatic quantum optimization. arXiv:0912.0746v1 (2009). Zbl1205.81056
  4. [4] P. Amara, D. Hsu and J. Straub, Global minimum searches using an approximate solution of the imaginary time Schrödinger equation. J. Chem. Phys.97 (1993) 6715–6721. 
  5. [5] A. Ambainis and O. Regev, An elementary proof of the quantum adiabatic theorem. arXiv:quant-ph/0411152 (2004). 
  6. [6] M.H.S. Amin and V. Choi. First order quantum phase transition in adiabatic quantum computation. arXiv:quant-ph/0904.1387v3 (2009). 
  7. [7] P. Anderson, Absence of diffusion in certain random lattices. Phys. Rev.109 (1958) 1492–1505. 
  8. [8] B. Apolloni, C. Carvalho and D. de Falco, Quantum stochastic optimization. Stoc. Proc. Appl.33 (1989) 223–244. Zbl0683.90067MR1030210
  9. [9] B. Apolloni, N. Cesa-Bianchi and D. de Falco, A numerical implementation of Quantum Annealing, in Stochastic Processes, Physics and Geometry, Proceedings of the Ascona/Locarno Conference, 4–9 July 1988. Albeverio et al., Eds. World Scientific (1990), 97–111. MR1124205
  10. [10] D. Battaglia, G. Santoro, L. Stella, E. Tosatti and O. Zagordi, Deterministic and stochastic quantum annealing approaches. Lecture Notes in Computer Physics206 (2005) 171–206. 
  11. [11] E. Bernstein and U. Vazirani, Quantum complexity theory. SIAM J. Comput.26 (1997) 1411–1473. Zbl0895.68042MR1471988
  12. [12] F. Bloch, Über die Quantenmechanik der Elektronen in Kristallgittern. Z. Phys.52 (1929) 555–600. Zbl54.0990.01JFM54.0990.01
  13. [13] M. Born and V. Fock, Beweis des Adiabatensatzes. Z. Phys. A 51 (1928) 165. Zbl54.0994.03JFM54.0994.03
  14. [14] S. Bravyi, Efficient algorithm for a quantum analogue of 2-sat. arXiV:quant-ph/0602108 (2006). Zbl1218.81032MR2768792
  15. [15] H.P. Breuer and F. Petruccione, The theory of open quantum systems. Oxford University Press, New York (2002). Zbl1223.81001MR2012610
  16. [16] D. de Falco and D. Tamascelli, Speed and entropy of an interacting continuous time quantum walk. J. Phys. A39 (2006) 5873–5895. Zbl1098.81026MR2238121
  17. [17] D. de Falco and D. Tamascelli, Quantum annealing and the Schrödinger-Langevin-Kostin equation. Phys. Rev. A 79 (2009) 012315. 
  18. [18] D. de Falco, E. Pertoso and D. Tamascelli, Dissipative quantum annealing, in Proceedings of the 29th Conference on Quantum Probability and Related Topics. World Scientific (2009) (in press). Zbl1208.81123
  19. [19] D. Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A400 (1985) 97–117. Zbl0900.81019MR801665
  20. [20] S. Eleuterio and S. Vilela Mendes, Stochastic ground-state processes. Phys. Rev. B50 (1994) 5035–5040. 
  21. [21] E. Farhi et al., Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106v1 (2000). 
  22. [22] E. Farhi et al., A quantum adiabatic evolution algorithm applied to random instances of an NP-Complete problem. Science (2001) 292. Zbl1226.81046MR1838761
  23. [23] R. Feynman, Simulating physics with computers. Int. J. Theor. Phys.21 (1982) 467–488. MR658311
  24. [24] R.P. Feynman, Space-time approach to non-relativistic quantum mechanics. Rev. Mod. Phys.20 (1948) 367–387. MR26940
  25. [25] G. Ford, M. Kac and P. Mazur, Statistical mechanics of assemblies of coupled oscillators. J. Math. Phys.6 (1965) 504–515. Zbl0127.21605MR180277
  26. [26] T. Gregor and R. Car, Minimization of the potential energy surface of Lennard-Jones clusters by quantum optimization. Chem. Rev. Lett.412 (2005) 125–130. 
  27. [27] J.J. Griffin and K.-K. Kan, Colliding heavy ions: Nuclei as dynamical fluids. Rev. Mod. Phys.48 (1976) 467–477. 
  28. [28] L. Grover, A fast quantum-mechanical algorithm for database search, in Proc. 28th Annual ACM Symposium on the Theory of Computing. ACM, New York (1996). Zbl0922.68044MR1427516
  29. [29] L. Grover, From Schrödinger equation to the quantum search algorithm. Am. J. Phys.69 (2001) 769–777. 
  30. [30] T. Hogg, Adiabatic quantum computing for random satisfiability problems. Phys. Rev. A 67 (2003) 022314. 
  31. [31] D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Shevon, Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning. Oper. Res.37 (1989) 865–892. Zbl0698.90065
  32. [32] G. Jona-Lasinio, F. Martinelli and E. Scoppola, New approach to the semiclassical limit of quantum mechanics. i. Multiple tunnelling in one dimension. Commun. Math. Phys. 80 (1981) 223–254. Zbl0483.60094MR623159
  33. [33] M. Kac, On distributions of certain Wiener functionals. Trans. Am. Math. Soc. (1949) 1–13. Zbl0032.03501MR27960
  34. [34] J. Kempe, A. Kitaev and O. Regev, The complexity of the local Hamiltonian problem. SIAM J. Comput.35 (2006) 1070–1097. Zbl1102.81032MR2217138
  35. [35] S. Kirkpatrik, C.D. Gelatt Jr. and M.P. Vecchi, Optimization by simulated annealing. Science220 (1983) 671–680. Zbl1225.90162MR702485
  36. [36] M. Kostin, On the Schrödinger-Langevin equation. J. Chem. Phys.57 (1972) 3589–3591. 
  37. [37] M. Kostin, Friction and dissipative phenomena in quantum mechanics. J. Statist. Phys.12 (1975) 145–151. 
  38. [38] K. Kurihara, S. Tanaka and S. Miyashita, Quantum annealing for clustering. arXiv:quant-ph/09053527v2 (2009). 
  39. [39] C. Laumann et al., On product, generic and random generic quantum satisfiability. arXiv:quant-ph/0910.2058v1 (2009). 
  40. [40] C. Laumann et al., Phase transitions and random quantum satisfiability. arXiv:quant-ph/0903.1904v1 (2009). 
  41. [41] A. Messiah, Quantum Mechanics. John Wiley and Sons (1958). Zbl0102.42602
  42. [42] S. Morita and H. Nishimori, Mathematical foundations of quantum annealing. J. Math. Phys. 49 (2008) 125210. Zbl1159.81332MR2484341
  43. [43] C. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity. Dover New York (1998). Zbl0944.90066MR1637890
  44. [44] B. Reichardt, The quantum adiabatic optimization algorithm and local minima, in Proc. 36th STOC (2004) 502. Zbl1192.81098MR2121636
  45. [45] G. Santoro and E. Tosatti, Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A 39 (2006) R393–R431. Zbl1130.49037MR2275113
  46. [46] G. Santoro and E. Tosatti, Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A: Math. Theor. 41 (2008) 209801. Zbl1149.49038MR2455150
  47. [47] P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 (1997) 1484. Zbl1005.11065MR1471990
  48. [48] L. Stella, G. Santoro and E. Tosatti, Optimization by quantum annealing: Lessons from simple cases. Phys. Rev. B 72 (2005) 014303. 
  49. [49] W. van Dam, M. Mosca and U. Vazirani, How powerful is adiabatic quantum computation. Proc. FOCS '01 (2001). MR1948718
  50. [50] J. Watrous, Succint quantum proofs for properties of finite groups, in Proc. IEEE FOCS (2000) 537–546. MR1931850
  51. [51] A.P. Young, S. Knysh and V.N. Smelyanskiy. Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Phys. Rev. Lett. 101 (2008) 170503. Zbl1219.81081
  52. [52] J. Yuen-Zhou et al., Time-dependent density functional theory for open quantum systems with unitary propagation. arXiv:cond-mat.mtrl-sci/0902.4505v3 (2009). 
  53. [53] C. Zener, A theory of the electrical breakdown of solid dielectrics. Proc. R. Soc. Lond. A145 (1934) 523–529. Zbl0009.27605
  54. [54] M. Žnidari and M. Horvat, Exponential complexity of an adiabatic algorithm for an np-complete problem. Phys. Rev. A 73 (2006) 022329. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.