Degeneracy, degree, and heavy tails in quantum annealing

Abstract

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.

14 pages. Corrected annealing schedule and dependent simulations

References in corpus (15)

• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Probing for quantum speedup in spin glass problems with planted solutions
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Quantum Annealing Implementation of Job-Shop Scheduling
• Reexamining classical and quantum models for the D-Wave One processor
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Benchmarking a quantum annealing processor with the time-to-target metric
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Unraveling Quantum Annealers using Classical Hardness
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Heavy tails in the distribution of time-to-solution for classical and quantum annealing
• Effect of Local Minima on Adiabatic Quantum Optimization

Cited by in corpus (19)

• Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
• Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
• Dissipation in adiabatic quantum computers: Lessons from an exactly solvable model
• Global warming: Temperature estimation in annealers
• Uncertain fate of fair sampling in quantum annealing
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• Improving performance of logical qubits by parameter tuning and topology compensation
• Fair sampling of ground-state configurations of binary optimization problems
• Achieving fair sampling in quantum annealing
• A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
• Fluctuation guided search in quantum annealing
• Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model
• Feeding the multitude: A polynomial-time algorithm to improve sampling
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• Bounding first-order quantum phase transitions in adiabatic quantum computing
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
• Optimizing embedding-related quantum annealing parameters for reducing hardware bias
• Observation of Magnetic Devil's Staircase-Like Behavior in Quasiperiodic Qubit Lattices
• Reducing quantum annealing biases for solving the graph partitioning problem