Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems
arXiv:2411.06901 · doi:10.7566/JPSJ.94.054003
Abstract
Quantum annealing is a generic solver for combinatorial optimization problems that utilizes quantum fluctuations. Recently, there has been extensive research applying quantum annealers, which are hardware implementations of quantum annealing. Since quantum annealers can only handle quadratic unconstrained binary optimization problems, to solve constrained combinatorial optimization problems using quantum annealers, the constraints must be incorporated into the objective function. One such technique is the Ohzeki method, which employs a Hubbard-Stratonovich transformation to relax equality constraints, and its effectiveness for large-scale problems has been demonstrated numerically. This study applies the Ohzeki method to combinatorial optimization problems with inequality constraints. We show that inequality constraints can be relaxed into a similar objective function through statistical mechanics calculations similar to those for equality constraints. In addition, we evaluate the performance of this method in a typical inequality-constrained combinatorial optimization problem, the quadratic knapsack problem.
17 pages, 4 figures
References in corpus (18)
- Quantum Annealing in the Transverse Ising Model
- Quantum Boltzmann Machine
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Nonnegative/binary matrix factorization with a D-Wave quantum annealer
- Traffic Signal Optimization on a Square Lattice with Quantum Annealing
- Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
- Travel time optimization on multi-AGV routing by reverse annealing
- Benchmark test of Black-box optimization using D-Wave quantum annealer
- 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
- 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
- Exploration of new chemical materials using black-box optimization with the D-wave quantum annealer
- Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem
- Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing