Dynamics of the Wang-Landau algorithm and complexity of rare events for the three-dimensional bimodal Ising spin glass

We investigate the performance of flat-histogram methods based on a multicanonical ensemble and the Wang-Landau algorithm for the three-dimensional +/-J spin glass by measuring round-trip times in the energy range between the zero-temperature ground state and the state of highest energy. Strong sample-to-sample variations are found for fixed system size and the distribution of round-trip times follows a fat-tailed Frechet extremal value distribution. Rare events in the fat tails of these distributions corresponding to extremely slowly equilibrating spin glass realizations dominate the calculations of statistical averages. While the typical round-trip times scale exponentially as expected for this NP-hard problem, we find that the average round-trip time is no longer well defined for systems with N greater than or equal to 8(3) spins. We relate the round-trip times for multicanonical sampling to intrinsic properties of the energy landscape and compare with the numerical effort needed by the genetic cluster-exact approximation to calculate the exact ground-state energies. For systems with N greater than or equal to 8(3) spins the simulation of these rare events becomes increasingly hard. For N greater than or equal to 14(3) there are samples where the Wang-Landau algorithm fails to find the true ground state within reasonable simulation times. We expect similar behaviour for other algorithms based on multicanonical sampling.