Abstract
I'll discuss an open problem that I see as central to the project of verifiable NISQ quantum supremacy. Basically: among all quantum circuits of a given size whose outputs are heavily concentrated on one computational basis state, do most have properties that make them easy to distinguish classically from completely random quantum circuits, given the circuit descriptions?
I'll connect this to a recent open problem of Paul Christiano, which he sees as central to the project of AI interpretability. Basically: among all neural nets of a given size whose outputs avoid a particular string, do most have properties that make them easy to distinguish (including via NP witnesses) from completely random neural nets, given the weight vectors?
I'll present numerical results about these questions, drawing in part on recent joint work with Yuxuan Zhang (https://arxiv.org/abs/2404.14493)