Degeneracy, degree, and heavy tails in quantum annealing

Understand

Both simulated quantum annealing and physical quantum annealing have shown the emergence of "heavy tails" in their performance as optimizers: The total time needed to solve a set of random input instances is dominated by a small number of very hard instances.

• Classical simulated annealing, in contrast, does not show such heavy tails.
• Here we explore the origin of these heavy tails, which appear for inputs with high local degeneracy---large isoenergetic clusters of states in Hamming space.
• This category includes the low-precision Chimera-structured problems studied in recent benchmarking work comparing the D-Wave Two quantum annealing processor with simulated annealing.