Two new results about quantum exact learning

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee +2

We present two new results about exact learning by quantum computers. First, we show how to exactly learn a $k$-Fourier-sparse $n$-bit Boolean function from $O(k^{1.5}(\log k{)}^2)$…