Two new results about quantum exact learning
Preprint
Abstract
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 $\widetilde{\Theta}(kn)$ uniformly random 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 $\mathcal{C}$ can be exactly learned using $Q$ quantum membership queries, then it can also be learned using $O\left(\frac{Q^2}{\log Q}\log|\mathcal{C}|\right)$ classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a $\log Q$-factor.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Machine learning & artificial intelligence in the quantum domain: a review of recent progressReports on Progress in Physics, 2018
- An Entropic Proof of Chang's InequalitySIAM Journal on Discrete Mathematics, 2014
- Restricted Isometry of Fourier Matrices and List Decodability of Random Linear CodesSIAM Journal on Computing, 2013
- Testing Fourier Dimensionality and Sparsity2009
- On sparse reconstruction from Fourier and Gaussian measurementsCommunications on Pure and Applied Mathematics, 2007
- Quantum Algorithms for Learning and Testing JuntasQuantum Information Processing, 2007
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?IEEE Transactions on Information Theory, 2006
- Learning functions of k relevant variablesJournal of Computer and System Sciences, 2004
- Equivalences and Separations Between Quantum and Classical LearnabilitySIAM Journal on Computing, 2004
- Quantum Complexity TheorySIAM Journal on Computing, 1997