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

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

The learnability of stabiliser states and DNF formulae

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

In person if possible Hicks Room, University Centre, Granta Place, Mill Lane, Cambridge CB2 1RU Pippard Lecture Theatre, Physics, Department of

Other talks

Afternoon Break Bacterial Physiology During Growth Arrest: Can It Be Targeted by Anti-Bacterial Therapeutics? Online Causal Inference Seminar Morning Break Beyond Hubble: Studying the Earliest Galaxies with the James Webb Space Telescope Alicia Anderson discussing some exciting news about HARPS3
 

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