A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm

• URL: http://arxiv.org/abs/2406.13879v1
• Date: Wed, 19 Jun 2024 23:15:35 GMT
• Title: A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm
• Authors: Junhyung Lyle Kim, Nai-Hui Chia, Anastasios Kyrillidis,
• Abstract summary: 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.
• Score: 9.804179673817574
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving systems of linear equations is a fundamental problem, but it can be computationally intensive for classical algorithms in high dimensions. Existing quantum algorithms can achieve exponential speedups for the quantum linear system problem (QLSP) in terms of the problem dimension, but even such a theoretical advantage is bottlenecked by the condition number of the coefficient matrix. In this work, we propose a new quantum algorithm for 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 \texttt{QLSP\_solver}, thereby directly approximating the solution vector instead of approximating the inverse of the coefficient matrix. 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.

Related papers

• Shadow Quantum Linear Solver: A Resource Efficient Quantum Algorithm for Linear Systems of Equations [0.8437187555622164]
  We present an original algorithmic procedure to solve the Quantum Linear System Problem (QLSP) on a digital quantum device. The result is a quantum algorithm avoiding the need for large controlled unitaries, requiring a number of qubits that is logarithmic in the system size. We apply this to a physical problem of practical relevance, by leveraging decomposition theorems from linear algebra to solve the discretized Laplace Equation in a 2D grid.
  arXiv  Detail & Related papers  (2024-09-13T15:46:32Z)
• An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
  We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension.
  arXiv  Detail & Related papers  (2024-03-28T20:37:32Z)
• 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)
• Hybrid quantum-classical and quantum-inspired classical algorithms for solving banded circulant linear systems [0.8192907805418583]
  We present an efficient algorithm based on convex optimization of combinations of quantum states to solve for banded circulant linear systems. By decomposing banded circulant matrices into cyclic permutations, our approach produces approximate solutions to such systems with a combination of quantum states linear to $K$. We validate our methods with classical simulations and actual IBM quantum computer implementation, showcasing their applicability for solving physical problems such as heat transfer.
  arXiv  Detail & Related papers  (2023-09-20T16:27:16Z)
• An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization [0.0]
  Quantum linear system algorithms (QLSAs) have the potential to speed up algorithms that rely on solving linear systems. In our work, we propose an Inexact-Feasible QIPM (IF-QIPM) and show its advantage in solving linearly constrained quadratic optimization problems.
  arXiv  Detail & Related papers  (2023-01-13T01:36:13Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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)
• 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)
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time [46.31710224483631]
  We show how to bypass the main open question of Nelson and Nguyen (FOCS, 2013) regarding the logarithmic factors in the sketching dimension for existing constant factor approximation oblivious subspace embeddings. A key technique we use is an explicit mapping of Indyk based on uncertainty principles and extractors. For the fundamental problems of rank computation and finding a linearly independent subset of columns, our algorithms improve Cheung, Kwok, and Lau (JACM, 2013) and are optimal to within a constant factor and a $loglog(n)$-factor, respectively.
  arXiv  Detail & Related papers  (2021-07-16T19:34:10Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)

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.