Initial State Encoding via Reverse Quantum Annealing and h-gain Features

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 paper, 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 allowing one to encode such an initial state: the reverse annealing and the h-gain features. Reverse annealing (RA) aims to refine a known solution following an anneal path starting with a classical state representing a good solution, going backwards to a point where a transverse field is present, and then finishing the annealing process with a forward anneal. The h-gain (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 encoding on random whole-chip spin glasses with the native hardware connectivity of the D-Wave Chimera and Pegasus chips.

arXiv commentarXiv admin note: substantial text overlap with arXiv:2009.05008

References in corpus (44)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Approximate Optimization Algorithm
• Quantum annealing with more than one hundred qubits
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Annealing and Analog Quantum Computation
• Quantum Computation by Adiabatic Evolution
• Perspectives of quantum annealing: Methods and implementations
• Mathematical Foundation of Quantum Annealing
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Experimental signature of programmable quantum annealing
• Warm-starting quantum optimization
• A practical heuristic for finding graph minors
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Coherent quantum annealing in a programmable 2000-qubit Ising chain
• Entanglement in a quantum annealing processor
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Scaling advantage in quantum simulation of geometrically frustrated magnets
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Reverse annealing for the fully connected $p$-spin model
• Modernizing Quantum Annealing using Local Searches
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Benchmarking Quantum Annealing Controls with Portfolio Optimization
• Pegasus: The second connectivity graph for large-scale quantum annealing hardware
• Reverse quantum annealing of the $p$-spin model with relaxation
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Reverse Annealing for Nonnegative/Binary Matrix Factorization
• Quantum annealing with longitudinal bias fields
• Simulating the Shastry-Sutherland Ising Model using Quantum Annealing
• Why and when is pausing beneficial in quantum annealing?
• Quantum annealing simulation of out-of-equilibrium magnetization in a spin-chain compound
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
• Kagome qubit ice
• On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Embedding of Complete Graphs in Broken Chimera Graphs
• Breakdown of the weak coupling limit in quantum annealing
• Exploring Quantum Annealing Architectures: A Spin Glass Perspective
• Erratum: Glassy Chimeras Could Be Blind to Quantum Speedup. . . [Phys. Rev. X 4, 021008 (2014)]
• The QAOA gets stuck starting from a good classical string

Cited by in corpus (5)

• Quantum annealer accelerates the variational quantum eigensolver in a triple-hybrid algorithm
• Reverse quantum annealing assisted by forward annealing
• Learning-Driven Annealing with Adaptive Hamiltonian Modification for Solving Large-Scale Problems on Quantum Devices
• Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems
• Operator dependence and robustness of spacetime-localized response in a quantum critical spin chain