Hot Topics in Computing: Quantum Computational Supremacy and its Applications

Scott Aaronson, Prof. UT Austin

Scott Aaronson, Professor, UT Austin

This fall, a team at Google announced the first-ever demonstration of “quantum computational supremacy”. In addition to the engineering accomplishment, Google’s experiment built on a decade of research in quantum complexity theory, some of which we did at MIT with students. This talk will discuss questions like: what exactly was the contrived problem that Google solved? How does one verify the outputs using a classical computer? And how confident are we that the problem is classically hard—especially in light of subsequent counterclaims by IBM? I’ll end with a proposed application for Google’s experiment—namely, the generation of certified random bits, for use (for example) in proof-of-stake cryptocurrencies—that I’ve been developing and that Google is now working to demonstrate.

Scott Aaronson is David J. Bruton Centennial Professor of Computer Science at the University of Texas at Austin. Prior to UT Austin, Aaronson spent nine years as a professor at MIT in EECS. Aaronson’s research in theoretical computer science has focused mainly on the capabilities and limits of quantum computers. His first book, Quantum Computing Since Democritus, was published in 2013 by Cambridge University Press. He received the National Science Foundation’s Alan T. Waterman Award, the United States PECASE Award, the Vannevar Bush Fellowship, the Tomassoni-Chisesi Prize in  Physics, and MIT’s Junior Bose Award for Excellence in Teaching.