BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Post-selected Classical Query Complexity  - Chris Cade (University
  of Bristol)
DTSTART:20190207T141500Z
DTEND:20190207T151500Z
UID:TALK118930@talks.cam.ac.uk
CONTACT:Johannes Bausch
DESCRIPTION:The precise relationship between post-selected classical and p
 ost-selected quantum computation is an open problem in complexity theory. 
 Post-selection has proven to be a useful tool in uncovering some of the di
 fferences between quantum and classical theories\, in foundations and else
 where. This is no less true in the area of computational complexity -- qua
 ntum computations augmented with post-selection are thought to be vastly m
 ore powerful than their classical counterparts. However\, the precise reas
 ons why this might be the case are not well understood\, and no rigorous s
 eparations between the two have been found. In this talk\, I will consider
  the difference in computational power of classical and quantum post-selec
 tion in the computational query complexity setting. \n\nWe define post-sel
 ected classical query algorithms\, and relate them to rational approximati
 ons of Boolean functions\; in particular\, by showing that the post-select
 ed classical query complexity of a Boolean function is equal to the minima
 l degree of a rational function with nonnegative coefficients that approxi
 mates it (up to a factor of two). For post-selected quantum query algorith
 ms\, a similar relationship was shown by Mahadev and de Wolf\, where the r
 ational approximations are allowed to have negative coefficients. Using ou
 r characterisation\, we find an exponentially large separation between pos
 t-selected classical query complexity and post-selected quantum query comp
 lexity\, by proving a lower bound on the degree of rational approximations
  to the Majority function. 
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberforce Road\, Cambr
 idge
END:VEVENT
END:VCALENDAR