2019-07-08
Two new results about quantum exact learning
Publication
Publication
Presented at the
46th International Colloquium on Automata, Languages and Programming (ICALP 19) (July 2019), Patras, Greece
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(k1.5(log k)2) uniform quantum examples for that function. This improves over the bound of ̃Θ(kn) uniformly ran- dom classical examples (Haviv and Regev, CCC’15). Our main tool is an improvement of Chang’s lemma for the special case of sparse functions. Second, we show that if a concept class C can be exactly learned using Q quantum membership queries, then it can also be learned us- ing O ( Q2 log Q log |C| ) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP’04) by a log Q-factor.
| Additional Metadata | |
|---|---|
| doi.org/10.4230/LIPIcs.ICALP.2019.16 | |
| Leibniz International Proceedings in Informatics (LIPIcs) | |
| Quantum algorithms and applications | |
| 46th International Colloquium on Automata, Languages and Programming (ICALP 19) | |
| Organisation | Algorithms and Complexity |
|
Arunachalam, S., Chakraborty, S., Lee, T., Paraashar, M., & de Wolf, R. (2019). Two new results about quantum exact learning. In International Colloquium on Automata, Languages, and Programming (pp. 16:1–16:15). doi:10.4230/LIPIcs.ICALP.2019.16 |
|
