Ferromagnetically Shifting the Power of Pausing
- 6 April 2021
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Applied
- Vol. 15 (4) , 044013
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 bounded-degree 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 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, , 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 increases. It also suggests why pausing, while still providing significant benefit, has a less pronounced effect on embedded problems.
Keywords
All Related Versions
Funding Information
- Air Force Research Laboratory (F4HBKC4162G001)
- Office of the Director of National Intelligence
- Intelligence Advanced Research Projects Activity
This publication has 25 references indexed in Scilit:
- Degree-bounded minimum spanning treesDiscrete Applied Mathematics, 2009
- A local search heuristic for bounded-degree minimum spanning treesEngineering Optimization, 2008
- Minor-embedding in adiabatic quantum computation: I. The parameter setting problemQuantum Information Processing, 2008
- Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising modelPhysical Review B, 2002
- Theory of Quantum Annealing of an Ising Spin GlassScience, 2002
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete ProblemScience, 2001
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Low-Degree Spanning Trees of Small WeightSIAM Journal on Computing, 1996
- Quantum annealing: A new method for minimizing multidimensional functionsChemical Physics Letters, 1994
- Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuationsPhysical Review B, 1989