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:Quantum states cannot be transmitted efficiently c
lassically - Ashley Montanaro\, Bristol
DTSTART;TZID=Europe/London:20170512T120000
DTEND;TZID=Europe/London:20170512T130000
UID:TALK72383AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/72383
DESCRIPTION:In this talk I will discuss recent work showing th
at any classical communication protocol that can a
pproximately simulate the result of applying an ar
bitrary measurement (held by one party) to a quant
um state of n qubits (held by another) must transm
it at least 2^n bits\, up to constant factors. The
argument is based on proving a lower bound on the
classical communication complexity of a distribut
ed variant of the Fourier sampling problem. Two op
timal quantum-classical separations follow as coro
llaries. First\, a sampling problem which can be s
olved with one quantum query to the input\, but wh
ich requires order-N classical queries for an inpu
t of size N. Second\, a nonlocal task which can be
solved using n Bell pairs\, but for which any app
roximate classical solution must communicate 2^n b
its\, up to constant factors.\n\nThe talk will be
based on the paper arXiv:1612.06546.\n
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Steve Brierley
END:VEVENT
END:VCALENDAR