Recorded 19 October 2023. Vedran Dunjko of Leiden University presents "Exponential separations between classical and quantum learners" at IPAM's Mathematical Aspects of Quantum Learning Workshop. Abstract: One of the key challenges of the quantum machine learning field is identifying learning problems where quantum learning algorithms can achieve a provable exponential advantage over classical learning algorithms. Proofs of separation for learning mostly work by reductions to plausible complexity theoretic assumptions of various types. Previously known examples of advantages are all contrived, and all rely on cryptographic methods to make learning hard for a classical learner. However, the broadly shared intuition is that learning separations should in particular be most apparent when the learning task involves data from genuinely quantum sources (but still quantum, i.e., measured out), which are very different from cryptographic problems. In the first part of this talk I will discuss this apparent discrepancy and present a series of new results showing various types of advantages that can be obtained, which will include advantages stemming from a large class complex quantum physical systems, rather than cryptography. In the second part of the talk, I will discuss how certain complexity theoretic arguments can be used to prove learning separations in a much more restricted setting where quantum capabilities are only assumed in the training stage of the quantum machine learning system, whereas the deployment is fully classical. The talk will be based on the following references: -Exponential separations between classical and quantum learners, C. Gyurik, V. Dunjko, arXiv:2306.16028 -Shadows of quantum machine learning, S. Jerbi, C. Gyurik, S. C. Marshall, R. Molteni, V. Dunjko, arXiv:2306.00061 Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-mathematical-aspects-of-quantum-learning/?tab=schedule