## Speaker:

## Affiliation:

Indian Statistical Institute (ISI)

Kolkata, West Bengal, India

## Time:

## 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.