title: Accelerated stochastic sampling of discrete statistical systems.
abstract: We propose a method to reduce the relaxation time toward equilibrium in stochastic sampling of complex energy landscapes in statistical systems with discrete degrees of freedom by generalizing the platform previously developed for continuous systems. The method starts from a master equation, in contrast to the Fokker-Planck equation for the continuous case. The master equation is transformed into an imaginary-time Schrödinger equation. The Hamiltonian of the Schrödinger equation is modified by adding a projector to its known ground state. We show how this transformation decreases the relaxation time and propose a way to use it to accelerate simulated annealing for optimization problems. We implement our method in a simplified kinetic Monte Carlo scheme and show acceleration by one order of magnitude in simulated annealing of the symmetric traveling salesman problem. Comparisons of simulated annealing are made with the exchange Monte Carlo algorithm for the three-dimensional Ising spin glass. Our implementation can be seen as a step toward accelerating the stochastic sampling of generic systems with complex landscapes and long equilibration times.
authors.affiliation: Department of Physics, Tokyo Institute of Technology, Oh-okayama, Meguro-ku, Tokyo 152-8551, Japan. zsolt@stat.phys.titech.ac.jp
authors.forename: Zsolt
authors.initials: Z
authors.lastname: Bertalan
authors.forename: Hidetoshi
authors.initials: H
authors.lastname: Nishimori
authors.forename: Henri
authors.initials: H
authors.lastname: Orland