Srinivasan Arunachalam: Optimal quantum sample complexity of learning algorithms

Subscribers:
345,000
Published on ● Video Link: https://www.youtube.com/watch?v=BcHKMOQTnKg



Duration: 31:55
862 views
15


We tightly determine the minimal sample complexity of learning algorithms that try to learn a target concept from quantum examples, which are the superposition-version of classical random examples. We study both the Probably Approximately Correct (PAC) and the agnostic model of learning. We prove a tight lower bound on the number of examples needed, as a function of the VC dimension of the concept class involved and the error parameters. This function coincides with the known characterizations of classical sample complexity, showing that classical and quantum sample complexity are equal up to constant factors for every concept class, both in the PAC model and in the agnostic model. We have two proof approaches, one based on quantum information theory, and one based on analysis of the properties of the Pretty Good Measurement.




Other Videos By Microsoft Research


2017-01-31Shalev Ben-David: Sculpting quantum speedups
2017-01-31David Sutter: Multivariate trace inequalities
2017-01-31Mischa Woods: Applications of recoverability in quantum information
2017-01-31Anand Natarajan: Limitations of semidefinite programs for separable states and entangled games
2017-01-31A parallel repetition theorem for all entangled games
2017-01-31Guillaume Dauphinais: Fault-tolerant error correction for non-abelian anyons
2017-01-31Dominic Williamson: Anyons and matrix product operator algebras
2017-01-31Jonathan Oppenheim: From quantum thermodynamical identities to a second law equality
2017-01-31Operator scaling and applications
2017-01-31Xin Wang: Asymptotic entanglement manipulation under PPT operations: new SDP bounds&irreversibility
2017-01-31Srinivasan Arunachalam: Optimal quantum sample complexity of learning algorithms
2017-01-311. Catalytic Decoupling 2. Deconstruction and conditional erasure of quantum correlations
2017-01-31A complete characterization of unitary quantum space
2017-01-31David Reutter: Biunitary constructions in quantum information
2017-01-31Fernando Brandao: Quantum speed-ups for semidefinite programming
2017-01-31Joseph M. Renes: Belief propagation decoding of quantum channels by passing quantum messages
2017-01-31Anupam Prakash: Quantum recommendation systems
2017-01-31Garnet Chan: Simulating quantum systems on classical computers
2017-01-31Rigetti Computing Software Demo: Forest
2017-01-31Frank Verstraete: The entanglement of distillation for gauge theories
2017-01-31Aram Harrow: Sequential measurements, disturbance and property testing



Tags:
microsoft research