An introduction to quantum annealing
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 45 (2011) no. 1, p. 99-116

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.

DOI : https://doi.org/10.1051/ita/2011013
Classification:  81P68,  68Q12,  68W25
Keywords: combinatorial optimization, adiabatic quantum computation, quantum annealing, dissipative dynamics
@article{ITA_2011__45_1_99_0,
     author = {de Falco, Diego and Tamascelli, Dario},
     title = {An introduction to quantum annealing},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {1},
     year = {2011},
     pages = {99-116},
     doi = {10.1051/ita/2011013},
     zbl = {1219.68105},
     mrnumber = {2776856},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2011__45_1_99_0}
}
de Falco, Diego; Tamascelli, Dario. An introduction to quantum annealing. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 45 (2011) no. 1, pp. 99-116. doi : 10.1051/ita/2011013. http://www.numdam.org/item/ITA_2011__45_1_99_0/

[1] D. Aharonov et al., Adiabatic quantum computation is equivalent to standard quantum computation. SIAM J. Comput. 37 (2007) 166. | MR 2306288 | Zbl 1134.81009

[2] S. Albeverio, R. Hoeg-Krohn and L. Streit, Energy forms, Hamiltonians and distorted Brownian paths. J. Math. Phys. 18 (1977) 907-917. | MR 446236 | Zbl 0368.60091

[3] B. Altshuler, H. Krovi and J. Roland, Anderson localization casts clouds over adiabatic quantum optimization. arXiv:0912.0746v1 (2009).

[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] A. Ambainis and O. Regev, An elementary proof of the quantum adiabatic theorem. arXiv:quant-ph/0411152 (2004).

[6] M.H.S. Amin and V. Choi. First order quantum phase transition in adiabatic quantum computation. arXiv:quant-ph/0904.1387v3 (2009).

[7] P. Anderson, Absence of diffusion in certain random lattices. Phys. Rev. 109 (1958) 1492-1505.

[8] B. Apolloni, C. Carvalho and D. De Falco, Quantum stochastic optimization. Stoc. Proc. Appl. 33 (1989) 223-244. | MR 1030210 | Zbl 0683.90067

[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. | MR 1124205

[10] D. Battaglia, G. Santoro, L. Stella, E. Tosatti and O. Zagordi, Deterministic and stochastic quantum annealing approaches. Lecture Notes in Computer Physics 206 (2005) 171-206.

[11] E. Bernstein and U. Vazirani, Quantum complexity theory. SIAM J. Comput. 26 (1997) 1411-1473. | MR 1471988 | Zbl 0895.68042

[12] F. Bloch, Über die Quantenmechanik der Elektronen in Kristallgittern. Z. Phys. 52 (1929) 555-600. | JFM 54.0990.01

[13] M. Born and V. Fock, Beweis des Adiabatensatzes. Z. Phys. A 51 (1928) 165. | JFM 54.0994.03

[14] S. Bravyi, Efficient algorithm for a quantum analogue of 2-sat. arXiV:quant-ph/0602108 (2006). | MR 2768792 | Zbl 1218.81032

[15] H.P. Breuer and F. Petruccione, The theory of open quantum systems. Oxford University Press, New York (2002). | MR 2012610 | Zbl 1223.81001

[16] D. De Falco and D. Tamascelli, Speed and entropy of an interacting continuous time quantum walk. J. Phys. A 39 (2006) 5873-5895. | MR 2238121 | Zbl 1098.81026

[17] D. De Falco and D. Tamascelli, Quantum annealing and the Schrödinger-Langevin-Kostin equation. Phys. Rev. A 79 (2009) 012315.

[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). | MR 2778557 | Zbl 1208.81123

[19] D. Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400 (1985) 97-117. | MR 801665 | Zbl 0900.81019

[20] S. Eleuterio and S. Vilela Mendes, Stochastic ground-state processes. Phys. Rev. B 50 (1994) 5035-5040.

[21] E. Farhi et al., Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106v1 (2000).

[22] E. Farhi et al., A quantum adiabatic evolution algorithm applied to random instances of an NP-Complete problem. Science (2001) 292. | MR 1838761 | Zbl 1226.81046

[23] R. Feynman, Simulating physics with computers. Int. J. Theor. Phys. 21 (1982) 467-488. | MR 658311

[24] R.P. Feynman, Space-time approach to non-relativistic quantum mechanics. Rev. Mod. Phys. 20 (1948) 367-387. | MR 26940

[25] G. Ford, M. Kac and P. Mazur, Statistical mechanics of assemblies of coupled oscillators. J. Math. Phys. 6 (1965) 504-515. | MR 180277 | Zbl 0127.21605

[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] J.J. Griffin and K.-K. Kan, Colliding heavy ions: Nuclei as dynamical fluids. Rev. Mod. Phys. 48 (1976) 467-477.

[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). | MR 1427516 | Zbl 0922.68044

[29] L. Grover, From Schrödinger equation to the quantum search algorithm. Am. J. Phys. 69 (2001) 769-777.

[30] T. Hogg, Adiabatic quantum computing for random satisfiability problems. Phys. Rev. A 67 (2003) 022314.

[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. | Zbl 0698.90065

[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. | MR 623159 | Zbl 0483.60094

[33] M. Kac, On distributions of certain Wiener functionals. Trans. Am. Math. Soc. (1949) 1-13. | MR 27960 | Zbl 0032.03501

[34] J. Kempe, A. Kitaev and O. Regev, The complexity of the local Hamiltonian problem. SIAM J. Comput. 35 (2006) 1070-1097. | MR 2217138 | Zbl 1102.81032

[35] S. Kirkpatrik, C.D. Gelatt Jr. and M.P. Vecchi, Optimization by simulated annealing. Science 220 (1983) 671-680. | MR 702485 | Zbl 1225.90162

[36] M. Kostin, On the Schrödinger-Langevin equation. J. Chem. Phys. 57 (1972) 3589-3591.

[37] M. Kostin, Friction and dissipative phenomena in quantum mechanics. J. Statist. Phys. 12 (1975) 145-151.

[38] K. Kurihara, S. Tanaka and S. Miyashita, Quantum annealing for clustering. arXiv:quant-ph/09053527v2 (2009).

[39] C. Laumann et al., On product, generic and random generic quantum satisfiability. arXiv:quant-ph/0910.2058v1 (2009).

[40] C. Laumann et al., Phase transitions and random quantum satisfiability. arXiv:quant-ph/0903.1904v1 (2009).

[41] A. Messiah, Quantum Mechanics. John Wiley and Sons (1958). | Zbl 0102.42602

[42] S. Morita and H. Nishimori, Mathematical foundations of quantum annealing. J. Math. Phys. 49 (2008) 125210. | MR 2484341 | Zbl 1159.81332

[43] C. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity. Dover New York (1998). | MR 1637890 | Zbl 0944.90066

[44] B. Reichardt, The quantum adiabatic optimization algorithm and local minima, in Proc. 36th STOC (2004) 502. | MR 2121636 | Zbl 1192.81098

[45] G. Santoro and E. Tosatti, Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A 39 (2006) R393-R431. | MR 2275113 | Zbl 1130.49037

[46] G. Santoro and E. Tosatti, Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A: Math. Theor. 41 (2008) 209801. | MR 2455150 | Zbl 1149.49038

[47] P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 (1997) 1484. | MR 1471990 | Zbl 1005.11065

[48] L. Stella, G. Santoro and E. Tosatti, Optimization by quantum annealing: Lessons from simple cases. Phys. Rev. B 72 (2005) 014303.

[49] W. Van Dam, M. Mosca and U. Vazirani, How powerful is adiabatic quantum computation. Proc. FOCS '01 (2001). | MR 1948718

[50] J. Watrous, Succint quantum proofs for properties of finite groups, in Proc. IEEE FOCS (2000) 537-546. | MR 1931850

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

[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] C. Zener, A theory of the electrical breakdown of solid dielectrics. Proc. R. Soc. Lond. A 145 (1934) 523-529. | Zbl 0009.27605

[54] M. Žnidari and M. Horvat, Exponential complexity of an adiabatic algorithm for an np-complete problem. Phys. Rev. A 73 (2006) 022329.