On the application of Sylvester's law of inertia to QUBO formulations for systems of linear equations

• URL: http://arxiv.org/abs/2111.10084v2
• Date: Fri, 10 Dec 2021 16:43:03 GMT
• Title: On the application of Sylvester's law of inertia to QUBO formulations for systems of linear equations
• Authors: Sun Woo Park and Kyungtaek Jun
• Abstract summary: 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.
• Score: 0.2538209532048866
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Previous research on quantum annealing methods focused on effectively modeling systems of linear equations by utilizing quadratic unconstrained binary optimization (QUBO) formulations. These studies take part in enhancing quantum computing algorithms, which extract properties of quantum computers suitable for improving classical computational models. In this paper, we further develop the QUBO formulations of systems of linear equations by applying Sylvester's law of inertia, which explores matrix congruence of any real symmetric matrix to a diagonal matrix. We expect that the proposed algorithm can effectively implement higher dimensional systems of linear equations on a quantum computer. Further experimental verification of the proposed QUBO models as well as their comparisons to classical algorithms are also made.

Related papers

• A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
  We propose a new quantum algorithm for the quantum linear system problem (QLSP) inspired by the classical proximal point algorithm (PPA) Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing texttimattQLSP_solver. By carefully choosing the step size $eta$, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches.
  arXiv  Detail & Related papers  (2024-06-19T23:15:35Z)
• Preconditioning for a Variational Quantum Linear Solver [0.0]
  We numerically demonstrate a notable reduction in the required ansatz depth, demonstrating that preconditioning is useful for quantum algorithms. Our findings suggest that combining classical computing techniques, such as preconditioning, with quantum algorithms can significantly enhance the performance of NISQ algorithms.
  arXiv  Detail & Related papers  (2023-12-25T08:50:22Z)
• 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)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
  arXiv  Detail & Related papers  (2023-06-14T23:08:51Z)
• 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)
• 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 matrix congruence to QUBO formulations for systems of linear equations [0.505645669728935]
  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.
  arXiv  Detail & Related papers  (2021-11-01T07:52:01Z)
• 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)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• 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)
• 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.