During this time of lockdown, the centre for quantum software and information (QSI) at the University of Technology Sydney has launched an online seminar series. With talks once or twice a week from leading researchers in the field, meQuanics is supporting this series by mirroring the audio from each talk. I would encourage if you listen to this episode, to visit and subscribe to the UTS:QSI YouTube page to see each of these talks with the associated slides to help it make more sense.
https://youtu.be/2syrO_asU5Y
Hardness of Random Circuit Sampling (Google's supremacy experiment)
TITLE: Cayley Path and Quantum Supremacy SPEAKER: Dr Ramis Movassagh
AFFILIATION: MIT-IBM Watson AI Lab, Cambridge MA, USA
HOSTED BY: Prof Michael Bremner, UTS Centre for Quantum Software and Information
ABSTRACT: Given the large push 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 that are 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.
RELATED ARTICLES: Unitary-valued paths, and an algebraic proof technique in complexity theory: https://ramismovassagh.wordpress.com/... Cayley path and quantum computational supremacy: A proof of average-case #P−hardness of Random Circuit Sampling with quantified robustness: https://arxiv.org/abs/1909.06210 Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling: https://arxiv.org/abs/1810.04681
OTHER LINKS: Ramis Movassagh Personal Webpage: https://ramismovassagh.wordpress.com/
MIT-IBM Watson AI Lab: https://mitibmwatsonailab.mit.edu/
meQuanics - QSI@UTS Seminar Series - S25 - Adrian Chapman (University of Sydney)
meQuanics - QSI@UTS Seminar Series - S23 - Lieven Vandersypen (QuTech, U. Delft)
meQuanics - QSI@UTS Seminar Series - S22 - Lana Mineh (Bristol University)
meQuanics - QSI@UTS Seminar Series - S21 - Gerardo Paz Silva (Griffith U)
meQuanics - QSI@UTS Seminar Series - S20 - Nana Liu (SJTU)
meQuanics - QSI@UTS Seminar Series - S19 - Yuval Sanders (University of Technology Sydney)
meQuanics - QSI@UTS Seminar Series - S18 - Chris Ferrie (University of Technology Sydney)
meQuanics - QSI@UTS Seminar Series - S17 - Josh Combes (University of Colorado)
meQuanics - QSI@UTS Seminar Series - S16 - Sergio Boixo (Google)
meQuanics - QSI@UTS Seminar Series - S15 - Chris Granade (Microsoft)
meQuanics - QSI@UTS Seminar Series - S14 - Zhengfeng Ji (University of Technology Sydney)
meQuanics - QSI@UTS Seminar Series - S13 - Tom Stace (University of Queensland)
meQuanics - QSI@UTS Seminar Series - S12 - Chris Jackson, (CQuIC)
meQuanics - QSI@UTS Seminar Series - S11 - Kai-Min Chung (Acedemia Sinica)
meQuanics - QSI@UTS Seminar Series - S10 - Marissa Giustina (Google)
meQuanics - QSI@UTS Seminar Series - S09 - Robin Blume-Kohout & Dr Erik Nielsen (Sandia Labs)
meQuanics - QSI@UTS Seminar Series - S08 - Guillaume Verdon (X)
meQuanics - QSI@UTS Seminar Series - S07 - Daniel Grier (U. Waterloo)
meQuanics - QSI@UTS Seminar Series - S06 - Maria Schuld (Xanadu and U. Kwazulu Natal)
Create your
podcast in
minutes
It is Free
DNA Today: A Genetics Podcast
Museum of the Missing
Strange by Nature Podcast
Sasquatch Chronicles
Hidden Brain