Abstract

In this talk, I will present the first general connection between the design of quantum algorithms and circuit lower bounds. In our work, we show that non-trivial quantum learning algorithms for circuit classes imply circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and crucially, on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). More concretely, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.

This is a joint work with Srinivasan Arunachalam, Tom Gur, Igor C. Oliveira, and Aarthi Sundaram.

Video Recording