Quantum advantage via the statistical lens
At their heart, many of the fundamental questions in science and at the cutting-edge of practice are questions about statistical learnability. Yet, they often fall outside the purview of "traditional" statistics and learning theory. In this talk, I will argue that the statistical lens can be a powerful tool for understanding these questions, and that this perspective can yield deep and surprising insights in both theory and practice. I will give a concrete example of this in my work on quantum computing. Here, one of the basic questions is that of quantum advantage: can existing quantum devices do something that classical computers provably cannot? While there has been significant work in this area, progress has been non-monotone, and work is typically conditional on very strong complexity theoretic assumptions which far exceed our current abilities to prove. Here, I will describe a completely different approach to demonstrating quantum advantage via statistical methods, based on proving tight minimax rates for quantum learning with and without quantum memory. Our techniques are purely statistical in nature, and thus, not conditional on any assumptions. By leveraging these ideas, we are able to give an unconditional demonstration of quantum advantage on a real quantum computer [Huang et al, Science 2022]. This is arguably the one of the first such demonstrations, in any setting, ever.
No background on quantum computing will be necessary or assumed for the talk.