Scott Aaronson
University of Texas at Austin
Austin — Texas — U.S.A.
Quantum Computational Supremacy
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. In Fall 2020, a group at USTC in China made a claim of quantum supremacy, using "BosonSampling" (a proposal by me and Alex Arkhipov in 2011) with 50-70 photons in an optical network. In addition to engineering, these accomplishments 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 how sure are we that the problems are indeed classically hard? I'll end with a proposed application for these sampling based quantum supremacy experiments that I've been working on: namely, the generation of certified random bits, for use (for example) in proof of-stake cryptocurrencies.
