Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning

Explore a groundbreaking framework for dequantizing quantum machine learning algorithms in this 21-minute conference talk presented at the Association for Computing Machinery (ACM). Delve into the world of sampling-based sublinear low-rank matrix arithmetic and its application to singular value transformation. Learn about the landscape of exponential speedups in quantum machine learning, and discover how quantum-inspired classical SVT can revolutionize the field. Gain insights into oversampling, query access, and the block-encoding-like composition properties of SQ. Understand techniques for reducing dimensionality to access matrix products and grasp the main theorem on even singular value transformation. Conclude with final thoughts on the implications of this innovative approach for the future of quantum and classical machine learning algorithms.

Intro
Landscape: exponential speedups in quantum machine learning
Main result: quantum-inspired classical SVT
Preliminaries
Oversampling and query access
SQ has block-encoding-like composition properties
Reducing dimensionality to access matrix products
Main theorem: even singular value transformation
Final thoughts