Two new results about quantum exact learning
This addresses efficiency in quantum learning algorithms for researchers in quantum computing and learning theory, with incremental improvements over existing bounds.
The paper tackles the problem of exact learning by quantum computers, showing that a k-Fourier-sparse Boolean function can be learned from O(k^1.5 (log k)^2) quantum examples, improving over classical bounds, and that quantum membership queries can be simulated by classical ones with a O(Q^2/log Q log|C|) cost, improving prior results.
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a $k$-Fourier-sparse $n$-bit Boolean function from $O(k^{1.5}(\log k)^2)$ uniform quantum examples for that function. This improves over the bound of $\widetildeΘ(kn)$ uniformly random \emph{classical} examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our $\widetilde{O}(k^{1.5})$ upper bound by proving an improvement of Chang's lemma for $k$-Fourier-sparse Boolean functions. Second, we show that if a concept class $\mathcal{C}$ can be exactly learned using $Q$ quantum membership queries, then it can also be learned using $O\left(\frac{Q^2}{\log Q}\log|\mathcal{C}|\right)$ \emph{classical} membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a $\log Q$-factor.