Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR20-185 | 1st December 2020 22:32

#### Quantum learning algorithms imply circuit lower bounds

TR20-185
Authors: Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram
Publication: 13th December 2020 09:09
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathrm{C}$ be a class of polynomial-size concepts, and suppose that $\mathrm{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 $\mathrm{BQE} \not\subseteq \mathrm{C}$, where $\mathrm{BQE} = \mathrm{BQTIME}[2^{O(n)}]$ is an exponential-time analogue of $\mathrm{BQP}$. This result is optimal in both $\gamma$ and $T$, since it is not hard to learn any class $\mathcal{C}$ of functions in (classical) time $T = 2^n$ (with no error), or in quantum time $T = \mathrm{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.