Abstract: We consider the problem of exact learning of $k$-Fourier sparse Boolean functions. In the classical setting the query complexity, Haviv-Regev (CCC'15) shows that, for learning a function is $\Theta(nk)$, when the function to be learnt takes an $n$ bits string and outputs one bit. In the quantum query we show how to exactly learn a $k$-Fourier-sparse n-bit Boolean function from $O(k^1.5 (log k)^2)$ uniform quantum samples from that function.
Our main tool is an improvement of Chang’s lemma for sparse Boolean functions of high Fourier rank.
This result appears in paper ``Two new results about quantum exact learning" (ICALP 2019) written jointly with Srinivasan Arunachalam, Troy Lee, Manaswi Paraashar and Ronald de Wolf.
