Degeneracy, degree, and heavy tails in quantum annealing
arXiv:1512.07325 · doi:10.1103/PhysRevA.93.052320
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.
arXiv comment14 pages. Corrected annealing schedule and dependent simulations
References in corpus (31)
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Defining and detecting quantum speedup
- Architectural considerations in the design of a superconducting quantum annealing processor
- Experimental signature of programmable quantum annealing
- Anderson localization casts clouds over adiabatic quantum optimization
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- A case study in programming a quantum annealer for hard operational planning problems
- Quantum Optimization of Fully-Connected Spin Glasses
- First order phase transition in the Quantum Adiabatic Algorithm
- Probing for quantum speedup in spin glass problems with planted solutions
- Optimized simulated annealing for Ising spin glasses
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Quantum Annealing Implementation of Job-Shop Scheduling
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- 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
- Quiet Planting in the Locked Constraint Satisfaction Problems
- Algorithmic approach to adiabatic quantum optimization
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- Effect of Local Minima on Adiabatic Quantum Optimization
- Construction of Energy Functions for Lattice Heteropolymer Models: A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization
- Elimination of Perturbative Crossings in 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