Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
arXiv:2307.05966 · doi:10.7566/JPSJ.92.113002
Abstract
We propose an efficient algorithm that combines column generation and quantum annealing to solve binary quadratic problems. Binary quadratic problems are difficult to solve because they are NP-hard. An attempt to solve binary quadratic problems efficiently by column generation has been studied, but it demands successively solving quadratic unconstrained binary optimization problems. We solve the bottleneck by using quantum annealing or simulated annealing. Our results demonstrate a good approximate solution obtained in 2.7 to 1000 times shorter computational time to use column generation and quantum annealing to solve binary quadratic problems than the existing fast solver.
arXiv comment5 pages, 3 figures, 1 Table
References in corpus (25)
- Quantum Annealing in the Transverse Ising Model
- Quantum Boltzmann Machine
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Coherent quantum annealing in a programmable 2000-qubit Ising chain
- 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
- Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
- Quantum Annealing for Combinatorial Clustering
- Traffic Signal Optimization on a Square Lattice with Quantum Annealing
- Forecasting financial crashes with quantum computing
- Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
- 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
- Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
- Fair Sampling by Simulated Annealing on Quantum Annealer
- Quantum pricing-based column-generation framework for hard combinatorial problems
- 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
- Teacher-student learning for a binary perceptron with quantum fluctuations
- L_1-regularized Boltzmann machine learning using majorizer minimization
Cited by in corpus (8)
- Annealing-Assisted Column Generation for Inequality-Constrained Combinatorial Optimization Problems
- Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing
- Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
- Impact of Fixing Spins in a Quantum Annealer with Energy Rescaling
- Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems
- Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing
- Leveraging Analog Neutral Atom Quantum Computers for Diversified Pricing in Hybrid Column Generation Frameworks
- Frustration-enhanced quantum annealing correction models with additional inter-replica interactions