IQI Weekly Seminar

Friday March 23, 2018 3:00 PM

The learnability of stabiliser states and DNF formulae

Speaker: Andrea Rocchetto, University of Oxford/UCL
Location: Annenberg 107

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.


















Series Institute for Quantum Information (IQI) Weekly Seminar Series

Contact: Bonnie Leung at 626.395.4964