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.
Mots-clés : 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},
pages = {99--116},
publisher = {EDP-Sciences},
volume = {45},
number = {1},
year = {2011},
doi = {10.1051/ita/2011013},
mrnumber = {2776856},
zbl = {1219.68105},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita/2011013/}
}
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 SP - 99 EP - 116 VL - 45 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2011013/ DO - 10.1051/ita/2011013 LA - en ID - ITA_2011__45_1_99_0 ER -
%0 Journal Article %A de Falco, Diego %A Tamascelli, Dario %T An introduction to quantum annealing %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2011 %P 99-116 %V 45 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2011013/ %R 10.1051/ita/2011013 %G en %F 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, Tome 45 (2011) no. 1, pp. 99-116. doi : 10.1051/ita/2011013. http://archive.numdam.org/articles/10.1051/ita/2011013/
[1] et al., Adiabatic quantum computation is equivalent to standard quantum computation. SIAM J. Comput. 37 (2007) 166. | MR | Zbl
[2] , and , Energy forms, Hamiltonians and distorted Brownian paths. J. Math. Phys. 18 (1977) 907-917. | MR | Zbl
[3] , and , Anderson localization casts clouds over adiabatic quantum optimization. arXiv:0912.0746v1 (2009).
[4] , and , Global minimum searches using an approximate solution of the imaginary time Schrödinger equation. J. Chem. Phys. 97 (1993) 6715-6721.
[5] and , An elementary proof of the quantum adiabatic theorem. arXiv:quant-ph/0411152 (2004).
[6] and . First order quantum phase transition in adiabatic quantum computation. arXiv:quant-ph/0904.1387v3 (2009).
[7] , Absence of diffusion in certain random lattices. Phys. Rev. 109 (1958) 1492-1505.
[8] , and , Quantum stochastic optimization. Stoc. Proc. Appl. 33 (1989) 223-244. | MR | Zbl
[9] , and , 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
[10] , , , and , Deterministic and stochastic quantum annealing approaches. Lecture Notes in Computer Physics 206 (2005) 171-206.
[11] and , Quantum complexity theory. SIAM J. Comput. 26 (1997) 1411-1473. | MR | Zbl
[12] , Über die Quantenmechanik der Elektronen in Kristallgittern. Z. Phys. 52 (1929) 555-600. | JFM
[13] and , Beweis des Adiabatensatzes. Z. Phys. A 51 (1928) 165. | JFM
[14] , Efficient algorithm for a quantum analogue of 2-sat. arXiV:quant-ph/0602108 (2006). | MR | Zbl
[15] and , The theory of open quantum systems. Oxford University Press, New York (2002). | MR | Zbl
[16] and , Speed and entropy of an interacting continuous time quantum walk. J. Phys. A 39 (2006) 5873-5895. | MR | Zbl
[17] and , Quantum annealing and the Schrödinger-Langevin-Kostin equation. Phys. Rev. A 79 (2009) 012315.
[18] , and , Dissipative quantum annealing, in Proceedings of the 29th Conference on Quantum Probability and Related Topics. World Scientific (2009) (in press). | MR | Zbl
[19] , Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400 (1985) 97-117. | MR | Zbl
[20] and , Stochastic ground-state processes. Phys. Rev. B 50 (1994) 5035-5040.
[21] et al., Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106v1 (2000).
[22] et al., A quantum adiabatic evolution algorithm applied to random instances of an NP-Complete problem. Science (2001) 292. | MR | Zbl
[23] , Simulating physics with computers. Int. J. Theor. Phys. 21 (1982) 467-488. | MR
[24] , Space-time approach to non-relativistic quantum mechanics. Rev. Mod. Phys. 20 (1948) 367-387. | MR
[25] , and , Statistical mechanics of assemblies of coupled oscillators. J. Math. Phys. 6 (1965) 504-515. | MR | Zbl
[26] and , Minimization of the potential energy surface of Lennard-Jones clusters by quantum optimization. Chem. Rev. Lett. 412 (2005) 125-130.
[27] and , Colliding heavy ions: Nuclei as dynamical fluids. Rev. Mod. Phys. 48 (1976) 467-477.
[28] , A fast quantum-mechanical algorithm for database search, in Proc. 28th Annual ACM Symposium on the Theory of Computing. ACM, New York (1996). | MR | Zbl
[29] , From Schrödinger equation to the quantum search algorithm. Am. J. Phys. 69 (2001) 769-777.
[30] , Adiabatic quantum computing for random satisfiability problems. Phys. Rev. A 67 (2003) 022314.
[31] , , and , Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning. Oper. Res. 37 (1989) 865-892. | Zbl
[32] , and , New approach to the semiclassical limit of quantum mechanics. i. Multiple tunnelling in one dimension. Commun. Math. Phys. 80 (1981) 223-254. | MR | Zbl
[33] , On distributions of certain Wiener functionals. Trans. Am. Math. Soc. (1949) 1-13. | MR | Zbl
[34] , and , The complexity of the local Hamiltonian problem. SIAM J. Comput. 35 (2006) 1070-1097. | MR | Zbl
[35] , and , Optimization by simulated annealing. Science 220 (1983) 671-680. | MR | Zbl
[36] , On the Schrödinger-Langevin equation. J. Chem. Phys. 57 (1972) 3589-3591.
[37] , Friction and dissipative phenomena in quantum mechanics. J. Statist. Phys. 12 (1975) 145-151.
[38] , and , Quantum annealing for clustering. arXiv:quant-ph/09053527v2 (2009).
[39] et al., On product, generic and random generic quantum satisfiability. arXiv:quant-ph/0910.2058v1 (2009).
[40] et al., Phase transitions and random quantum satisfiability. arXiv:quant-ph/0903.1904v1 (2009).
[41] , Quantum Mechanics. John Wiley and Sons (1958). | Zbl
[42] and , Mathematical foundations of quantum annealing. J. Math. Phys. 49 (2008) 125210. | MR | Zbl
[43] and , Combinatorial optimization: algorithms and complexity. Dover New York (1998). | MR | Zbl
[44] , The quantum adiabatic optimization algorithm and local minima, in Proc. 36th STOC (2004) 502. | MR | Zbl
[45] and , Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A 39 (2006) R393-R431. | MR | Zbl
[46] and , Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A: Math. Theor. 41 (2008) 209801. | MR | Zbl
[47] , Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 (1997) 1484. | MR | Zbl
[48] , and , Optimization by quantum annealing: Lessons from simple cases. Phys. Rev. B 72 (2005) 014303.
[49] , and , How powerful is adiabatic quantum computation. Proc. FOCS '01 (2001). | MR
[50] , Succint quantum proofs for properties of finite groups, in Proc. IEEE FOCS (2000) 537-546. | MR
[51] , and . Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Phys. Rev. Lett. 101 (2008) 170503.
[52] et al., Time-dependent density functional theory for open quantum systems with unitary propagation. arXiv:cond-mat.mtrl-sci/0902.4505v3 (2009).
[53] , A theory of the electrical breakdown of solid dielectrics. Proc. R. Soc. Lond. A 145 (1934) 523-529. | Zbl
[54] and , Exponential complexity of an adiabatic algorithm for an np-complete problem. Phys. Rev. A 73 (2006) 022329.
Cité par Sources :
