Scott Aaronson @ Theory Lunch

Title: Quantum Computational Supremacy And Its Applications

Abstract: Last fall, a team at Google announced the first-ever demonstration of "quantum computational supremacy" using a 53-qubit programmable superconducting chip called Sycamore. In addition to engineering, this accomplishment built on a decade of research in quantum complexity theory. In this talk, I'll start by discussing: what exactly was the "Random Circuit Sampling" task that Sycamore performed? How does one verify the outputs using a classical computer? And how confident are we that the problem is classically intractable? I'll end with a proposed application for Random Circuit Sampling---namely, the generation of certified random bits, for use (for example) in proof-of-stake cryptocurrencies---that I developed and that Google is currently working to demonstrate.

Based in part on joint works with Lijie Chen (CCC'2017) and Sam Gunn (arXiv:1910.12085).

Видео Scott Aaronson @ Theory Lunch канала Princeton TCS