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 ) uniform quantum examples for that function. This improves over the bound of Θ ~ ( k n ) uniformly random \emph{classical} examples (Haviv and Regev, CCC'15). Second, we show that if a concept class C can be exactly learned using Q quantum membership queries, then it can also be learned using O ( Q 2 log Q log | C | ) \emph{classical} membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a log Q -factor.
Additional Metadata
Series arXiv.org e-Print archive
Arunachalam, S, Chakraborty, S, Lee, T. J, & de Wolf, R. M. (2018). Two new results about quantum exact learning. arXiv.org e-Print archive.