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.
arXiv comment8 pages, 5 figures
References in corpus (28)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Quantum Boltzmann Machine
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
- A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Quantum Variational Autoencoder
- Nonnegative/binary matrix factorization with a D-Wave quantum annealer
- Quantum Annealing for Combinatorial Clustering
- Traffic Signal Optimization on a Square Lattice with Quantum Annealing
- Modernizing Quantum Annealing using Local Searches
- Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
- Forecasting financial crashes with quantum computing
- Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
- Residual Energies after Slow Quantum Annealing
- Item Listing Optimization for E-commerce Websites based on Diversity
- Travel time optimization on multi-AGV routing by reverse annealing
- Benchmark test of Black-box optimization using D-Wave quantum annealer
- Implementation of a Hybrid Classical-Quantum Annealing Algorithm for Logistic Network Design
- Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
- Hybrid Quantum Annealing via Molecular Dynamics
- 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
- Teacher-student learning for a binary perceptron with quantum fluctuations
- Virtual Screening of Chemical Space based on Quantum Annealing
- Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
- Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems