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 Θ(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(k1.5(logk)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.