Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra. (arXiv:2011.04125v7 [cs.DS] UPDATED)

We create classical (non-quantum) dynamic data structures supporting queries
for recommender systems and least-squares regression that are comparable to
their quantum analogues. De-quantizing such algorithms has received a flurry of
attention in recent years; we obtain sharper bounds for these problems. More
significantly, we achieve these improvements by arguing that the previous
quantum-inspired algorithms for these problems are doing leverage or
ridge-leverage score sampling in disguise; these are powerful and standard
techniques in randomized numerical linear algebra. With this recognition, …

algorithms arxiv linear linear algebra numerical quantum