Reverse quantum annealing assisted by forward annealing
arXiv:2408.13603 · doi:10.3390/quantum6030030
Abstract
Quantum annealers conventionally use forward annealing to generate heuristic solutions. Reverse annealing can potentially generate better solutions but necessitates an appropriate initial state. Ways to find such states are generally unknown or highly problem dependent, offer limited success, and severely restrict the scope of reverse annealing. We use a general method that improves the overall solution quality and quantity by feeding reverse annealing with low-quality solutions obtained from forward annealing. An experimental demonstration of solving the graph coloring problem using the D-Wave quantum annealers shows that our method is able to convert invalid solutions obtained from forward annealing to at least one valid solution obtained after assisted reverse annealing for of random Erdős-Rényi graphs. Our method significantly outperforms random initial states, obtains more unique solutions on average, and widens the applicability of reverse annealing. Although the average number of valid solutions obtained drops exponentially with the problem size, a scaling analysis for the graph coloring problem shows that our method effectively extends the computational reach of conventional forward annealing using reverse annealing.
References in corpus (26)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- The theory of variational hybrid quantum-classical algorithms
- Trapped-Ion Quantum Computing: Progress and Challenges
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Observation of topological phenomena in a programmable lattice of 1,800 qubits
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Application of Quantum Annealing to Nurse Scheduling Problem
- Quantum annealing with antiferromagnetic fluctuations
- Reverse annealing for the fully connected -spin model
- Modernizing Quantum Annealing using Local Searches
- Dynamics of reverse annealing for the fully-connected -spin model
- Qubit spin ice
- Reverse Annealing for Nonnegative/Binary Matrix Factorization
- Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
- Travel time optimization on multi-AGV routing by reverse annealing
- Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
- Breakdown of the weak coupling limit in quantum annealing
- Improved variational quantum eigensolver via quasi-dynamical evolution
- Efficiency Optimization in Quantum Computing: Balancing Thermodynamics and Computational Performance
- Initial State Encoding via Reverse Quantum Annealing and h-gain Features
- Quantum annealer accelerates the variational quantum eigensolver in a triple-hybrid algorithm