Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0910.5644 · Progress of Theoretical Physics Supplement

Quantum Annealing of Hard Problems

Thomas Jörg, Florent Krząkała, Jorge Kurchan B, Andrew Colin Maggs

Published Jan 1, 2010• 11 citations
arXivHTMLPDF

Abstract

Quantum annealing is analogous to simulated annealing with a tunneling mechanism substituting for thermal activation. Its performance has been tested in numerical simulation with mixed conclusions. There is a class of optimization problems for which the efficiency can be studied analytically using techniques based on the statistical mechanics of spin glasses.

DOI
10.1143/ptps.184.290

Related papers

1Quantum Annealing of Hard Problems

Florent Krząkała, Jorge Kurchan B, Anthony C. Maggs

Quantum annealing is analogous to simulated annealing with a tunneling mechanism substituting for thermal activation. Its performance has been tested in numerical simulation with mixed conclusions. There is a class of optimization problems for which the efficiency can be studied analytically using techniques based on the statistical mechanics of spin glasses. Solving hard combinatorial problems by temperature annealing is a classic method in computer science.1) The problem is formulated in terms of a cost function, which one can identify as an energy. The dynamics are then a combination of a systematic descent in energy perturbed by a ’noise’, which is turned off gradually, inducing

•Aug 17, 2016•14 citations

Quantum annealing

Alfonso de la Fuente Ruiz

Brief description on the state of the art of some local optimization methods: Quantum annealing Quantum annealing (also known as alloy, crystallization or tempering) is analogous to simulated annealing but in substitution of thermal activation by quantum tunneling. The class of algorithmic methods for quantum annealing (dubbed: 'QA'), sometimes referred by the italian school as Quantum Stochastic Optimization ('QSO'), is a promising metaheuristic tool for solving local search problems in multivariable optimization contexts.

arXiv:1404.2465•Apr 9, 2014•5 citations

Optimization by quantum annealing: Lessons from hard satisfiability problems

Demian A. Battaglia, Giuseppe E. Santoro, Erio Tosatti

The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.

arXiv:cond-mat/0502468•Physical Review E•Jun 29, 2005•107 citations

Quantum annealing optimization and geophysical inverse method

Meigen Zhang

The idea of Quantum Annealing(QA),which is based on the mechanism of quantum transition tunneling effect and not same with the annealing theory of simulated thermal annealing,is a recent offspring of the celebrated simulated thermal annealing by Kirkpatrick.This paper,firstly,summarizes the basic differences between Quantum Annealing and Simulated Annealing;and then mainly addresses the attention to the practical developments of the application in optimization such as Ising spin glass,Traveling Salesman Problem,Boolean Satisfiability Problem and so on,discusses the details of the annealing process of Quantum Annealing and its compare with Simulated Annealing on test problems;subsequently,expatiates the geophysical inverse theory and method corresponding to Quantum Annealing,discusses the setting of parameters such as Temperature and Transverse field,compares the probabilities of being on configurations with different transverse fields and potential energies;finally briefly summarizes the prospects and the existent problems of using Quantum Annealing in geophysical inverse problem.

Progress in geophysics•Jan 1, 2007•2 citations

Quantum Spin Glasses, Annealing and Computation

Shu Tanaka, Ryo Tamura, Bikas K. Chakrabarti

Quantum annealing is a new-generation tool of information technology, which helps in solving combinatorial optimization problems with high precision, based on the concepts of quantum statistical physics. Detailed discussion on quantum spin glasses and its application in solving combinatorial optimization problems is required for better understanding of quantum annealing concepts. Fulfilling this requirement, the book highlights recent development in quantum spin glasses including Nishimori line, replica method and quantum annealing methods along with the essential principles. Separate chapters on simulated annealing, quantum dynamics and classical spin models are provided for enhanced learning. Important topics including adiabatic quantum computers and quenching dynamics are discussed in detail. This text will be useful for students of quantum computation, quantum information, statistical physics and computer science.

•May 4, 2017•75 citations

Tunneling through high energy barriers in simulated quantum annealing

Elizabeth Crosson, Mingkai Deng

We analyze the performance of simulated quantum annealing (SQA) on an optimization problem for which simulated classical annealing (SA) is provably inefficient because of a high energy barrier. We present evidence that SQA can pass through this barrier to find the global minimum efficiently. This demonstrates the potential for SQA to inherit some of the advantages of quantum annealing (QA), since this problem has been previously shown to be efficiently solvable by quantum adiabatic optimization.

arXiv:1410.8484•Oct 30, 2014•9 citations
Quantum annealing is analogous to simulated annealing with a tunneling mechanism substituting for thermal activation. Its performance has been tested in numerical simulation with mixed conclusions. There is a class of optimization problems for which the efficiency can be studied analytically using techniques based on the statistical mechanics of spin glasses.
Quantum annealing is analogous to simulated annealing with a tunneling mechanism substituting for thermal activation. Its performance has been tested in numerical simulation with mixed conclusions. There is a class of optimization problems for which the efficiency can be studied analytically using techniques based on the statistical mechanics of spin glasses. Solving hard combinatorial problems by temperature annealing is a classic method in computer science.1) The problem is formulated in terms of a cost function, which one can identify as an energy. The dynamics are then a combination of a systematic descent in energy perturbed by a ’noise’, which is turned off gradually, inducing
Brief description on the state of the art of some local optimization methods: Quantum annealing Quantum annealing (also known as alloy, crystallization or tempering) is analogous to simulated annealing but in substitution of thermal activation by quantum tunneling. The class of algorithmic methods for quantum annealing (dubbed: 'QA'), sometimes referred by the italian school as Quantum Stochastic Optimization ('QSO'), is a promising metaheuristic tool for solving local search problems in multivariable optimization contexts.
The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.
The idea of Quantum Annealing(QA),which is based on the mechanism of quantum transition tunneling effect and not same with the annealing theory of simulated thermal annealing,is a recent offspring of the celebrated simulated thermal annealing by Kirkpatrick.This paper,firstly,summarizes the basic differences between Quantum Annealing and Simulated Annealing;and then mainly addresses the attention to the practical developments of the application in optimization such as Ising spin glass,Traveling Salesman Problem,Boolean Satisfiability Problem and so on,discusses the details of the annealing process of Quantum Annealing and its compare with Simulated Annealing on test problems;subsequently,expatiates the geophysical inverse theory and method corresponding to Quantum Annealing,discusses the setting of parameters such as Temperature and Transverse field,compares the probabilities of being on configurations with different transverse fields and potential energies;finally briefly summarizes the prospects and the existent problems of using Quantum Annealing in geophysical inverse problem.
Quantum annealing is a new-generation tool of information technology, which helps in solving combinatorial optimization problems with high precision, based on the concepts of quantum statistical physics. Detailed discussion on quantum spin glasses and its application in solving combinatorial optimization problems is required for better understanding of quantum annealing concepts. Fulfilling this requirement, the book highlights recent development in quantum spin glasses including Nishimori line, replica method and quantum annealing methods along with the essential principles. Separate chapters on simulated annealing, quantum dynamics and classical spin models are provided for enhanced learning. Important topics including adiabatic quantum computers and quenching dynamics are discussed in detail. This text will be useful for students of quantum computation, quantum information, statistical physics and computer science.