Quantum learning algorithms imply circuit lower bounds
  We establish the first general connection between the design of quantum
algorithms and circuit lower bounds. Specifically, let $\mathfrak{C}$ be a
class of polynomial-size concepts, and suppose that $\mathfrak{C}$ can be
PAC-learned with membership queries under the uniform distribution with error
$1/2 - \gamma$ by a time $T$ quantum algorithm. We prove that if $\gamma^2
\cdot T \ll 2^n/n$, then $\mathsf{BQE} \nsubseteq \mathfrak{C}$, where
$\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]$ is an exponential-time analogue of
$\mathsf{BQP}$. This result is optimal in both $\gamma$ and $T$, since it is
not hard to learn any class $\mathfrak{C}$ of functions in (classical) time $T
= 2^n$ (with no error), or in quantum time $T = \mathsf{poly}(n)$ with error at
most $1/2 - \Omega(2^{-n/2})$ via Fourier sampling. In other words, even a
marginal improvement on these generic learning algorithms would lead to major
consequences in complexity theory.
  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). Extending their approach to quantum learning
algorithms turns out to create significant challenges. To achieve that, 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.
