Two new results about quantum exact learning

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(logk)²) uniform quantum examples for that function. This improves over the bound of Θ˜(^kn) uniformly random classical examples (Haviv and Regev, CCC'15). Our main tool is an improvement of Chang's lemma for the special case of sparse functions. Second, we show that if aconcept class C can be exactly learned using Q quantum membership queries, then it can also be learned using O((Q²/logQ)log|C|) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a log Q-factor.