Two new results about quantum exact learning
Open Access
- 24 November 2021
- journal article
- research article
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 5, 587
Abstract
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald de Wolf, Quantum 5, 587 (2021). 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…
Keywords
All Related Versions
Funding Information
- ERC consolidator grant (615307-QPROGRESS)
- Australian Research Council (DP200100950)
- Singapore National Research Foundation (NRF-NRFF2013-13)
- Dutch Research Council (NWO) through Gravitation-grant Quantum Software Consortium (024.003.037)
- Dutch Research Council (NWO) through QuantERA project QuantAlgo (680-91-034)
This publication has 30 references indexed in Scilit:
- Restricted Isometry of Fourier Matrices and List Decodability of Random Linear CodesSIAM Journal on Computing, 2013
- Testing Fourier Dimensionality and SparsitySIAM Journal on Computing, 2011
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- On sparse reconstruction from Fourier and Gaussian measurementsCommunications on Pure and Applied Mathematics, 2007
- Quantum Algorithms for Learning and Testing JuntasQuantum Information Processing, 2007
- Learning functions of k relevant variablesJournal of Computer and System Sciences, 2004
- Equivalences and Separations Between Quantum and Classical LearnabilitySIAM Journal on Computing, 2004
- A polynomial bound in Freiman's theoremDuke Mathematical Journal, 2002
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- A theory of the learnableCommunications of the ACM, 1984