Finding a ground state of a given Hamiltonian of an Ising model on a graph
$G=(V,E)$ is an important but hard problem. The standard approach for this kind
of problem is the application of algorithms that rely on single-spin-flip
Markov chain Monte Carlo methods, such as the simulated annealing based on
Glauber or Metropolis dynamics. In this paper, we investigate a particular kind
of stochastic cellular automata, in which all spins are updated independently
and simultaneously. We prove that (i) if the temperature is fixed sufficiently
high, then the mixing time is at most of order $\log|V|$, and that (ii) if the
temperature drops in time $n$ as $1/\log n$, then the limiting measure is
uniformly distributed over the ground states. We also provide some simulations
of the algorithms studied in this paper implemented on a GPU and show their
superior performance compared to the conventional simulated annealing.
