Quadratic Unconstrained Binary Optimization via Quantum-Inspired Annealing

Authors:

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.
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: