COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > CQIF Seminar > Cayley path and quantum supremacy: Average case #P-Hardness of random circuit sampling

## Cayley path and quantum supremacy: Average case #P-Hardness of random circuit samplingAdd to your list(s) Download to your calendar using vCal - Ramis Movassagh, IBM Research
- Wednesday 27 May 2020, 14:15-15:15
- Zoom.
If you have a question about this talk, please contact Sergii Strelchuk. 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 computer. Demonstration of computational advantages of noisy near-term quantum computers over classical computers is an imperative near-term goal. The foremost candidate task for showing this is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. This is exactly the task that recently Google experimentally performed on 53-qubits. Stockmeyer’s theorem implies that efficient sampling allows for estimation of probability amplitudes. Therefore, hardness of probability estimation implies hardness of sampling. We prove that estimating probabilities to within small errors is #P-hard on average (i.e. for random circuits), and put the results in the context of previous works. Some ingredients developed to make this proof possible are construction of the Cayley path as a rational function valued unitary path that interpolate between two arbitrary unitaries, an extension of Berlekamp-Welch algorithm that efficiently and exactly interpolates rational functions, and construction of probability distributions over unitaries that are arbitrarily close to the Haar measure. —— This talk will be delivered remotely. Those wishing to join the broadcast please contact Sergii Strelchuk (ss870@cam.ac.uk) This talk is part of the CQIF Seminar series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsWomen's Word European Research Group MARLEN KHUTSIEV IN CAMBRIDGE AND LONDON## Other talksStudies in Natural Product Synthesis DNA repair: from mechanistic insights to therapeutic applications in cancer Cancer metabolism, a hallmark of cancer The common link between schizophrenia and diabetes Multi-Asset Noisy Rational Expectations Equilibrium with Contingent Claims TBA |