Portal de Periódicos da CAPES

Heavy Tails in the Distribution of Time to Solution for Classical and Quantum Annealing

2015; American Physical Society; Volume: 115; Issue: 23 Linguagem: Inglês

10.1103/physrevlett.115.230501

1092-0145

Damian S. Steiger, Troels F. Rønnow, Matthias Troyer,

Quantum many-body systems

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.