Increasing the dimension of linear systems solved by classical or quantum binary optimization: A new method to solve large linear equation systems

• URL: http://arxiv.org/abs/2309.09933v2
• Date: Fri, 29 Sep 2023 17:48:00 GMT
• Title: Increasing the dimension of linear systems solved by classical or quantum binary optimization: A new method to solve large linear equation systems
• Authors: Erick R. Castro, Eldues O. Martins, Roberto S. Sarthour, Alexandre M. Souza, Ivan S. Oliveira
• Abstract summary: We propose a new method to solve linear systems written as a binary optimization problem. The procedure solves the problem efficiently and allows it to handle large linear systems.
• Score: 41.94295877935867
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, binary optimization has become an attractive research topic due to the development of quantum computing and specialized classical systems inspired by quantum computing. These hardware systems promise to speed up the computation significantly. In this work, we propose a new method to solve linear systems written as a binary optimization problem. The procedure solves the problem efficiently and allows it to handle large linear systems. Our approach is founded on the geometry of the original linear problem and resembles the gradient conjugate method. The conjugated directions used can significantly improve the algorithm's convergence rate. We also show that a partial knowledge of the intrinsic geometry of the problem can divide the original problem into independent sub-problems of smaller dimensions. These sub-problems can then be solved using quantum or classical solvers. Although determining the geometry of the problem has an additional computational cost, it can substantially improve the performance of our method compared to previous implementations.

Related papers

• New Quantum Algorithm For Solving Linear System of Equations [0.0]
  We introduce a new quantum algorithm for solving linear systems based on the gradient descent method. Inspired by the vector/density state formalism, we represent a point, or vector, as a density state-like entity. The operator corresponding to the intermediate solution is updated iteratively, with a provable guarantee of convergence.
  arXiv  Detail & Related papers  (2025-02-19T11:08:56Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms [18.075115172621096]
  We present a formal analysis of hybrid algorithms in the context of solving mixed-binary quadratic programs via Ising solvers. We propose to solve this reformulation with a hybrid quantum-classical cutting-plane algorithm.
  arXiv  Detail & Related papers  (2022-07-27T16:47:32Z)
• A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
  We propose a quantum-inspired tensor-network-based algorithm for general locally constrained optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem. Our results show the effectiveness of this construction and potential applications.
  arXiv  Detail & Related papers  (2022-03-29T05:44:07Z)
• Improving quantum linear system solvers via a gradient descent perspective [3.0969191504482247]
  We revisit quantum linear system solvers from the perspective of convex optimization. This leads to a considerable constant-factor iteration in the runtime. We show how the optimal quantum linear system solver of Childs, Kothari, and Somma is related to the gradient descent algorithm.
  arXiv  Detail & Related papers  (2021-09-09T13:16:28Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  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.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Quantum variational optimization: The role of entanglement and problem hardness [0.0]
  We study the role of entanglement, the structure of the variational quantum circuit, and the structure of the optimization problem. Our numerical results indicate an advantage in adapting the distribution of entangling gates to the problem's topology. We find evidence that applying conditional value at risk type cost functions improves the optimization, increasing the probability of overlap with the optimal solutions.
  arXiv  Detail & Related papers  (2021-03-26T14:06:54Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)

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.