Initial State Encoding via Reverse Quantum Annealing and H-Gain Features
Open Access
- 27 September 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 4, 1-21
Abstract
Quantum annealing is a specialized type of quantum computation that aims to use quantum fluctuations in order to obtain global minimum solutions of combinatorial optimization problems. Programmable D-Wave quantum annealers are available as cloud computing resources, which allow users low-level access to quantum annealing control features. In this article, we are interested in improving the quality of the solutions returned by a quantum annealer by encoding an initial state into the annealing process. We explore two D-Wave features that allow one to encode such an initial state: the reverse annealing (RA) and the h-gain (HG) features. RA aims to refine a known solution following an anneal path starting with a classical state representing a good solution, going backward to a point where a transverse field is present, and then finishing the annealing process with a forward anneal. The HG feature allows one to put a time-dependent weighting scheme on linear ( $h$ ) biases of the Hamiltonian, and we demonstrate that this feature likewise can be used to bias the annealing to start from an initial state. We also consider a hybrid method consisting of a backward phase resembling RA and a forward phase using the HG initial state encoding. Importantly, we investigate the idea of iteratively applying RA and HG to a problem, with the goal of monotonically improving on an initial state that is not optimal. The HG encoding technique is evaluated on a variety of input problems including the edge-weighted maximum cut problem and the vertex-weighted maximum clique problem, demonstrating that the HG technique is a viable alternative to RA for some problems. We also investigate how the iterative procedures perform for both RA and HG initial state encodings on random whole-chip spin glasses with the native hardware connectivity of the D-Wave Chimera and Pegasus chips.Keywords
All Related Versions
Funding Information
- U.S. Department of Energy
- Los Alamos National Laboratory
- Laboratory Directed Research and Development Program of LANL (20220656ER)
- National Nuclear Security Administration's (NNSA) Advanced Simulation and Computing Beyond Moore's Law Program at LANL
- LANL Institutional Computing Program
- U.S. Department of Energy National Nuclear Security Administration (89233218CNA000001)
- LANL is operated by Triad National Security, LLC
- National Nuclear Security Administration
- U.S. Department of Energy (89233218CNA000001)
- Bulgarian National Science Fund (KP-06-DB-11)
- Cure Alzheimer's Fund of the National Institutes of Health (1R01 AI 154470-01, 2U01 HG 008685, R21 HD 095228 008976, U01 HL 089856, U01 HL 089897, P01 HL 120839, P01 HL 132825, 2U01 HG 008685, R21 HD 095228, P01HL132825)
- National Science Foundation (NSF PHY 2033046, NSF GRFP 1745302)
- National Institutes of Health (P30-ES002109)
This publication has 50 references indexed in Scilit:
- Glassy Chimeras Could Be Blind to Quantum Speedup: Designing Better Benchmarks for Quantum Annealing MachinesPhysical Review X, 2014
- Evidence for quantum annealing with more than one hundred qubitsNature Physics, 2014
- Ising formulations of many NP problemsFrontiers in Physics, 2014
- Experimental signature of programmable quantum annealingNature Communications, 2013
- Quantum annealing with manufactured spinsNature, 2011
- A study of heuristic guesses for adiabatic quantum computationQuantum Information Processing, 2010
- Mathematical foundation of quantum annealingJournal of Mathematical Physics, 2008
- Colloquium: Quantum annealing and analog quantum computationReviews of Modern Physics, 2008
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- On Bayesian Methods for Seeking the Extremum1975