Certified Randomness from Quantum Supremacy

After three decades of research in quantum computing theory and experiments, the world has seen the emergence of noisy quantum devices capable of solving special sampling problems using 50-60 qubits or approximately 100 photons in a way that is believed to achieve quantum computational supremacy, i.e., the quantum devices outperform any existing classical computer for these tasks. Despite these achievements, whether they lead to practical applications have remained unclear.

In this talk, I will discuss the latest developments in quantum supremacy proposals and applications from them. Then I will focus on my recent work on certified randomness from random circuit sampling, where we show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain min-entropy proportional to the number of qubits. This novel application challenges us to further explore the limitations of quantum devices, and repurposes the supremacy experiment for practical uses. This talk is based on joint work with Scott Aaronson.