The learnability of stabiliser states and DNF formulae

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

• Andrea Rocchetto
• Thursday 26 October 2017, 14:15-15:15
• MR5, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

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.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR5, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.