- Home »
- Chris Cade: Post-selected classical query complexity

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.

Collection/Series:

Event Type:

Seminar

Scientific Area(s):

Speaker(s):

Event Date:

Wednesday, January 23, 2019 - 16:00 to 17:30

Location:

Bob Room

Room #:

405

©2012 Perimeter Institute for Theoretical Physics