BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The learnability of stabiliser states and DNF formulae - Andrea Ro
 cchetto
DTSTART:20171026T131500Z
DTEND:20171026T141500Z
UID:TALK94087@talks.cam.ac.uk
CONTACT:Steve Brierley
DESCRIPTION:Computational learning theory provides a mathematical framewor
 k for rigorously formulating learning problems from both a statistical and
  computational perspective. During this talk we will discuss two independe
 nt results at the interplay of learning theory and quantum computation. On
  one hand we will show that DNF formulae are efficiently quantum PAC learn
 able under product distributions. The best known classical algorithm runs 
 in time O(n^(log(n)). On the other hand we will show a class of states\, n
 amely stabiliser states\, for which the “pretty-good tomography” intro
 duced by Aaronson [Proc. R. Soc. A\, 2088\, (2007)] can be performed in po
 lynomial time. The results are joint work with Varun Kanade and Simone Sev
 erini.
LOCATION:MR5\, Centre for Mathematical Sciences\, Wilberforce Road\, Cambr
 idge
END:VEVENT
END:VCALENDAR