QuRANLA: Quantum-Inspired Randomized Algorithms for Large-Scale Linear Algebra

Building on the RandNLA survey (2024) and Sketch 'n Solve (2024), this research explores how quantum computing concepts can inspire new classical algorithms. While current RandNLA methods use random sampling and projection, QuRANLA would incorporate quantum-inspired techniques like amplitude amplification and quantum walk-inspired matrix exploration. The key insight is that certain quantum algorithmic principles can be approximated classically to achieve similar computational advantages. For example, quantum amplitude amplification can inspire new sampling strategies that focus computational effort on matrix regions with higher information content. This differs from existing RandNLA approaches by using quantum-inspired probability distributions rather than uniform or Gaussian sampling. The research would develop theoretical foundations for these hybrid algorithms and implement them in libraries like Ginkgo (2020). This could bridge the gap between quantum computing's theoretical advantages and practical classical implementation, potentially offering 2-5x speedups for certain matrix operations while maintaining numerical stability.

References:

1. Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning. Michal Derezinski, Michael W. Mahoney (2024). Knowledge Discovery and Data Mining.
2. Ginkgo: A high performance numerical linear algebra library. H. Anzt, T. Cojean, Yen-Chen Chen, Goran Flegar, Fritz Göbel, Thomas Grützmacher, Pratik Nayak, T. Ribizel, Yu-Hsiang Tsai (2020). Journal of Open Source Software.
3. Sketch 'n Solve: An Efficient Python Package for Large-Scale Least Squares Using Randomized Numerical Linear Algebra. Alex Lavaee (2024).