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

Sourav Chakraborty
Arkadev Chattopadhyay
Friday, 20 Sep 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.