A near-term quantum algorithm for solving linear systems of equations based on the Woodbury identity

• URL: http://arxiv.org/abs/2205.00645v2
• Date: Tue, 25 Jun 2024 23:16:54 GMT
• Title: A near-term quantum algorithm for solving linear systems of equations based on the Woodbury identity
• Authors: Daniel O'Malley, Jessie M. Henderson, Elijah Pelofske, Sarah Greer, Yigit Subasi, John K. Golden, Robert Lowrie, Stephan Eidenbenz,
• Abstract summary: We describe a quantum algorithm for solving linear systems of equations that avoids problems such as barren plateaus and local optima. Our algorithm is based on the Woodbury identity, which analytically describes the inverse of a matrix that is a low-rank modification of another (easily-invertible) matrix. We estimate the inner product involving the solution of a system of more than 16 million equations with 2% error using IBM's Auckland quantum computer.
• Score: 0.602276990341246
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum algorithms for solving linear systems of equations have generated excitement because of the potential speed-ups involved and the importance of solving linear equations in many applications. However, applying these algorithms can be challenging. The Harrow-Hassidim-Lloyd algorithm and improvements thereof require complex subroutines suitable for fault-tolerant hardware such as Hamiltonian simulation, making it ill-suited to current hardware. Variational algorithms, on the other hand, involve expensive optimization loops, which can be prone to barren plateaus and local optima. We describe a quantum algorithm for solving linear systems of equations that avoids these problems. Our algorithm is based on the Woodbury identity, which analytically describes the inverse of a matrix that is a low-rank modification of another (easily-invertible) matrix. This approach only utilizes basic quantum subroutines like the Hadamard test or the swap test, so it is well-suited to current hardware. There is no optimization loop, so barren plateaus and local optima do not present a problem. The low-rank aspect of the identity enables us to efficiently transfer information to and from the quantum computer. This approach can produce accurate results on current hardware. As evidence of this, we estimate an inner product involving the solution of a system of more than 16 million equations with 2% error using IBM's Auckland quantum computer. To our knowledge, no system of equations this large has previously been solved to this level of accuracy on a quantum computer.

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)
• 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)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL) This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
  arXiv  Detail & Related papers  (2022-10-23T11:58:05Z)
• 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)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
  The complexity of our algorithm is $O(rm polylog(n/epsilon))$, which provides an exponential improvement over the optimal classical algorithm in dimension $n$. Our algorithm exponentially accelerates the solution of QNSE and has wide applications in all kinds of nonlinear problems.
  arXiv  Detail & Related papers  (2021-12-03T00:27:16Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• QUBO formulations for numerical quantum computing [0.0]
  Harrow-Hassidim-Lloyd algorithm is a monumental quantum algorithm for solving linear systems on gate model quantum computers. We will find unconstrained binary optimization (QUBO) models for a vector x that satisfies Ax=b. We validate those QUBO models on the D-Wave system and discuss the results.
  arXiv  Detail & Related papers  (2021-06-21T02:49:59Z)
• 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.