Ewin Tang: Building a classical framework to analyze quantum machine learning speedups
0An invited talk by Ewin Tang at the 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), Day 1. TQC 2019 was hosted June 3-5, 2019 by the Joint Center for Quantum Information and Computer Science at the University of Maryland (QuICS). More information about TQC can be found at https://www.tqcconference.org.
Abstract: We cover some recent work on "dequantizing" QML algorithms and the set of classical length-squared sampling techniques used to achieve these results. First, we motivate the correspondence between QML with state preparation assumptions and classical ML with sampling assumptions. In the latter setting, we describe an algorithm toolkit which bears resemblance to quantum operations on classical distributions. Second, we describe the capabilities and limitations of these techniques in comparison with quantum computing, by considering their application to low-rank matrix inversion (1811.04909 and 1811.04852), supervised clustering (1811.00414), and recommendation systems (1807.04271). This theory of quantum-like classical sampling algorithms formalizes some intuition informing our evaluation of polylogarithmic-time QML algorithms as "good" or "bad". By comparing QML algorithms to classical ML algorithms strengthened with sampling assumptions, we can distinguish the speedups artificially created from quantum state preparation assumptions from the speedups that truly exploit the quantumness of the algorithm.