BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Cayley path and quantum supremacy: Average case #P-Hardness of ran
 dom circuit sampling - Ramis Movassagh\, IBM Research
DTSTART:20200527T131500Z
DTEND:20200527T141500Z
UID:TALK142651@talks.cam.ac.uk
CONTACT:Sergii Strelchuk
DESCRIPTION:Given the unprecedented effort by academia and industry (e.g.\
 , IBM and Google)\, quantum computers with hundred(s) of qubits are at the
  brink of existence with the promise of outperforming any classical comput
 er. Demonstration of computational advantages of noisy near-term quantum c
 omputers over classical computers is an imperative near-term goal. The for
 emost candidate task for showing this is Random Circuit Sampling (RCS)\, w
 hich is the task of sampling from the output distribution of a random circ
 uit. This is exactly the task that recently Google experimentally performe
 d on 53-qubits.\n\nStockmeyer's theorem implies that efficient sampling al
 lows for estimation of probability amplitudes. Therefore\, hardness of pro
 bability estimation implies hardness of sampling. We prove that estimating
  probabilities to within small errors is #P-hard on average (i.e. for rand
 om circuits)\, and put the results in the context of previous works.\n\nSo
 me ingredients developed to make this proof possible are construction of t
 he Cayley path as a rational function valued unitary path that interpolate
  between two arbitrary unitaries\, an extension of Berlekamp-Welch algorit
 hm that efficiently and exactly interpolates rational functions\, and cons
 truction of probability distributions over unitaries that are arbitrarily 
 close to the Haar measure.\n----\nThis talk will be delivered remotely. Th
 ose wishing to join the broadcast please contact Sergii Strelchuk (ss870@c
 am.ac.uk)
LOCATION:Zoom
END:VEVENT
END:VCALENDAR