Spring 2020

A Classical Algorithm Framework for Dequantizing Quantum Machine Learning

Tuesday, Feb. 25, 2020 11:15 am11:45 am PST

Add to Calendar


Ewin Tang (University of Washington)


Calvin Lab Auditorium

We discuss a classical analogue to the singular value transformation framework for quantum linear algebra algorithms developed by Gilyén et al. The proofs underlying this classical framework have natural connections to well-known ideas in randomized numerical linear algebra. Namely, our proofs are based on one key observation: approximating matrix products is easy in the quantum-inspired input model. This primitive's simplicity makes finding classical analogues to quantum machine learning algorithms straightforward and intuitive. We present sketches of the key proofs of our sketches as well as of its applications to dequantizing low-rank quantum machine learning.

Joint work with Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang.