BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:The learnability of stabiliser states and DNF form
ulae - Andrea Rocchetto
DTSTART;TZID=Europe/London:20171026T141500
DTEND;TZID=Europe/London:20171026T151500
UID:TALK94087AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/94087
DESCRIPTION:Computational learning theory provides a mathemati
cal framework for rigorously formulating learning
problems from both a statistical and computational
perspective. During this talk we will discuss two
independent results at the interplay of learning
theory and quantum computation. On one hand we wil
l show that DNF formulae are efficiently quantum P
AC learnable 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 stat
es\, namely stabiliser states\, for which the “pre
tty-good tomography” introduced by Aaronson [Proc.
R. Soc. A\, 2088\, (2007)] can be performed in po
lynomial time. The results are joint work with Var
un Kanade and Simone Severini.
LOCATION:MR5\, Centre for Mathematical Sciences\, Wilberfor
ce Road\, Cambridge
CONTACT:Steve Brierley
END:VEVENT
END:VCALENDAR