Document Open Access Logo

Two New Results About Quantum Exact Learning

Authors Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.16.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Hardware → Quantum computation
  • Theory of computation → Sample complexity and generalization bounds
  • Theory of computation → Boolean function learning
Keywords
  • quantum computing
  • exact learning
  • analysis of Boolean functions
  • Fourier sparse Boolean functions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Theta~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Our main tool is an improvement of Chang’s lemma for sparse Boolean 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 using O ({Q^2}/{log Q} * log|C|) classical membership queries. This improves the previous-best simulation result (Servedio-Gortler, SICOMP'04) by a log Q-factor.

Cite As Get BibTex

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald de Wolf. Two New Results About Quantum Exact Learning. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.16

Author Details

Srinivasan Arunachalam
  • Center for Theoretical Physics, MIT, Cambridge, MA, USA
Sourav Chakraborty
  • Indian Statistical Institute, Kolkata, India
Troy Lee
  • Centre for Quantum Software and Information, School of Software, Faculty of Engineering and Information Technology, University of Technology Sydney, Australia
Manaswi Paraashar
  • Indian Statistical Institute, Kolkata, India
Ronald de Wolf
  • QuSoft, CWI and University of Amsterdam, The Netherlands

Funding

  • Arunachalam, Srinivasan: Work done when at QuSoft, CWI, Amsterdam, the Netherlands. Supported by ERC Consolidator Grant 615307 QPROGRESS and MIT-IBM Watson AI Lab under the project Machine Learning in Hilbert space.
  • Chakraborty, Sourav: Work done while on sabbatical at CWI, supported by ERC QPROGRESS.
  • Lee, Troy: Part of this work was done while at the School for Physical and Mathematical Sciences, Nanyang Technological University and the Centre for Quantum Technologies, Singapore, supported by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13.
  • de Wolf, Ronald: Supported by ERC QPROGRESS, and QuantERA project QuantAlgo 680-91-034, and NWO Gravitation project QSC.

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, 9 Dec 2015. URL: http://arxiv.org/abs/1512.02900.
  2. A. Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750-767, 2002. Earlier version in STOC'00. URL: http://arxiv.org/abs/quant-ph/0002066.
  3. S. Arunachalam, S. Chakraborty, T. Lee, M. Paraashar, and R. de Wolf. Two new results about quantum exact learning. URL: http://arxiv.org/abs/1810.00481.
  4. S. Arunachalam and R. de Wolf. Guest Column: A Survey of Quantum Learning Theory. SIGACT News, 48(2):41-67, 2017. URL: http://arxiv.org/abs/1701.06806.
  5. S. Arunachalam and R. de Wolf. Optimal Quantum Sample Complexity of Learning Algorithms. Journal of Machine Learning Research, 19, 2018. Earlier version in CCC'17. URL: http://arxiv.org/abs/1607.00932.
  6. A. At\ic\i and R. Servedio. Quantum Algorithms for Learning and Testing Juntas. Quantum Information Processing, 6(5):323-348, 2009. URL: http://arxiv.org/abs/0707.3479.
  7. 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. Google Scholar
  8. E. Bernstein and U. Vazirani. Quantum Complexity Theory. SIAM Journal on Computing, 26(5):1411-1473, 1997. Earlier version in STOC'93. Google Scholar
  9. J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd. Quantum machine learning. Nature, 549(7671), 2017. URL: http://arxiv.org/abs/1611.09347.
  10. 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. Google Scholar
  11. 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. Earlier version in COLT'95. Google Scholar
  12. 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. Google Scholar
  13. M. C. Chang. A polynomial bound in Freiman’s theorem. Duke Mathematics Journal, 113(3):399-419, 2002. Google Scholar
  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. Google Scholar
  15. T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, 1991. Google Scholar
  16. V. Dunjko and H. Briegel. Machine learning &artificial intelligence in the quantum domain, 8 Sep 2017. URL: http://arxiv.org/abs/1709.02779.
  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. Earlier version in ICALP'09. Google Scholar
  18. L. K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of 28th ACM STOC, pages 212-219, 1996. URL: http://arxiv.org/abs/quant-ph/9605043.
  19. A. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for solving linear systems of equations. Physical Review Letters, 103(15):150502, 2009. URL: http://arxiv.org/abs/0811.3171.
  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. Google Scholar
  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. Earlier version in CCC'15. URL: http://arxiv.org/abs/1504.01649.
  22. R. Impagliazzo, C. Moore, and A. Russell. An Entropic Proof of Chang’s Inequality. SIAM Journal of Discrete Mathematics, 28(1):173-176, 2014. URL: http://arxiv.org/abs/1205.0263.
  23. P. Indyk and M. Kapralov. Sample-Optimal Fourier Sampling in Any Constant Dimension. In Proceedings of 55th IEEE FOCS, pages 514-523, 2014. Google Scholar
  24. 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. Earlier version in STOC'03. Google Scholar
  25. M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  26. R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  27. M. Rudelson and R. Vershynin. On sparse reconstruction from Fourier and Gaussian measurements. Communications on Pure and Applied Mathematics, 61(8):1025-1045, 2008. Google Scholar
  28. S. Sanyal. Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity. In Proceedings of 42nd ICALP, pages 1035-1045, 2015. Google Scholar
  29. M. Schuld, I. Sinayskiy, and F. Petruccione. An introduction to quantum machine learning. Contemporary Physics, 56(2):172-185, 2015. URL: http://arxiv.org/abs/1409.3097.
  30. R. Servedio and S. Gortler. Equivalences and Separations Between Quantum and Classical Learnability. SIAM Journal on Computing, 33(5):1067-1092, 2004. Combines earlier papers from ICALP'01 and CCC'01. quant-ph/0007036. Google Scholar
  31. 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. URL: http://arxiv.org/abs/quant-ph/0409116.
  32. L. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–-1142, 1984. Google Scholar
  33. 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. Google Scholar
  34. P. Wittek. Quantum Machine Learning: What Quantum Computing Means to Data Mining. Elsevier, 2014. Google Scholar
  35. R. de Wolf. A Brief Introduction to Fourier Analysis on the Boolean Cube. Theory of Computing, 2008. ToC Library, Graduate Surveys 1. Google Scholar
  36. A. C-C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of 18th IEEE FOCS, pages 222-227, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact