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(log k)2) uniform quantum examples for that function. This improves over the bound of ̃Θ(kn) uniformly ran- dom 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 a concept class C can be exactly learned using Q quantum membership queries, then it can also be learned us- ing O ( Q2 log Q log |C| ) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP’04) by a log Q-factor.

Leibniz International Proceedings in Informatics
Quantum algorithms and applications
46th International Colloquium on Automata, Languages and Programming (ICALP 19)
Algorithms and Complexity

Arunachalam, S, Chakraborty, S, Lee, T. J, Paraashar, M, & de Wolf, R.M. (2019). Two new results about quantum exact learning. In International Colloquium on Automata, Languages, and Programming (pp. 16:1–16:15). doi:10.4230/LIPIcs.ICALP.2019.16