Physics Colloquium

Prof. Scott Aaronson, Department of Computer Science, UT-Austin

"Quantum Supremacy"

4:00pm, The John A. Wheeler Lecture Hall (RLM 4.102). Coffee and cookies will be served at 3:45pm in RLM 4.102

Abstract:

In the near future, it will likely become possible to perform special-purpose quantum computations that, while not immediately useful for anything, are plausibly hard to simulate using a classical computer. These "quantum supremacy experiments" would be a scientific milestone -- decisively answering quantum computing skeptics, while casting doubt on one of the foundational tenets of computer science, the Extended Church-Turing Thesis. At the same time, these experiments also raise fascinating theoretical questions: for example, on what grounds should we believe that a given quantum system really is hard to simulate classically? Does classical simulation become easier as a quantum system becomes noisier? And how do we verify the results of such an experiment? In this lecture, I'll discuss recent results and open problems about these questions, using the following three examples:

- BosonSampling (proposed by myself and Alex Arkhipov in 2011, and since experimentally demonstrated on a small scale by numerous quantum optics groups)

- Fourier Sampling / Commuting Hamiltonians (studied by myself and by Bremner, Jozsa and Shepherd)

- Random quantum circuits sampling (the focus of a large-scale planned experiment by John Martinis's group at Google, and also of brand-new theoretical work by myself and Lijie Chen)