On the application of matrix congruence to QUBO formulations for systems of linear equations

• URL: http://arxiv.org/abs/2111.00747v1
• Date: Mon, 1 Nov 2021 07:52:01 GMT
• Title: On the application of matrix congruence to QUBO formulations for systems of linear equations
• Authors: Sun Woo Park, Hyunju Lee, Byung Chun Kim, Youngho Woo, and Kyungtaek Jun
• Abstract summary: Recent studies on quantum computing algorithms focus on excavating features of quantum computers which have potential for contributing to computational model enhancements. In this paper, we simplify quadratic unconstrained binary optimization (QUBO) formulations of systems of linear equations by exploiting congruence of real symmetric matrices to diagonal matrices. We further exhibit computational merits of the proposed QUBO models, which can outperform classical algorithms such as QR and SVD decomposition.
• Score: 0.505645669728935
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent studies on quantum computing algorithms focus on excavating features of quantum computers which have potential for contributing to computational model enhancements. Among various approaches, quantum annealing methods effectively parallelize quadratic unconstrained binary optimization (QUBO) formulations of systems of linear equations. In this paper, we simplify these formulations by exploiting congruence of real symmetric matrices to diagonal matrices. We further exhibit computational merits of the proposed QUBO models, which can outperform classical algorithms such as QR and SVD decomposition.

Related papers

• An Improved Method for Quantum Matrix Multiplication [0.0]
  Following the celebrated quantum algorithm for solving linear equations, we provide an approach to solve a linear system of equations with exponentially improved dependence on precision. A few examples that motivate this application are included and we further discuss an application of this improved matrix application algorithm explicitly with an efficient quantum procedure.
  arXiv  Detail & Related papers  (2023-11-23T15:00:36Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
  arXiv  Detail & Related papers  (2022-02-10T08:12:20Z)
• On the application of Sylvester's law of inertia to QUBO formulations for systems of linear equations [0.2538209532048866]
  We develop the QUBO formulations of systems of linear equations by applying Sylvester's law of inertia. We expect that the proposed algorithm can effectively implement higher dimensional systems of linear equations on a quantum computer.
  arXiv  Detail & Related papers  (2021-11-19T07:55:10Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• Quantum algorithms for powering stable Hermitian matrices [0.7734726150561088]
  Matrix powering is a fundamental computational primitive in linear algebra. We present two quantum algorithms that can achieve speedup over the classical matrix powering algorithms.
  arXiv  Detail & Related papers  (2021-03-15T12:20:04Z)
• 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)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)
• Block-encoding based quantum algorithm for linear systems with displacement structures [4.145426157018113]
  We present efficient and memory-reduced quantum algorithms for solving linear systems with displacement structures. The proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms. One of the quantum linear system solvers is applied to the linear prediction of time series.
  arXiv  Detail & Related papers  (2019-12-27T16:10:13Z)

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.