IQI Weekly Seminar

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.