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., Paraashar, M., & de Wolf, R. (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