Ferromagnetically shifting the power of pausing

Abstract

We study the interplay between quantum annealing parameters in embedded problems, providing both deeper insights into the physics of these devices and pragmatic recommendations to improve performance on optimization problems. We choose as our test case the class of degree-bounded minimum spanning tree problems. Through runs on a D-Wave quantum annealer, we demonstrate that pausing in a specific time window in the anneal provides improvement in the probability of success and in the time-to-solution for these problems. The time window is consistent across problem instances, and its location is within the region suggested by prior theory and seen in previous results on native problems. An approach to enable gauge transformations for problems with the qubit coupling strength $J$ in an asymmetric range is presented and shown to significantly improve performance. We also confirm that the optimal pause location exhibits a shift with the magnitude of the ferromagnetic coupling, $|J_F|$, between physical qubits representing the same logical one. We extend the theoretical picture for pausing and thermalization in quantum annealing to the embedded case. This picture, along with perturbation theory analysis, and exact numerical results on small problems, confirms that the effective pause region moves earlier in the anneal as $|J_F|$ increases. It also suggests why pausing, while still providing significant benefit, has a less pronounced effect on embedded problems.

arXiv comment22 pages, 14 figures

References in corpus (17)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum annealing with more than one hundred qubits
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Defining and detecting quantum speedup
• Experimental signature of programmable quantum annealing
• A case study in programming a quantum annealer for hard operational planning problems
• Quantum Optimization of Fully-Connected Spin Glasses
• Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Low-Degree Spanning Trees of Small Weight
• Why and when is pausing beneficial in quantum annealing?
• Comparing relaxation mechanisms in quantum and classical transverse-field annealing
• The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
• Perils of Embedding for Sampling Problems

Cited by in corpus (12)

• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Optimal quantum annealing: A variational shortcut to adiabaticity approach
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Simulation of adiabatic quantum computing for molecular ground states
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Counterdiabatic Reverse Annealing
• Deep learning optimal quantum annealing schedules for random Ising models
• Advantage of pausing: parameter setting for quantum annealers
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Demonstration of error-suppressed quantum annealing via boundary cancellation
• Noise Effects on Diabatic Quantum Annealing Protocols