A survey of quantum learning theory

Preprint, Article English OPEN
Arunachalam, Srinivasan; de Wolf, Ronald;
(2017)
  • Subject: Computer Science - Computational Complexity | Computer Science - Learning | Quantum Physics
    acm: TheoryofComputation_GENERAL | ComputerSystemsOrganization_MISCELLANEOUS
    arxiv: Computer Science::Machine Learning

This paper surveys quantum learning theory: the theoretical aspects of machine learning using quantum computers. We describe the main results known for three models of learning: exact learning from membership queries, and Probably Approximately Correct (PAC) and agnosti... View more
  • References (45)
    45 references, page 1 of 5

    [AAD+15] 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. arXiv:1512.02900. 2

    E. A¨ımeur, G. Brassard, and S. Gambs. Quantum speed-up for unsupervised learning. Machine Learning, 90(2):261-287, 2013. 2

    S. Aaronson and L. Chen. Complexity-theoretic foundations of quantum supremacy experiments. arxiv:1612.05903, 2016. 19

    [AIK+04] A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, R. H. Putra, and S. Yamashita. Quantum identification of Boolean oracles. In Proceedings of 30th Annual Symposium on Theoretical Aspects of Computer Science (STACS'04), pages 105-116, 2004. arXiv:quantph/0403056. 10

    [AIK+07] A. Ambainis, K. Iwama, A. Kawachi, R. Raymond, and S. Yamashita. Improved algorithms for quantum identification of Boolean oracles. Theoretical Computer Science, 378(1):41-53, 2007. 10

    [AIN+09] A. Ambainis, K. Iwama, M. Nakanishi, H. Nishimura, R. Raymond, S. Tani, and S. Yamashita. Average/worst-case gap of quantum query complexities by on-set size. 2009. Preprint at arXiv:0908.2468v1. 10

    [BCG+96] N. H. Bshouty, R. Cleve, R. Gavalda`, S. Kannan, and C. Tamon. Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences, 52(3):421- 433, 1996. Earlier version in COLT'94. 8

    [BEHW89] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929-965, 1989. 11

    bound. Computational Complexity, 24(2):255-293, 2015. Earlier version in Complexity'14. arXiv:1311.6777. 18

    of Statistical Physics, 29(3):515-546, 1982. 1

  • Related Organizations (1)
  • Metrics
Share - Bookmark