BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Post-selected Classical Query Complexity - Chris
Cade (University of Bristol)
DTSTART;TZID=Europe/London:20190207T141500
DTEND;TZID=Europe/London:20190207T151500
UID:TALK118930AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/118930
DESCRIPTION:The precise relationship between post-selected cla
ssical 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 n
o less true in the area of computational complexit
y -- quantum computations augmented with post-sele
ction are thought to be vastly more powerful than
their classical counterparts. However\, the precis
e reasons why this might be the case are not well
understood\, and no rigorous separations between t
he two have been found. In this talk\, I will cons
ider the difference in computational power of clas
sical and quantum post-selection in the computatio
nal query complexity setting. \n\nWe define post-s
elected classical query algorithms\, and relate th
em to rational approximations of Boolean functions
\; in particular\, by showing that the post-select
ed classical query complexity of a Boolean functio
n is equal to the minimal degree of a rational fun
ction with nonnegative coefficients that approxima
tes 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 ratio
nal approximations are allowed to have negative co
efficients. Using our characterisation\, we find a
n exponentially large separation between post-sele
cted classical query complexity and post-selected
quantum query complexity\, by proving a lower boun
d on the degree of rational approximations to the
Majority function.
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberfor
ce Road\, Cambridge
CONTACT:Johannes Bausch
END:VEVENT
END:VCALENDAR