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(log k\)²) uniform quantum examples for that function. This improves over the bound of widetildeΘ(kn) uniformly random 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 Oleft\(frac{Q²}{log Q}log|mathcal{C}|right\) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a log Q-factor.