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:Cayley path and quantum supremacy: Average case #P
-Hardness of random circuit sampling - Ramis Movas
sagh\, IBM Research
DTSTART;TZID=Europe/London:20200527T141500
DTEND;TZID=Europe/London:20200527T151500
UID:TALK142651AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/142651
DESCRIPTION:Given the unprecedented effort by academia and ind
ustry (e.g.\, IBM and Google)\, quantum computers
with hundred(s) of qubits are at the brink of exis
tence with the promise of outperforming any classi
cal computer. Demonstration of computational advan
tages of noisy near-term quantum computers over cl
assical computers is an imperative near-term goal.
The foremost candidate task for showing this is R
andom Circuit Sampling (RCS)\, which is the task o
f sampling from the output distribution of a rando
m circuit. This is exactly the task that recently
Google experimentally performed on 53-qubits.\n\nS
tockmeyer's theorem implies that efficient samplin
g allows for estimation of probability amplitudes.
Therefore\, hardness of probability estimation im
plies hardness of sampling. We prove that estimati
ng probabilities to within small errors is #P-hard
on average (i.e. for random circuits)\, and put t
he results in the context of previous works.\n\nSo
me ingredients developed to make this proof possib
le are construction of the Cayley path as a ration
al function valued unitary path that interpolate b
etween two arbitrary unitaries\, an extension of B
erlekamp-Welch algorithm that efficiently and exac
tly interpolates rational functions\, and construc
tion of probability distributions over unitaries t
hat are arbitrarily close to the Haar measure.\n--
--\nThis talk will be delivered remotely. Those wi
shing to join the broadcast please contact Sergii
Strelchuk (ss870@cam.ac.uk)
LOCATION:Zoom
CONTACT:Sergii Strelchuk
END:VEVENT
END:VCALENDAR