Colloquium

Google's recent announcement of quantum computational supremacy was exciting from various physics and engineering standpoints, but what about math? In this talk, I'll explain the probability distributions over \(\{0,1\}^{53}\) from which Google extracted samples, and what we know about those distributions' statistical properties. As we'll see, this topic ties together everything from Archimedes' hat-box theorem of ~200BC, to the fact that amplitudes in quantum mechanics are over \(\mathbb{C}\) rather than \(\mathbb{R}\). And it has implications for questions of such obvious relevance as: how do you verify, using a classical computer, that Google did its experiment correctly? And how confident can we be, in the present state of theoretical computer science, that the task Google perform really is classically hard?

Based in part on joint work with Lijie Chen, Sam Gunn, and others.

[video recording]

1:30-2:30: introductory lecture for students