Overcoming the slowing down of flat-histogram Monte Carlo simulations: Cluster updates and optimized broad-histogram ensembles

We study the performance of Monte Carlo simulations that sample a broad histogram in energy by determining the mean first-passage time to span the entire energy space of $d$-dimensional ferromagnetic Ising/Potts models. We first show that flat-histogram Monte Carlo methods with single-spin flip updates such as the Wang-Landau algorithm or the multicanonical method perform suboptimally in comparison to an unbiased Markovian random walk in energy space. For the $d=1$, 2, 3 Ising model, the mean first-passage time $\ensuremath{\tau}$ scales with the number of spins $N={L}^{d}$ as $\ensuremath{\tau}\ensuremath{\propto}{N}^{2}{L}^{z}$. The exponent $z$ is found to decrease as the dimensionality $d$ is increased. In the mean-field limit of infinite dimensions we find that $z$ vanishes up to logarithmic corrections. We then demonstrate how the slowdown characterized by $zg0$ for finite $d$ can be overcome by two complementary approaches\char22{}cluster dynamics in connection with Wang-Landau sampling and the recently developed ensemble optimization technique. Both approaches are found to improve the random walk in energy space so that $\ensuremath{\tau}\ensuremath{\propto}{N}^{2}$ up to logarithmic corrections for the $d=1$, 2 Ising model.