Abstract
I'll discuss some of the complexity-theoretic foundations of quantum supremacy experiments with random quantum circuits, of the sort that Google is planning in the near future with its 72-qubit chip. (Based on my joint work with Lijie Chen.) Then, in a second part of the talk, I'll discuss how these experiments could be used to generate certified random bits.