Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
arXiv:2104.14096 · doi:10.1038/s41598-022-06070-5
Abstract
Recently, inspired by quantum annealing, many solvers specialized for unconstrained binary quadratic programming problems have been developed. For further improvement and application of these solvers, it is important to clarify the differences in their performance for various types of problems. In this study, the performance of four quadratic unconstrained binary optimization problem solvers, namely D-Wave Hybrid Solver Service (HSS), Toshiba Simulated Bifurcation Machine (SBM), Fujitsu DigitalAnnealer (DA), and simulated annealing on a personal computer, was benchmarked. The problems used for benchmarking were instances of real problems in MQLib, instances of the SAT-UNSAT phase transition point of random not-all-equal 3-SAT(NAE 3-SAT), and the Ising spin glass Sherrington-Kirkpatrick (SK) model. Concerning MQLib instances, the HSS performance ranked first; for NAE 3-SAT, DA performance ranked first; and regarding the SK model, SBM performance ranked first. These results may help understand the strengths and weaknesses of these solvers.
11 pages, 3 figures, 10 tables
References in corpus (1)
Cited by in corpus (21)
- Roadmap for Unconventional Computing with Nanotechnology
- Basic Elements for Simulations of Standard Model Physics with Quantum Annealers: Multigrid and Clock States
- Travel time optimization on multi-AGV routing by reverse annealing
- Mapping quantum circuits to modular architectures with QUBO
- Simulated bifurcation assisted by thermal fluctuation
- Simulated bifurcation for higher-order cost functions
- Comparing the effects of Boltzmann machines as associative memory in Generative Adversarial Networks between classical and quantum sampling
- Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
- Virtual Screening of Chemical Space based on Quantum Annealing
- An Optimization Case Study for solving a Transport Robot Scheduling Problem on Quantum-Hybrid and Quantum-Inspired Hardware
- Quantum-inspired optimization for wavelength assignment
- Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing
- Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
- Message Passing Variational Autoregressive Network for Solving Intractable Ising Models
- Incentivising Demand Side Response through Discount Scheduling using Hybrid Quantum Optimization
- Online calibration scheme for training restricted Boltzmann machines with quantum annealing
- Deep Unfolded Local Quantum Annealing
- Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems
- Edge-of-chaos enhanced quantum-inspired algorithm for combinatorial optimization
- Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
- A Vectorized Positive Semidefinite Penalty Method for Unconstrained Binary Quadratic Programming