A Classical Algorithm Framework for Dequantizing Quantum Machine Learning

Explore a classical algorithm framework for dequantizing quantum machine learning in this 34-minute lecture by Ewin Tang from the University of Washington. Delve into topics such as quantum linear algebra, matrix notation, input/output assumptions of QML, and the powering up of classical computation with measurements. Examine sample and query access, quantum-inspired sketching, and importance sampling techniques for approximating matrix products. Learn about RUR decompositions and the main theorem on even singular value transformation. Compare quantum-inspired SVT to quantum SVT, and investigate the implications for exponential speedups in quantum machine learning. This talk, part of the Quantum Algorithms series at the Simons Institute, provides valuable insights into the intersection of classical and quantum computational approaches in machine learning.

Intro
Dequantizing quantum lipear algebra
Unifying quantum linear algebra
Matrix notation
Input/output assumptions of QML
Powering up classical computation with measurements
Sample and query access
Quantum-inspired sketching, aka importance sampling
Importance sampling can approximate matrix products
All we need are RUR decompositions
Main theorem: even singular value transformation
Proof sketch of main theprem
Interpreting the even SVT result
Comparing quantum-inspired SVT to quantum SVT
Applications
Implications for exponential speedups in QML