  For many optimization algorithms the time-to-solution depends not only on the
problem size but also on the specific problem instance and may vary by many
orders of magnitude. It is then necessary to investigate the full distribution
and especially its tail. Here we analyze the distributions of annealing times
for simulated annealing and simulated quantum annealing (by path integral
quantum Monte Carlo) for random Ising spin glass instances. We find power-law
distributions with very heavy tails, corresponding to extremely hard instances,
but far broader distributions - and thus worse performance for hard instances -
for simulated quantum annealing than for simulated annealing. Fast,
non-adiabatic, annealing schedules can improve the performance of simulated
quantum annealing for very hard instances by many orders of magnitude.
