Colloquium Speaker Speaker: Umesh Vazirani, University of California at Berkeley Title: Theoretical Reflections on Quantum Supremacy Date: Wednesday, May 19 Time: 12:30pm ET Hosts: Sanjeev Arora & Andrew Houck Event page: [ https://www.cs.princeton.edu/events/26082 | https://www.cs.princeton.edu/events/26082 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_6zJv9owaS3WOuss4Gg7_7A | https://princeton.zoom.us/webinar/register/WN_6zJv9owaS3WOuss4Gg7_7A ] Abstract: The recent demonstration of quantum supremacy by Google is a first step towards the era of small to medium scale quantum computers. In this talk I will explain what the experiment accomplished and the theoretical work it is based on, as well as what it did not accomplish and the many theoretical and practical challenges that remain. I will also describe recent breakthroughs in the design of protocols for the testing and benchmarking of quantum computers, a task that has deep computational and philosophical implications. Specifically, this leads to protocols for scalable and verifiable quantum supremacy, certifiable quantum random generation and verification of quantum computation. Bio: Umesh Vazirani is Strauch Distinguished Professor of Computer Science at UC Berkeley, and Director of the Berkeley Quantum Computing Center (BQIC). His 1993 paper with Ethan Bernstein laid the foundations of quantum complexity theory, and his research has touched on many facets of quantum computation, including Quantum Algorithms, Quantum Hamiltonian Complexity and Interactive classical testing of quantum devices. Vazirani is co-inventor of the Bid Scaling algorithm for the AdWords auction which is widely used by Internet search companies, and co-winner of the Fulkerson Prize for the ARV graph partitioning algorithm. He is member of the NAS, and co-author of two books: An Introduction to Computational Learning Theory (MIT Press) and Algorithms (McGraw-Hill).