BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Ramis Movassagh (MIT-IBM Watson AI Lab) DTSTART:20200702T233000Z DTEND:20200703T003000Z DTSTAMP:20260423T041751Z UID:UTSQSI/12 DESCRIPTION:Title: Cayley Path and Quantum Supremacy\nby Ramis Movassagh (MIT-IBM Watson AI Lab) as part of Centre for Quantum Software and Information Seminar Ser ies\n\n\nAbstract\nGiven the large push by academia and industry (e.g.\, I BM and Google)\, quantum computers with hundred(s) of qubits are at the br ink of existence with the promise of outperforming any classical computer. Demonstration of computational advantages of noisy near-term quantum comp uters over classical computers is an imperative near-term goal. The foremo st candidate task for showing this is Random Circuit Sampling (RCS)\, whic h is the task of sampling from the output distribution of a random circuit . This is exactly the task that recently Google experimentally performed o n 53-qubits.\n\nStockmeyer's theorem implies that efficient sampling allow s for estimation of probability amplitudes. Therefore\, hardness of probab ility estimation implies hardness of sampling. We prove that estimating pr obabilities to within small errors is #P-hard on average (i.e. for random circuits)\, and put the results in the context of previous works.\n\nSome ingredients that are developed to make this proof possible are constructio n of the Cayley path as a rational function valued unitary path that inter polate between two arbitrary unitaries\, an extension of Berlekamp-Welch a lgorithm that efficiently and exactly interpolates rational functions\, an d construction of probability distributions over unitaries that are arbitr arily close to the Haar measure.\n LOCATION:https://researchseminars.org/talk/UTSQSI/12/ END:VEVENT END:VCALENDAR