Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
arXiv:2308.10765 · doi:10.7566/JPSJ.93.034001
Abstract
The demand for classical-quantum hybrid algorithms to solve large-scale combinatorial optimization problems using quantum annealing (QA) has increased. One approach involves obtaining an approximate solution using classical algorithms and refining it using QA. In previous studies, such variables were determined using molecular dynamics (MD) as a continuous optimization method. We propose a method that uses the simple continuous relaxation technique called linear programming (LP) relaxation. Our method demonstrated superiority through comparative experiments with the minimum vertex cover problem versus the previous MD-based approach. Furthermore, the hybrid approach of LP relaxation and simulated annealing showed advantages in accuracy and speed compared to solving with simulated annealing alone.
8 pages, 5 figures
References in corpus (9)
- Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
- Quantum Annealing for Combinatorial Clustering
- Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
- Item Listing Optimization for E-commerce Websites based on Diversity
- Travel time optimization on multi-AGV routing by reverse annealing
- Fair Sampling by Simulated Annealing on Quantum Annealer
- Comparing the effects of Boltzmann machines as associative memory in Generative Adversarial Networks between classical and quantum sampling
- Virtual Screening of Chemical Space based on Quantum Annealing
- Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing