Srinivasan Arunachalam: Strengths and weaknesses of quantum examples for learning
A talk by Srinivasan Arunachalam at the Quantum Machine Learning Workshop, hosted September 24-28, 2018 by the Joint Center for Quantum Information and Computer Science at the University of Maryland (QuICS).
Abstract: Recently, there has been a lot of recent interest in quantum algorithms for machine learning. These try to improve over classical algorithms for generalizing or otherwise learning from given data (the data itself could also be quantum).
I will consider the following setting: Let C be concept class of Boolean functions f:{0,1}^n-greater than{-1,1}. In the classical learning model, a learner is given a (x,f(x)) sample where x is drawn according to a distribution D and quantumly an example would be a *superposition* sum_x sqrt{D(x)}|x,c(x)greater than. The goal of the learner is output an hypothesis with error (from the unknown f) is at most eps.
In this talk, I will describe a few instances where quantum examples help and when they don't.
a) In the classical PAC model, D is unknown to the learner. Fundamental results in classical learning show that the classical sample complexity of a concept class C in the PAC model is tightly determined by the so-called VC-dimension of C. Our main result is to show that exactly the same formula gives the quantum sample complexity, showing that quantum examples do not help in the PAC model of learning (nor in the related agnostic model).
b) Let D be the uniform distribution, eps=0 (i.e., we need to *identity* f) and suppose C contains Boolean functions having at most k non-zero Fourier coefficients, then how many classical examples suffice to identity f? This question has been studied for over a decade under the name of sparse recovery and Fourier sampling, having applications in compressed sensing and the data stream model. Regev and Haviv (CCC'15) showed Theta(nk) classical samples suffice and are required to solve this problem. In this work, we solve this problem using O(k^{1.5}) quantum samples and show that Omega(k) quantum samples are necessary (importantly, it is independent of n!).
c) I will also consider the coupon-collector problem and show how quantum examples give a logarithmic-improvement over the classical algorithms that solve the coupon collector problem.
Based on joint work with Ronald de Wolf and others.