Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing

• URL: http://arxiv.org/abs/2108.08064v2
• Date: Mon, 25 Oct 2021 16:33:26 GMT
• Title: Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing
• Authors: Joseph Bowles, Alexandre Dauphin, Patrick Huembeli, Jos\'e Martinez, Antonio Ac\'in
• Abstract summary: We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
• Score: 58.720142291102135
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. The algorithm can be seen as an analogue 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 tuneable 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 non-stochastic setting.

Related papers

• The Differentiable Feasibility Pump [49.55771920271201]
  This paper shows that the traditional feasibility pump and many of its follow-ups can be seen as gradient-descent algorithms with specific parameters. A central aspect of this reinterpretation is observing that the traditional algorithm differentiates the solution of the linear relaxation with respect to its cost.
  arXiv  Detail & Related papers  (2024-11-05T22:26:51Z)
• Qudit inspired optimization for graph coloring [0.0]
  We introduce a quantum-inspired algorithm for Graph Coloring Problems (GCPs) We use qudits in a product state, with each qudit representing a node in the graph and parameterized by d-dimensional spherical coordinates. We benchmark two optimization strategies: qudit gradient descent (QdGD), initiating qudits in random states and employing gradient descent to minimize a cost function.
  arXiv  Detail & Related papers  (2024-06-02T16:19:55Z)
• Compressed sensing enhanced by quantum approximate optimization algorithm [0.0]
  We present a framework to deal with a range of large scale compressive sensing problems using a quantum subroutine. Our results explore a promising path of applying quantum computers in the compressive sensing field.
  arXiv  Detail & Related papers  (2024-03-26T05:26:51Z)
• Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization [39.58317527488534]
  We propose a novel method for solving linear systems. We transform the linear system into a binary optimization problem, drawing inspiration from the geometry of the original problem. We demonstrate that by leveraging partial knowledge of the problem's intrinsic geometry, we can decompose the original problem into smaller, independent sub-problems.
  arXiv  Detail & Related papers  (2023-09-18T16:51:03Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Avoiding local minima in Variational Quantum Algorithms with Neural Networks [0.0]
  Variational Quantum Algorithms have emerged as a leading paradigm for near-term computation. In this paper we present two algorithms within benchmark them on instances of the gradient landscape problem. We suggest that our approach suggests that the cost landscape is a fruitful path to improving near-term quantum computing algorithms.
  arXiv  Detail & Related papers  (2021-04-07T07:07:28Z)
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms [0.0]
  We apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach.
  arXiv  Detail & Related papers  (2021-01-19T19:00:40Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.