  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 time scales
exponential as expected for this NP-hard problem, we find that the average
round-trip time is no longer well-defined for systems with N >= 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 >= 8^3 spins the simulation of these rare events
becomes increasingly hard. For N >= 14^3 there are samples where the
Wang-Landau algorithm fails to find the true ground state within reasonable
simulation times. We expect similar behavior for other algorithms based on
multicanonical sampling.
