Srinivasan Arunachalam: Strengths and weaknesses of quantum examples for learning

Channel:
Subscribers:
2,520
Published on ● Video Link: https://www.youtube.com/watch?v=k0x4LJCoPVU



Duration: 52:41
372 views
0


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.




Other Videos By QuICS


2018-10-31Scott Aaronson: Gentle Measurement of Quantum States and Differential Privacy
2018-10-31Seth Lloyd: Quantum Generative Adversarial Networks
2018-10-31Norbert Linke: Quantum Machine Learning with Trapped Ions
2018-10-31Kristan Temme: Supervised Learning with Quantum Enhanced Feature Spaces
2018-10-31Soheil Feizi: Generative Adversarial Networks: Formulation, Design and Computation
2018-10-31Nathan Wiebe: Optimizing Quantum Optimization Algorithms via Faster Quantum Gradient Computation
2018-10-31Rolando Somma: Quantum Algorithms for Systems of Linear Equations
2018-10-31Anupam Praksah: A Quantum Interior Point Method for LPs and SDPs
2018-10-31Furong Huang: Discovery of Latent Factors in High-dimensional Data Using Tensor Methods
2018-10-31Fernando Brandao: Quantum Speed-up for SDPs and Kernel Learning
2018-10-31Srinivasan Arunachalam: Strengths and weaknesses of quantum examples for learning
2018-10-31Vedran Dunjko: A Route towards Quantum-Enhanced Artificial Intelligence
2018-10-31Elad Hazan: Efficient Optimization for Machine Learning: Beyond Stochastic Gradient Descent
2017-10-11John Preskill: QEC in 2017—Past, present, and future
2017-10-11Sepehr Nezami: Quantum Error Correction of Reference Frame Information
2017-10-11Anirudh Krishna: Performance of hyperbolic surface codes
2017-10-11Brian Swingle: Entanglement, Wormholes, and Quantum Error Correction
2017-10-11Christa Flühmann: Preparation of Grid state qubits by sequential modular position measurements
2017-10-11Matteo Marinelli: Repetitive stabilizer readout with conditional feedback
2017-10-11Norbert Linke: Fault-tolerant quantum error detection with trapped ions
2017-10-11Rui Chao: Fault-tolerant quantum computation with few qubits



Tags:
machine learning