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. On similar inputs designed to suppress local degeneracy, performance of a quantum annealing processor on hard instances improves by orders of magnitude at the 512-qubit scale, while classical performance remains relatively unchanged. Simulations indicate that perturbative crossings are the primary factor contributing to these heavy tails, while sensitivity to Hamiltonian misspecification error plays a less significant role in this particular setting.
Distribution of hardness for odd parity U  and even parity U  instances on 127 qubits (C4). (Top) Results for U  instances show comparable tails at large R (low success probability) for DW2X and SA. For U  instances, the DW2X results show the same characteristic heavy tail seen for SQA, whereas SA (210 sweeps) shows no such tail. (Bottom) We visualize these data with R on the y-axis. DW2X performance is highly dependent on degree. For U  instances, DW2X and SA cross near the median, while for U  instances DW2X dominates throughout the distribution.
A testbed consisted of random U1 and U4 Ising instances on Chimera subgrids of varying size, from 3 × 3 unit cells (C3) to 10 × 10 unit cells (C10). These problems contain between 72 and 765 operable qubits. For each problem size, range k, and target degree d, they constructed 1000 U d k instances, each on a newly generated subgraph with target degree d.