Heavy tails in the distribution of time-to-solution for classical and quantum annealing

Abstract

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.

References in corpus (8)

• Feedback-optimized parallel tempering Monte Carlo
• Performance Limitations of Flat Histogram Methods and Optimality of Wang-Landau Sampling
• Reexamining classical and quantum models for the D-Wave One processor
• Universality-class dependence of energy distributions in spin glasses
• Probing tails of energy distributions using importance-sampling in the disorder with a guiding function
• Dynamics of the Wang-Landau algorithm and complexity of rare events for the three-dimensional bimodal Ising spin glass
• Extreme-Value Distributions and the Freezing Transition of Structural Glasses
• Typical versus average helicity modulus in the three-dimensional gauge glass: Understanding the vortex glass phase

Cited by in corpus (31)

• Quantum information processing with superconducting circuits: a review
• First Passage Under Restart
• Optimal stochastic restart renders fluctuations in first passage times universal
• What is the Computational Value of Finite Range Tunneling?
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Diffusion with resetting in a logarithmic potential
• Training A Quantum Optimizer
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Benchmarking a quantum annealing processor with the time-to-target metric
• Benchmarking Quantum Annealing Controls with Portfolio Optimization
• Invariants of motion with stochastic resetting and space-time coupled returns
• Stochastic resetting by a random amplitude
• Space-dependent diffusion with stochastic resetting: A first-passage study
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• Mean-performance of sharp restart I: Statistical roadmap
• Mitigating long queues and waiting times with service resetting
• Diffusion with Local Resetting and Exclusion
• Schedule path optimization for quantum annealing and adiabatic quantum computing
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Degeneracy, degree, and heavy tails in quantum annealing
• Application of Pontryagin's Minimum Principle to Grover's Quantum Search Problem
• Tail-behavior roadmap for sharp restart
• Fluctuation guided search in quantum annealing
• Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model
• Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
• Pulsed quantum annealing
• Tensor network method for reversible classical computation
• Benchmarking Embedded Chain Breaking in Quantum Annealing
• Topological and geometric patterns in optimal bang-bang protocols for variational quantum algorithms: application to the $XXZ$ model on the square lattice
• Machine learning in physics: The pitfalls of poisoned training sets