2018-09-30
Two new results about quantum exact learning
Publication
Publication
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a
Fourier-sparse
-bit Boolean function from
uniform quantum examples for that function. This improves over the bound of
uniformly random \emph{classical} examples (Haviv and Regev, CCC'15). Second, we show that if a concept class
can be exactly learned using
quantum membership queries, then it can also be learned using
\emph{classical} membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a
-factor.
Additional Metadata | |
---|---|
arXiv.org e-Print archive | |
Organisation | Algorithms and Complexity |
Arunachalam, S, Chakraborty, S, Lee, T. J, & de Wolf, R.M. (2018). Two new results about quantum exact learning. arXiv.org e-Print archive.
|