- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review A

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Editors' Suggestion
  • Open Access
  • Access by Xinjiang University

Superpolynomial quantum-classical separation for density modeling

Niklas Pirnay1, Ryan Sweke2,*, Jens Eisert2,3, and Jean-Pierre Seifert1,4

  • 1Electrical Engineering and Computer Science, Technische Universität Berlin, 10587 Berlin, Germany
  • 2Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
  • 3Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany
  • 4Fraunhofer SIT, D-64295 Darmstadt, Germany

  • *Currently at IBM Quantum, Almaden Research Center, San Jose, CA 95120, USA.
PDF

Phys. Rev. A 107, 042416 – Published 13 April, 2023

DOI: https://doi.org/10.1103/PhysRevA.107.042416

Abstract

Density modeling is the task of learning an unknown probability density function from samples, and is one of the central problems of unsupervised machine learning. In this work, we show that there exists a density modeling problem for which fault-tolerant quantum computers can offer a superpolynomial advantage over classical learning algorithms, given standard cryptographic assumptions. Along the way, we provide a variety of additional results and insights of potential interest for proving future distribution learning separations between quantum and classical learning algorithms. Specifically, we (a) provide an overview of the relationships between hardness results in supervised learning and distribution learning, and (b) show that any weak pseudorandom function can be used to construct a classically hard density modeling problem. The latter result opens up the possibility of proving quantum-classical separations for density modeling based on weaker assumptions than those necessary for pseudorandom functions.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (25)

  1. M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. E. Schapire, and L. Sellie, in Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC '94 (Association for Computing Machinery, New York, 1994), pp. 273–282
  2. J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Nature (London) 549, 195 (2017).
  3. S. Arunachalam and R. de Wolf, A survey of quantum learning theory, arXiv:1701.06806.
  4. S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum algorithms for supervised and unsupervised machine learning, arXiv:1307.0411.
  5. G. Carleo, I. Cirac, K. Cranmer, L. Daudet, M. Schuld, N. Tishby, L. Vogt-Maranto, and L. Zdeborová, Rev. Mod. Phys. 91, 045002 (2019).
  6. M. Benedetti, E. Lloyd, S. Sack, and M. Fiorentini, Quantum Sci. Technol. 4, 043001 (2019).
  7. M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, et al., Nat. Rev. Phys. 3, 625 (2021).
  8. R. A. Servedio and S. J. Gortler, SIAM J. Comput. 33, 1067 (2004).
  9. V. Dunjko, Y.-K. Liu, X. Wu, and J. M. Taylor, arXiv:1710.11160.
  10. Y. Liu, S. Arunachalam, and K. Temme, Nat. Phys. 17, 1013 (2021).
  11. R. Sweke, J.-P. Seifert, D. Hangleiter, and J. Eisert, Quantum 5, 417 (2021).
  12. C. Gyurik and V. Dunjko, On establishing learning separations between classical and quantum machine learning with classical data, arXiv:2208.06339.
  13. L. G. Valiant, Commun. ACM 27, 1134 (1984).
  14. M. J. Kearns and U. Vazirani, An Introduction to Computational Learning Theory (MIT Press, Cambridge, 1994).
  15. M. Kearns, J. ACM 45, 983 (1998).
  16. D. Xiao, in COLT 2010–The 23rd Conference on Learning Theory, Haifa, Israel, June 27–29, 2010, edited by A. T. Kalai and M. Mohri (Omnipress, Madison, 2010), pp. 516–528.
  17. O. Goldreich, S. Goldwasser, and S. Micali, J. ACM 33, 792 (1986).
  18. G. Bresler, F. Koehler, and A. Moitra, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (ACM, 2019), pp. 828–839.
  19. S. A. Terwijn, in Grammatical Inference: Algorithms and Applications: 6th International Colloquium, ICGI 2002, Amsterdam, The Netherlands, September 23–25, 2002 (Springer, New York, 2002), pp. 261–268.
  20. G. Bresler, D. Gamarnik, and D. Shah, Adv. Neural Inf. Proc. Sys. 27, 1062 (2014).
  21. I. Diakonikolas, D. M. Kane, and A. Stewart, in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, New York, 2017), pp. 73–84.
  22. A. Bogdanov and A. Rosen, Tutorials on the Foundations of Cryptography (Springer, Berlin, 2017), pp. 79–158.
  23. A. W. Cross, G. Smith, and J. A. Smolin, Phys. Rev. A 92, 012327 (2015).
  24. B. Coyle, D. Mills, V. Danos, and E. Kashefi, npj Quantum Inf. 6, 60 (2020).
  25. J.-G. Liu and L. Wang, Phys. Rev. A 98, 062324 (2018).

Outline

Information

Phys. Rev. A 107, 042416– Published 13 April, 2023
  • Received 7 December 2022
  • Accepted 20 March 2023
Crossmark - Check for updates button
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal "citation, and DOI.

©2023 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation