Lecture Computer Science: Quantum Computational Supremacy

Scott J. Aaronson

In Fall 2019, a team at Google made the first-ever claim of "quantum computational supremacy"---that is, a clear quantum speedup over a classical computer for some task---using a 53-qubit programmable superconducting chip called Sycamore. Since then, a group at USTC in China has made several additional claims of quantum supremacy, using both superconducting qubits and "BosonSampling" (a proposal by me and Alex Arkhipov from 2011) with ~70 photons in an optical network. In addition to engineering, these experiments built on a decade of research in quantum complexity theory. This talk will discuss questions like: what exactly were the contrived computational problems that were solved? How does one verify the outputs using a classical computer? And crucially, how confident can we be that the problems are really classically hard?

---