Finding optimal solutions by stochastic cellular automata

arXiv1906.06645MaRDI QIDQ6320558FDOQ6320558

Authors: Satoshi Handa, Katsuhiro Kamakura, Yoshinori Kamijima, Akira Sakai 

Publication date: 16 June 2019

Abstract: Finding a ground state of a given Hamiltonian is an important but hard problem. One of the potential methods is to use a Markov chain Monte Carlo (MCMC) to sample the Gibbs distribution whose highest peaks correspond to the ground states. In this short paper, we use stochastic cellular automata (SCA) and see if it is possible to find a ground state faster than the conventional MCMCs, such as the Glauber dynamics. We show that, if the temperature is sufficiently high, it is possible for SCA to have more spin-flips per update in average than Glauber and, at the same time, to have an equilibrium distribution ``close" to the one for Glauber, i.e., the Gibbs distribution. During the course, we also propose a new way to characterize how close a probability measure is to the target Gibbs.

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Combinatorial optimization (90C27) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Monte Carlo methods applied to problems in optics and electromagnetic theory (78M31)

This page was built for publication: Finding optimal solutions by stochastic cellular automata

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