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(k1.5(logk)2) uniform quantum examples for that function. This improves over the bound of Θ˜(kn) uniformly random \emph{classical} examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our O˜(k1.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 C can be exactly learned using Q quantum membership queries, then it can also be learned using O(Q2logQlog|C|) \emph{classical} membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a logQ-factor.

IBM Research, Thomas J. Watson Research Center, USA
Algorithms and Complexity

Arunachalam, S, Chakraborty, S, Lee, T. J, Paraashar, M, & de Wolf, R.M. (2021). Two new results about quantum exact learning.