1IBM T. J. Watson Research Center
2Indian Statistical Institute, Kolkata, India
3Centre for Quantum Software and Information, University of Technology Sydney, Australia
4QuSoft, CWI and University of Amsterdam, the Netherlands
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
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). Additionally, we provide a possible direction to improve our $widetilde{O}(k^{1.5})$ upper bound by proving an improvement of Chang’s lemma for $k$-Fourier-sparse Boolean 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 $Oleft(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.
► BibTeX data
► References
[1] J. Adcock, E. Allen, M. Day, S. Frick, J. Hinchliff, M. Johnson, S. Morley-Short, S. Pallister, A. Price, and S. Stanisic. Advances in quantum machine learning, 2015. URL https://arxiv.org/abs/1512.02900.
arXiv:1512.02900
[2] A. Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64 (4): 750–767, 2002. 10.1006/jcss.2002.1826. Earlier version in STOC’00.
https://doi.org/10.1006/jcss.2002.1826
[3] S. Arunachalam and R. de Wolf. Guest column: A survey of quantum learning theory. SIGACT News, 48 (2): 41–67, 2017. 10.1145/3106700.3106710. arXiv:1701.06806.
https://doi.org/10.1145/3106700.3106710
arXiv:1701.06806
[4] S. Arunachalam and R. de Wolf. Optimal quantum sample complexity of learning algorithms. Journal of Machine Learning Research, 19, 2018. URL http://jmlr.org/papers/v19/18-195.html. Earlier version in CCC’17.
http://jmlr.org/papers/v19/18-195.html
[5] A. Atıcı and R. Servedio. Quantum algorithms for learning and testing juntas. Quantum Information Processing, 6 (5): 323–348, 2009. 10.1007/s11128-007-0061-6.
https://doi.org/10.1007/s11128-007-0061-6
[6] H. Barnum, M. Saks, and M. Szegedy. Quantum query complexity and semi-definite programming. In Proceedings of 18th IEEE Conference on Computational Complexity, pages 179–193, 2003. 10.1109/CCC.2003.1214419.
https://doi.org/10.1109/CCC.2003.1214419
[7] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/S0097539796300921. Earlier version in STOC’93.
https://doi.org/10.1137/S0097539796300921
[8] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd. Quantum machine learning. Nature, 549 (7671), 2017. 10.1038/nature23474.
https://doi.org/10.1038/nature23474
[9] J. Bourgain. An improved estimate in the restricted isometry problem. In Geometric Aspects of Functional Analysis, volume 2116 of Lecture Notes in Mathematics, pages 65–70. Springer, 2014. 10.1007/978-3-319-09477-9_5.
https://doi.org/10.1007/978-3-319-09477-9_5
[10] N. H. Bshouty and J. C. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. SIAM Journal on Computing, 28 (3): 1136––1153, 1999. 10.1145/225298.225312. Earlier version in COLT’95.
https://doi.org/10.1145/225298.225312
[11] E. J. Candés and T. Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory, 52 (12): 5406–5425, 2006. 10.1109/TIT.2006.885507.
https://doi.org/10.1109/TIT.2006.885507
[12] Sourav Chakraborty, Nikhil S Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, and Swagato Sanyal. Tight Chang’s-lemma-type bounds for Boolean functions, 2020. URL https://arxiv.org/abs/2012.02335.
arXiv:2012.02335
[13] M. C. Chang. A polynomial bound in Freiman’s theorem. Duke Mathematics Journal, 113 (3): 399–419, 2002. 10.1215/S0012-7094-02-11331-3.
https://doi.org/10.1215/S0012-7094-02-11331-3
[14] M. Cheraghchi, V. Guruswami, and A. Velingker. Restricted isometry of Fourier matrices and list decodability of random linear codes. SIAM Journal on Computing, 42 (5): 1888–1914, 2013. 10.1137/120896773.
https://doi.org/10.1137/120896773
[15] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, 1991. 10.1002/047174882X.
https://doi.org/10.1002/047174882X
[16] V. Dunjko and H. J. Briegel. Machine learning & artificial intelligence in the quantum domain: a review of recent progress. Reports on Progress in Physics, 81 (7): 074001, 2018. 10.1088/1361-6633/aab406.
https://doi.org/10.1088/1361-6633/aab406
[17] P. Gopalan, R. O’Donnell, R. A. Servedio, A. Shpilka, and K. Wimmer. Testing Fourier dimensionality and sparsity. SIAM Journal on Computing, 40 (4): 1075–1100, 2011. 10.1137/100785429. Earlier version in ICALP’09.
https://doi.org/10.1137/100785429
[18] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th ACM STOC, pages 212–219, 1996. 10.1145/237814.237866.
https://doi.org/10.1145/237814.237866
[19] A. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for solving linear systems of equations. Physical Review Letters, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https://doi.org/10.1103/PhysRevLett.103.150502
[20] H. Hassanieh, P. Indyk, D. Katabi, and E. Price. Nearly optimal sparse Fourier transform. In Proceedings of 44th ACM STOC, pages 563–578, 2012. 10.1145/2213977.2214029.
https://doi.org/10.1145/2213977.2214029
[21] I. Haviv and O. Regev. The list-decoding size of Fourier-sparse Boolean functions. ACM Transactions on Computation Theory, 8 (3): 10:1–10:14, 2016. 10.1145/2898439. Earlier version in CCC’15.
https://doi.org/10.1145/2898439
[22] P. Indyk and M. Kapralov. Sample-optimal Fourier sampling in any constant dimension. In Proceedings of 55th IEEE FOCS, pages 514–523, 2014. 10.1109/FOCS.2014.61.
https://doi.org/10.1109/FOCS.2014.61
[23] E. Mossel, R. O’Donnell, and R. Servedio. Learning functions of $k$ relevant variables. Journal of Computer and System Sciences, 69 (3): 421–434, 2004. 10.1016/j.jcss.2004.04.002. Earlier version in STOC’03.
https://doi.org/10.1016/j.jcss.2004.04.002
[24] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667
[25] R. O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. 10.1017/CBO9781139814782.
https://doi.org/10.1017/CBO9781139814782
[26] M. Rudelson and R. Vershynin. On sparse reconstruction from Fourier and Gaussian measurements. Communications on Pure and Applied Mathematics, 61 (8): 1025–1045, 2008. 10.1002/cpa.20227.
https://doi.org/10.1002/cpa.20227
[27] Swagato Sanyal. Fourier sparsity and dimension. volume 15, pages 1–13. Theory of Computing, 2019. 10.4086/toc.2019.v015a011.
https://doi.org/10.4086/toc.2019.v015a011
[28] M. Schuld, I. Sinayskiy, and F. Petruccione. An introduction to quantum machine learning. Contemporary Physics, 56 (2): 172–185, 2015. 10.1080/00107514.2014.964942.
https://doi.org/10.1080/00107514.2014.964942
[29] R. Servedio and S. Gortler. Equivalences and separations between quantum and classical learnability. SIAM Journal on Computing, 33 (5): 1067–1092, 2004. 10.1137/S0097539704412910. Combines earlier papers from ICALP’01 and CCC’01.
https://doi.org/10.1137/S0097539704412910
[30] R. Špalek and M. Szegedy. All quantum adversary methods are equivalent. In Proceedings of 32nd ICALP, volume 3580 of Lecture Notes in Computer Science, pages 1299–1311, 2005. 10.1007/11523468_105.
https://doi.org/10.1007/11523468_105
[31] L. Valiant. A theory of the learnable. Communications of the ACM, 27 (11): 1134–1142, 1984. 10.1145/1968.1972.
https://doi.org/10.1145/1968.1972
[32] K. A. Verbeurgt. Learning DNF under the uniform distribution in quasi-polynomial time. In Proceedings of 3rd Annual Workshop on Computational Learning Theory (COLT’90), pages 314–326, 1990. URL https://dl.acm.org/doi/10.5555/92571.92659.
https://dl.acm.org/doi/10.5555/92571.92659
[33] P. Wittek. Quantum Machine Learning: What Quantum Computing Means to Data Mining. Elsevier, 2014. 10.1016/C2013-0-19170-2.
https://doi.org/10.1016/C2013-0-19170-2
[34] R. de Wolf. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing, 2008. 10.4086/toc.gs.2008.001. ToC Library, Graduate Surveys 1.
https://doi.org/10.4086/toc.gs.2008.001
[35] A. C-C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of 18th IEEE FOCS, pages 222–227, 1977. 10.1109/SFCS.1977.24.
https://doi.org/10.1109/SFCS.1977.24
Cited by
[1] Srinivasan Arunachalam and Reevu Maity, “Quantum Boosting”, arXiv:2002.05056.
[2] Srinivasan Arunachalam, Alex B. Grilo, and Aarthi Sundaram, “Quantum hardness of learning shallow classical circuits”, arXiv:1903.02840.
[3] András Gilyén and Tongyang Li, “Distributional property testing in a quantum world”, arXiv:1902.00814.
[4] Matthias C. Caro, “Quantum learning Boolean linear functions w.r.t. product distributions”, Quantum Information Processing 19 6, 172 (2020).
The above citations are from SAO/NASA ADS (last updated successfully 2021-11-29 14:57:49). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2021-11-29 14:57:47).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.
Source: https://quantum-journal.org/papers/q-2021-11-24-587/
