Quadratic Unconstrained Binary Optimization via Quantum-Inspired Annealing
- 7 September 2022
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Applied
- Vol. 18 (3) , 034016
Abstract
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimization. The algorithm can be seen as an analog of quantum annealing under the restriction of a product-state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent-based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large-scale problem instances with tunable hardness and planted solutions. We find that our algorithm offers a similar performance to current state-of-the-art approaches within a comparably simple gradient-based and nonstochastic setting.Keywords
All Related Versions
Funding Information
- Generalitat de Catalunya
- Ministry of Economy and Competitiveness
- Horizon 2020 (899794)
- National Science Centre, Poland (2016/20/W/ST4/00314)
- Caixa Foundation
This publication has 34 references indexed in Scilit:
- A 20k-Spin Ising Chip to Solve Combinatorial Optimization Problems With CMOS AnnealingIEEE Journal of Solid-State Circuits, 2015
- Quantum Optimization of Fully Connected Spin GlassesPhysical Review X, 2015
- Comparing Monte Carlo methods for finding ground states of Ising spin glasses: Population annealing, simulated annealing, and parallel temperingPhysical Review E, 2015
- Classical signature of quantum annealingFrontiers in Physics, 2014
- Ising formulations of many NP problemsFrontiers in Physics, 2014
- GNCCP—Graduated NonConvexityand Concavity ProcedureIEEE Transactions on Pattern Analysis and Machine Intelligence, 2013
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete ProblemScience, 2001
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and boundsAnnals of Operations Research, 1991
- Computing with Neural Circuits: A ModelScience, 1986