Understand
We construct an efficient classical analogue of the quantum matrix inversion algorithm (HHL) for low-rank matrices.
- Inspired by recent work of Tang, assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix and sample from the solution to the problem $Ax=b$ using fast sampling techniques.
- We implement the pseudo-inverse by finding an approximate singular value decomposition of $A$ via subsampling, then inverting the singular values.
- In principle, the approach can also be used to apply any desired "smooth" function to the singular values.
Built on
Fast Monte-Carlo algorithms for finding low-rank approximations
Alan Frieze, Ravi Kannan, and Santosh Vempala · 2004
Earlier work this paper cites.
Quantum algorithm for linear systems of equations
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd · 2009
Earlier work this paper cites.
Quantum recommendation systems
Iordanis Kerenidis and Anupam Prakash · 2017
Earlier work this paper cites.
Randomized algorithms in numerical linear algebra
Ravindran Kannan and Santosh Vempala · 2017
Earlier work this paper cites.
Similar
Shantanav Chakraborty, András Gilyén, and Stacey Jeffery · 2018
Cited alongside, same era.
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe · 2018
Cited alongside, same era.
Quantum computational finance: quantum algorithm for portfolio optimization
Patrick Rebentrost and Seth Lloyd · 2018
Cited alongside, same era.
Then
Quantum singular-value decomposition of nonsparse low-rank matrices
Patrick Rebentrost, Adrian Steffens, Iman Marvian, and Seth Lloyd · 2018
Closest in time.
A quantum-inspired classical algorithm for recommendation systems
Ewin Tang · 2018
Closest in time.
Quantum-inspired classical algorithms for principal component analysis and supervised clustering
Ewin Tang · 2018
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…