University of Cambridge > Talks.cam > CQIF Seminar > The learnability of stabiliser states and DNF formulae

The learnability of stabiliser states and DNF formulae

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Steve Brierley.

Computational learning theory provides a mathematical 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 will show that DNF formulae are efficiently quantum PAC 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 states, namely stabiliser states, for which the “pretty-good tomography” introduced by Aaronson [Proc. R. Soc. A, 2088, (2007)] can be performed in polynomial time. The results are joint work with Varun Kanade and Simone Severini.

This talk is part of the CQIF Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2022 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity