Tata Institute of Fundamental Research
Quantum Exact Learning of k-sparse Functions and Improved Chang's Lemma for Sparse Boolean Functions
STCS Seminar
Speaker:
Sourav Chakraborty (Indian Statistical Institute (ISI)
Kolkata, West Bengal, India)
Organiser:
Arkadev Chattopadhyay
Date:
Friday, 20 Sep 2019, 16:15 to 17:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Sourav Chakraborty (Indian Statistical Institute (ISI) Kolkata, West Bengal, India) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Friday, 20 Sep 2019, 16:15 to 17:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.