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.