Quantum-inspired algorithms for solving low-rank linear equation systems with logarithmic dependence on the dimension
We present two efficient classical analogues of the quantum matrix inversion algorithm [16] for low-rank matrices. Inspired by recent work of Tang [27], assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix allowing us to sample from the solution t...
Main Authors: | Chia, NH, Gilyén, A, Lin, HH, Lloyd, S, Tang, E, Wang, C |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Mechanical Engineering |
Format: | Article |
Language: | English |
Published: |
2022
|
Online Access: | https://hdl.handle.net/1721.1/138872 |
Similar Items
-
Quantum Algorithm for Linear Systems of Equations
by: Lloyd, Seth, et al.
Published: (2010) -
Analysis of algorithms to solve the discrete logarithm problem
by: Sim, Ernest Zi-En
Published: (2024) -
Logarithmic Picard groups, chip firing, and the combinatorial rank
by: Foster, Tyler, et al.
Published: (2021) -
Quantum algorithm for nonhomogeneous linear partial differential equations
by: Arrazola, Juan Miguel, et al.
Published: (2021) -
Finite Logarithmic Order Meromorphic Solutions of Complex Linear Delay-Differential Equations
by: Abdelkader Dahmani, et al.
Published: (2023-11-01)