Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The first demonstration of quantum supremacy in October 2019 was a major achievement of experimental physics. At the same time, it relied on important developments in theoretical computer science. In this talk I will describe my recent work laying the complexity-theoretic foundations for Google/UCSB’s quantum supremacy experiment, providing evidence that their device is exponentially difficult to simulate with a classical computer. This crossroad between complexity theory and quantum physics also offers new insights into both disciplines. For example, I will explain how techniques from quantum complexity theory can be used to settle purely classical problems. Specifically, I will describe a quantum argument which nearly resolves the approximate degree composition conjecture, generalizing nearly 20 years of prior work. In a different direction, I will show that the notion of computational pseudorandomness from complexity-based cryptography has fundamental implications for black hole physics and the theory of quantum gravity.

There will be a light reception at 2:30pm