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

Statistical science and interdisciplinary research

Quantum Annealing, Spin Glasses, Optimization and Analog Quantum Computation

Arnab Das, Bikas K. Chakrabarti

Published Nov 1, 2009• 0 citations
Publisher

Abstract

We review here the recent success in annealing or optimizing the cost functions of complex systems utilizing quantum fluctuations rather than the classical (thermal) fluctuations. These are introduced through studies of mapping of such computationally hard problems to classical spin glass problems, quantum spin glasses and consequent annealing or analog quantum computation.

DOI
10.1142/9789814287333_0014

Related papers

Colloquium : Quantum annealing and analog quantum computation

Arnab Das, Bikas K. Chakrabarti

The recent success in quantum annealing, i.e., optimization of the cost or energy functions of complex systems utilizing quantum fluctuations is reviewed here. The concept is introduced in successive steps through studying the mapping of such computationally hard problems to classical spin-glass problems, quantum spin-glass problems arising with the introduction of quantum fluctuations, and the annealing behavior of the systems as these fluctuations are reduced slowly to zero. This provides a general framework for realizing analog quantum computation.

arXiv:0801.2193•Reviews of Modern Physics•Sep 5, 2008•717 citations

Quantum Optimization of Fully Connected Spin Glasses

Davide Venturelli, Salvatore Mandrà, Sergey Knysh +3 more

Quantum computing promises to be more efficient and significantly faster than today's classical computing. Researchers compare the performance of a quantum annealer with that of classical algorithms for the first time on hard spin-glass problems.

arXiv:1406.7553•Physical Review X•Sep 18, 2015•227 citations

The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective

Victor Bapst, Laura Foini, Florent Krząkała +2 more

Among various algorithms designed to exploit the specific properties of quantum computers with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to find the minimal value of an arbitrary cost function (ground state energy). Random optimization problems provide a natural testbed to compare its efficiency with that of classical algorithms. These problems correspond to mean field spin glasses that have been extensively studied in the classical case. This paper reviews recent analytical works that extended these studies to incorporate the effect of quantum fluctuations, and presents also some original results in this direction.

•Oct 2, 2012•123 citations

Quantum Annealing of Hard Problems

Thomas Jörg, Florent Krząkała, Jorge Kurchan +1 more

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.

arXiv:0910.5644•Progress of Theoretical Physics Supplement•Jan 1, 2010•13 citations

Optimization Via Open System Quantum Annealing

Sergio Boixo, Robert F. Lucas, Daniel A. Lidar +2 more

Abstract : Many computationally challenging problems can be reduced to Quadratic Unconstrained Binary Optimization (QUBO), which can be solved by a quantum evolution from a strong transverse field to a spin glass Hamiltonian (also known as quantum annealing or QA). We have examined open system QA, using theoretical and experimental techniques to deepen our understanding of open system QA by situating it in the context of related, well studied classical and quantum problems. We have explored and elucidated the significance of tunneling in QA with Path Integral Monte Carlo. We have also provided signatures of quantum behavior of QA against closely related simulated annealing implementations, analytically, numerically, and experimentally. We have carried out a comprehensive comparison of geometrically-local open-system QA and classical solvers for computationally hard problems such as MAX-2-SAT. We have exploited and further developed a graph-theoretical mapping between the Ising spin glass partition function and circuit model decision problems, discovered in a previous ARO Quantum Algorithms funded project. We have made significant progress on error correction techniques for QA, both theoretically and experimentally, and in demonstration of quantum speedup.

•Jan 7, 2016•0 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•88 citations
We review here the recent success in annealing or optimizing the cost functions of complex systems utilizing quantum fluctuations rather than the classical (thermal) fluctuations. These are introduced through studies of mapping of such computationally hard problems to classical spin glass problems, quantum spin glasses and consequent annealing or analog quantum computation.
The recent success in quantum annealing, i.e., optimization of the cost or energy functions of complex systems utilizing quantum fluctuations is reviewed here. The concept is introduced in successive steps through studying the mapping of such computationally hard problems to classical spin-glass problems, quantum spin-glass problems arising with the introduction of quantum fluctuations, and the annealing behavior of the systems as these fluctuations are reduced slowly to zero. This provides a general framework for realizing analog quantum computation.
Among various algorithms designed to exploit the specific properties of quantum computers with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to find the minimal value of an arbitrary cost function (ground state energy). Random optimization problems provide a natural testbed to compare its efficiency with that of classical algorithms. These problems correspond to mean field spin glasses that have been extensively studied in the classical case. This paper reviews recent analytical works that extended these studies to incorporate the effect of quantum fluctuations, and presents also some original results in this direction.
Abstract : Many computationally challenging problems can be reduced to Quadratic Unconstrained Binary Optimization (QUBO), which can be solved by a quantum evolution from a strong transverse field to a spin glass Hamiltonian (also known as quantum annealing or QA). We have examined open system QA, using theoretical and experimental techniques to deepen our understanding of open system QA by situating it in the context of related, well studied classical and quantum problems. We have explored and elucidated the significance of tunneling in QA with Path Integral Monte Carlo. We have also provided signatures of quantum behavior of QA against closely related simulated annealing implementations, analytically, numerically, and experimentally. We have carried out a comprehensive comparison of geometrically-local open-system QA and classical solvers for computationally hard problems such as MAX-2-SAT. We have exploited and further developed a graph-theoretical mapping between the Ising spin glass partition function and circuit model decision problems, discovered in a previous ARO Quantum Algorithms funded project. We have made significant progress on error correction techniques for QA, both theoretically and experimentally, and in demonstration of quantum speedup.
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.