A Classical Algorithm Framework for Dequantizing Quantum Machine Learning

          @misc{ scivideos_15414,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tbd-134},
            author = {},
            keywords = {},
            language = {en},
            title = {A Classical Algorithm Framework for Dequantizing Quantum Machine Learning},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {feb},
            note = {15414 see, \url{https://scivideos.org/Simons-Institute/15414}}
          }
          

Abstract

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.