Quantum Exact Learning of k-sparse Functions and Improved Chang's Lemma for Sparse Boolean Functions


Sourav Chakraborty


Indian Statistical Institute (ISI)
Kolkata, West Bengal, India


Friday, 20 September 2019, 16:15 to 17:15


  • A-201 (STCS Seminar Room)


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.