University of Cambridge > > CQIF Seminar > Post-selected Classical Query Complexity

Post-selected Classical Query Complexity

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

If you have a question about this talk, please contact Johannes Bausch.

The precise relationship between post-selected classical and post-selected quantum computation is an open problem in complexity theory. Post-selection has proven to be a useful tool in uncovering some of the differences between quantum and classical theories, in foundations and elsewhere. This is no less true in the area of computational complexity—quantum computations augmented with post-selection are thought to be vastly more powerful than their classical counterparts. However, the precise reasons why this might be the case are not well understood, and no rigorous separations between the two have been found. In this talk, I will consider the difference in computational power of classical and quantum post-selection in the computational query complexity setting.

We define post-selected classical query algorithms, and relate them to rational approximations of Boolean functions; in particular, by showing that the post-selected classical query complexity of a Boolean function is equal to the minimal degree of a rational function with nonnegative coefficients that approximates it (up to a factor of two). For post-selected quantum query algorithms, a similar relationship was shown by Mahadev and de Wolf, where the rational approximations are allowed to have negative coefficients. Using our characterisation, we find an exponentially large separation between post-selected classical query complexity and post-selected quantum query complexity, by proving a lower bound on the degree of rational approximations to the Majority function.

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-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity