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

Speaker:

Sourav Chakraborty

Affiliation:

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

Time:

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

Venue:

• A-201 (STCS Seminar Room)

Organisers:

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.