Mathematical aspects of the Digital Annealer's simulated annealing algorithm

DOI10.1007/S10955-023-03179-3MaRDI QIDQ6140923zbMATH OpenOpenAlexFDO

Authors Bruno Hideki Fukushima-Kimura, Noe Kawamoto, Eitaro Noda, Akira Sakai

Publication date 2 January 2024

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.08392

zbMATH Keywords

combinatorial optimizationDigital Annealerground statesIsing modelQUBOsimulated annealingstochastic optimization

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: The Digital Annealer is a quantum-inspired CMOS hardware designed by Fujitsu Laboratories for high-speed solving Quadratic Unconstrained Binary Optimization (QUBO) problems that could be difficult to solve by means of existing general-purpose computers. In this paper, we present a mathematical description of the first-generation Digital Annealer's Algorithm from the Markov chain theory perspective, establish a relationship between its stationary distribution with the Gibbs-Boltzmann distribution, and provide a necessary and sufficient condition on its cooling schedule that ensures asymptotic convergence to the ground states.

Recommendations

• Quantum annealing of hard problems
• The mathematics of quantum-enabled applications on the D-wave quantum computer
• An introduction to quantum annealing
• Mathematical foundation of quantum annealing
• Quantum annealing versus digital computing. An experimental comparison

Cites work

• \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems
• Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems
• Convergence and finite-time behavior of simulated annealing
• Convergence of an annealing algorithm
• Cooling Schedules for Optimal Annealing
• Equation of state calculations by fast computing machines
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 4048925 (Why is no real title available?)
• scientific article; zbMATH DE number 41891 (Why is no real title available?)
• scientific article; zbMATH DE number 193510 (Why is no real title available?)
• scientific article; zbMATH DE number 3519671 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Mixing time and simulated annealing for the stochastic cellular automata
• Non-negative matrices and Markov chains.
• Optimization by simulated annealing
• Piecewise constant triangular cooling schedules for generalized simulated annealing algorithms
• Random Perturbations of Dynamical Systems
• Rough large deviation estimates for simulated annealing: Application to exponential schedules
• Sharp large deviations estimates for simulated annealing algorithms
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm

Cited in

(1)

• Ising Machines for Diophantine Problems in Physics

This page was built for publication: Mathematical aspects of the Digital Annealer's simulated annealing algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6140923)