Optimization through quantum annealing: theory and some applications

D. A. Battaglia, L. Stella*

*Corresponding author for this work

Research output: Contribution to journalLiterature reviewpeer-review

3 Citations (Scopus)

Abstract

Quantum annealing is a promising tool for solving optimization problems, similar in some ways to the traditional ( classical) simulated annealing of Kirkpatrick et al. Simulated annealing takes advantage of thermal fluctuations in order to explore the optimization landscape of the problem at hand, whereas quantum annealing employs quantum fluctuations. Intriguingly, quantum annealing has been proved to be more effective than its classical counterpart in many applications. We illustrate the theory and the practical implementation of both classical and quantum annealing - highlighting the crucial differences between these two methods - by means of results recently obtained in experiments, in simple toy-models, and more challenging combinatorial optimization problems ( namely, Random Ising model and Travelling Salesman Problem). The techniques used to implement quantum and classical annealing are either deterministic evolutions, for the simplest models, or Monte Carlo approaches, for harder optimization tasks. We discuss the pro and cons of these approaches and their possible connections to the landscape of the problem addressed.

Original languageEnglish
Pages (from-to)195-208
Number of pages14
JournalContemporary physics
Volume47
Issue number4
DOIs
Publication statusPublished - 2006

Keywords

  • ALGORITHM

Cite this