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

Re‘class’ification of ‘quant’ified classical simulated annealing

Published Nov 20, 2012• 0 citations
OpenAlex

Abstract

Abstract. We discuss a classical reinterpretation of quantum-mechanics-based analysis of classical Markov chains with detailed balance, that is based on the quantum-classical correspondence. The classical reinterpretation is then used to demonstrate that it successfully reproduces a sufficient condition for cooling schedule in classical simulated annealing, which has the inverse-logarithm scaling. 1.

Related papers

Re'class'ification of 'quant'ified classical simulated annealing

Toshiyuki Tanaka

We discuss a classical reinterpretation of quantum-mechanics-based analysis of classical Markov chains with detailed balance, that is based on the quantum-classical correspondence. The classical reinterpretation is then used to demonstrate that it successfully reproduces a sufficient condition for cooling schedule in classical simulated annealing, which has the inverse-logarithmic scaling.

arXiv:0810.0557•Journal of Physics Conference Series•Jan 7, 2009•0 citations

Quantum Simulated Annealing

Somma, R., Boixo, S., Howard Barnum

We develop a quantum algorithm to solve combinatorial optimization problems through quantum simulation of a classical annealing process. Our algorithm combines techniques from quantum walks, quantum phase estimation, and quantum Zeno effect. It can be viewed as a quantum analogue of the discrete-time Markov chain Monte Carlo implementation of classical simulated annealing. Our implementation scales with the inverse of the square root of the minimum spectral gap of the stochastic matrix used in the classical simulation. The quantum algorithm outperforms the classical one, which scales with the inverse of the gap.

arXiv:0712.1008•Dec 6, 2007•19 citations

Statistical Analysis of Quantum Annealing

Xinyu Song, Yazhen Wang, Shang Wu +1 more

Quantum computers use quantum resources to carry out computational tasks and may outperform classical computers in solving certain computational problems. Special-purpose quantum computers such as quantum annealers employ quantum adiabatic theorem to solve combinatorial optimization problems. In this paper, we compare classical annealings such as simulated annealing and quantum annealings that are done by the D-Wave machines both theoretically and numerically. We show that if the classical and quantum annealing are characterized by equivalent Ising models, then solving an optimization problem, i.e., finding the minimal energy of each Ising model, by the two annealing procedures, are mathematically identical. For quantum annealing, we also derive the probability lower-bound on successfully solving an optimization problem by measuring the system at the end of the annealing procedure. Moreover, we present the Markov chain Monte Carlo (MCMC) method to realize quantum annealing by classical computers and investigate its statistical properties. In the numerical section, we discuss the discrepancies between the MCMC based annealing approaches and the quantum annealing approach in solving optimization problems.

arXiv:2101.06854•Jan 18, 2021•0 citations

Comparing Relaxation Mechanisms in Quantum and Classical Transverse-Field Annealing

Tameem Albash, Jeffrey Marshall

Annealing schedule control provides opportunities to better understand the manner and mechanisms by which putative quantum annealers operate. By appropriately modifying the annealing schedule to include a pause (keeping the Hamiltonian fixed) for a period of time, we show that it is possible to more directly probe the dissipative dynamics of the system at intermediate points along the anneal and examine thermal relaxation rates, for example, by observing the repopulation of the ground state after the minimum spectral gap. We provide a detailed comparison of experiments from a D-Wave device, simulations of the quantum adiabatic master equation, and a classical analogue of quantum annealing, spin-vector Monte Carlo, and we observe qualitative agreement, showing that the characteristic increase in success probability when pausing is not a uniquely quantum phenomena. We find that the relaxation in our system is dominated by a single timescale, which allows us to give a simple condition for when we can expect pausing to improve the time to solution, the relevant metric for classical optimization. Finally, we also explore in simulation the role of temperature whilst pausing as a means to better distinguish quantum and classical models of quantum annealers.

arXiv:2009.04934•Physical Review Applied•Jan 19, 2021•31 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 algorithms for simulated annealing

Sergio Boixo, Rolando D. Somma

This paper summarizes a quantum algorithm of [R.D. Somma, et.al., Phys. Rev. Lett. 101, 130504 (2008)] that simulates a classical annealing process for solving discrete optimization problems. The complexity of the quantum algorithm scales with the inverse square root of the spectral gap of an associated stochastic matrix. This represents a quadratic quantum speedup, in terms of the gap, with respect to classical simulated annealing.

arXiv:1512.03806•Dec 11, 2015•0 citations
Abstract. We discuss a classical reinterpretation of quantum-mechanics-based analysis of classical Markov chains with detailed balance, that is based on the quantum-classical correspondence. The classical reinterpretation is then used to demonstrate that it successfully reproduces a sufficient condition for cooling schedule in classical simulated annealing, which has the inverse-logarithm scaling. 1.
We develop a quantum algorithm to solve combinatorial optimization problems through quantum simulation of a classical annealing process. Our algorithm combines techniques from quantum walks, quantum phase estimation, and quantum Zeno effect. It can be viewed as a quantum analogue of the discrete-time Markov chain Monte Carlo implementation of classical simulated annealing. Our implementation scales with the inverse of the square root of the minimum spectral gap of the stochastic matrix used in the classical simulation. The quantum algorithm outperforms the classical one, which scales with the inverse of the gap.
Quantum computers use quantum resources to carry out computational tasks and may outperform classical computers in solving certain computational problems. Special-purpose quantum computers such as quantum annealers employ quantum adiabatic theorem to solve combinatorial optimization problems. In this paper, we compare classical annealings such as simulated annealing and quantum annealings that are done by the D-Wave machines both theoretically and numerically. We show that if the classical and quantum annealing are characterized by equivalent Ising models, then solving an optimization problem, i.e., finding the minimal energy of each Ising model, by the two annealing procedures, are mathematically identical. For quantum annealing, we also derive the probability lower-bound on successfully solving an optimization problem by measuring the system at the end of the annealing procedure. Moreover, we present the Markov chain Monte Carlo (MCMC) method to realize quantum annealing by classical computers and investigate its statistical properties. In the numerical section, we discuss the discrepancies between the MCMC based annealing approaches and the quantum annealing approach in solving optimization problems.
Annealing schedule control provides opportunities to better understand the manner and mechanisms by which putative quantum annealers operate. By appropriately modifying the annealing schedule to include a pause (keeping the Hamiltonian fixed) for a period of time, we show that it is possible to more directly probe the dissipative dynamics of the system at intermediate points along the anneal and examine thermal relaxation rates, for example, by observing the repopulation of the ground state after the minimum spectral gap. We provide a detailed comparison of experiments from a D-Wave device, simulations of the quantum adiabatic master equation, and a classical analogue of quantum annealing, spin-vector Monte Carlo, and we observe qualitative agreement, showing that the characteristic increase in success probability when pausing is not a uniquely quantum phenomena. We find that the relaxation in our system is dominated by a single timescale, which allows us to give a simple condition for when we can expect pausing to improve the time to solution, the relevant metric for classical optimization. Finally, we also explore in simulation the role of temperature whilst pausing as a means to better distinguish quantum and classical models of quantum annealers.
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.