Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra

Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin, David P. WoodruffICML 2022 · OpenReview

Introduction

In recent years, several quantum algorithms have promised "exponential speedups" for fundamental linear algebra tasks like recommendation systems and regression. However, these speedups come with a significant caveat: they assume the input matrix is stored in a highly specific, tree-based data structure that allows for fast quantum state preparation.

This has led to the study of "dequantization"—the process of finding classical algorithms that use these same data structures to achieve similar sublinear runtimes (runtimes that do not depend directly on the total number of rows or columns). While previous dequantized algorithms proved that quantum speedups in this setting weren't strictly exponential, their runtimes were often high-degree polynomials of parameters like the matrix rank ($k$) and condition number ($\kappa$), making them highly impractical.

This paper bridges the gap between these "quantum-inspired" methods and the mature field of Randomized Numerical Linear Algebra (RandNLA). By applying standard RandNLA tools, the authors develop classical algorithms for ridge regression and low-rank approximation that are significantly faster, simpler, and more practical than previous quantum-inspired versions.

The RandNLA Connection

The authors' primary "Aha!" moment is the realization that the sampling operations supported by "quantum-ready" data structures are essentially leverage score sampling in disguise. Leverage scores identify which rows of a matrix are most "influential" for its overall structure, a foundational concept in RandNLA.

By reframing the problem, the authors bypass complex $\ell_2$-sampling arguments used in prior dequantization work. Their methodology relies on three key techniques:

  1. Simulating Leverage Score Sampling: They demonstrate that sampling rows proportional to their squared Euclidean norms (which the quantum-ready data structure natively supports) is equivalent to leverage score sampling, provided you oversample by a factor related to the matrix's condition number.
  2. RandNLA Primitives: The algorithms employ Subspace Embeddings to reduce the number of rows while preserving the geometry of the column space, and Projection-Cost Preserving (PCP) sketches to maintain the error bounds of projecting onto low-rank subspaces.
  3. Dynamic Data Structures: They utilize a tree-based structure (DYNSAMP) that supports "turnstile" updates (insertions and deletions of entries) in $O(\log(nd))$ time, allowing the algorithms to function efficiently in dynamic environments.

Key Results and Performance

The paper provides drastically improved theoretical bounds alongside strong empirical performance across synthetic and real-world datasets (including KOS blog word frequencies, MovieLens 100K, and YearPrediction).

Theoretical Improvements

By leveraging RandNLA, the authors reduce the polynomial dependence on numerical parameters, moving these algorithms from theoretical curiosities to practical tools.

Comparison of runtime bounds between this work and prior quantum-inspired algorithms.

As shown in the table above, the query times for Ridge Regression and Low Rank Sampling are substantially reduced. Most notably, in Ridge Regression, the dependence on the condition number $\kappa$ drops from a prohibitive $\kappa^{16}$ in prior work to just $\kappa^3$ or $\kappa^2$.

Empirical Speedups

The authors compared their algorithms against a leading implementation of prior dequantized algorithms (referred to as ADBL).

  • Speed: The proposed algorithms were consistently faster. On datasets like MovieLens and KOS, query times were roughly 6x faster than ADBL.
  • Accuracy: They achieved comparable error rates (around $\epsilon \approx 0.05$) while remaining significantly faster than computing a standard Singular Value Decomposition (SVD).
  • Scalability: On the massive YearPrediction dataset, the algorithm achieved an error of $<0.1$ while sampling only a tiny fraction of the rows, running much faster than exact solution methods.
Empirical performance comparing the proposed algorithms against ADBL and exact SVD.

Limitations and Future Directions

While the runtimes are sublinear in matrix dimensions $n$ and $d$, they still depend on "numerical" parameters like the condition number $\kappa(A)$ and the Frobenius norm $\|A\|_F$. If a matrix is extremely ill-conditioned, the sampling requirements might grow until the algorithm is no longer faster than classical dense methods.

Additionally, the algorithms assume the tree-based data structure is already built. While building it takes $O(\text{nnz}(A))$ time—which is standard for reading the data—this initial cost must be amortized over many queries to realize a true performance benefit.

Looking forward, the authors suggest that these RandNLA techniques could be extended to dequantize other "quantum-ready" problems, such as solving semi-definite programs (SDPs) or training more complex machine learning models.

Summary updated

BibTeX
@inproceedings{chepurko2022quantum,
  author = {Nadiia Chepurko and Kenneth L. Clarkson and Lior Horesh and Honghao Lin and David P. Woodruff},
  title = {{Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=O53vM1sc3O},
}
Figure