Quantum learning algorithms imply circuit lower bounds

Srinivasan Arunachalam, Alex B. Grilo, Tom Gur +2

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…