Post-selected Classical Query Complexity

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

• Chris Cade (University of Bristol)
• Thursday 07 February 2019, 14:15-15:15
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

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.

This talk is included in these lists:

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

Note that ex-directory lists are not shown.