Friday, March 23, 2018
3:00 pm

IQI Weekly Seminar

The learnability of stabiliser states and DNF formulae
Andrea Rocchetto, University of Oxford/UCL

Abstract: : Computational learning theory provides a mathematical framework for rigorously formulating learning problems from both a statistical and computational perspective. During this talk I will present two independent results at the interplay of learning theory and quantum computation. First, I will show that the class of boolean functions that can be expressed as polynomial size formulae in disjunctive normal form (DNF) is efficiently quantum PAC learnable under product distributions. The best known classical algorithm runs in superpolynomial  time. Second, I will present a class of states, namely stabiliser states, for which the "pretty-good tomography" introduced by Aaronson can be performed in polynomial time. The results are joint work with Varun Kanade and Simone Severini.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Contact Bonnie Leung bjleung@caltech.edu at 626.395.4964
Add this event to my calendar