In the wake of Google's bombshell announcement of quantum computational supremacy, using random circuit sampling with a 53-qubit superconducting device, I'll discuss the current state and future prospects of the theoretical foundations of this sort of experiment. Topics will include:

- The quest for sampling-based quantum supremacy under more secure computational assumptions.

- The quest for sampling-based quantum supremacy with efficient classical verification of the outputs.

- Potential applications of sampling-based quantum supremacy, including to the generation of cryptographically certified random bits.

This talk will build on the tutorial talks by Adam Bouland.

Video Recording