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\left({k}^{1.5}\left(\mathrm{log}k{\right)}^{2}\right)$ uniform quantum examples for that function. This improves over the bound of $\stackrel{~}{\Theta }\left(kn\right)$ uniformly random \emph{classical} examples (Haviv and Regev, CCC'15). 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}}{\mathrm{log}Q}\mathrm{log}|\mathcal{C}|\right)$ \emph{classical} membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a $\mathrm{log}Q$ -factor.
arXiv.org e-Print archive
Algorithms and Complexity

Arunachalam, S, Chakraborty, S, Lee, T. J, & de Wolf, R.M. (2018). Two new results about quantum exact learning. arXiv.org e-Print archive.