The precise relationship between post-selected classical and post-selected quantum computation is an open problem in complexity theory, and lies at the heart of many results in the area of quantum computational supremacy. In this talk, I will consider the difference in computational power of classical and quantum post-selection in the query 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.