Colloquium Details

Quantum Advantage via the Statistical Lens

Speaker: Jerry Li, Microsoft

Location: 60 Fifth Avenue Room 150

Date: March 5, 2024, 2 p.m.

Host: Michael Overton


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 probably 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, in work recently published in Science, we are able to give an unconditional demonstration of quantum advantage on a real-world quantum computer. This is arguably the one of the first such demonstrations, in any setting, ever.

Speaker Bio:

Jerry is a Principal Research Scientist at Microsoft Research, Redmond. Prior to this, he was the VMWare Research Fellow at the Simons Institute. He obtained his PhD from MIT, where he was advised by Ankur Moitra. He is primarily interested in aspects of statistical learning theory, broadly defined. He has worked on a wide array of topics, including robust statistics, mixture models, distributed optimization, semi-random models, AI alignment, and more recently, quantum information theory and theoretical aspects of large generative models. For his PhD work on robust statistics, he was awarded the George M. Sprowls Award for outstanding Ph.D. thesis in EECS at MIT. He has published in many top conferences and journals, including Science and Nature Communications, and his work has been featured in the Communications of the ACM.


In-person attendance only available to those with active NYU ID cards.

How to Subscribe