Recorded 17 October 2023. Jens Eisert of Freie Universität Berlin presents "Do quantum computers have applications in machine learning and combinatorial optimization?" at IPAM's Mathematical Aspects of Quantum Learning Workshop. Abstract: There has been substantial excitement recently in identifying tasks for which quantum devices could possibly outperform classical devices. Recent experimental implementations on random circuit sampling have provided strong evidence that near-term quantum devices can outperform classical computers on paradigmatic tasks [1]. Also, quantum simulators seem to reach regimes out of scope for classical computers. These developments invite further studies to see what further applications of quantum devices could be found. Notions of quantum-assisted machine learning are seen as being candidates for this. We will have a careful look at such notions of quantum-assisted machine learning, driven by the hope that quantum algorithms could fare better than classical ones in instances of learning tasks. These advantages could refer to computational speedups, but also to better generalization and other figures of merit. We will discuss the comparative power of classical and quantum learners for generative modelling within the probably approximately correct framework, for which we prove a separation between the quantum and classical settings [2, 3]. In the light of new findings on the PAC learnability of the output distributions of near-term local quantum circuits, we will discuss how much structure is actually expected to be required to hope for quantum advantages in quantum-assisted machine learning [4]. We prove that the injection of a single T-gate into Clifford circuits renders the task of learning evaluators from samples infeasible in polynomial time. This is in stark contrast to the case of Clifford circuits for which we provide an efficient learning algorithm based on Gaussian elimination [5]. Finally, we will have a look at the sense in which quantum computers may assist in solving problems of combinatorial optimization. These problems are usually NP-hard in worst case complexity, so it is far from clear what type of quantum advantage one can even hope for, despite commonly made claims of expectations of such advantages in the literature. We discuss a proven super-exponential quantum advantage for combinatorial optimization, providing evidence that quantum computers may indeed be useful for such problems [6]. At the end of the talk, we will put these findings into perspective and discuss the potential for near-term quantum computing, including limitations of quantum error mitigation in NISQ devices [7], noise being helpful in variational quantum algorithms [8], classical surrogates simulating variational quantum algorithms in execution but not in training [9] and the exploitation of symmetry in NISQ devices [10]. [1] Rev. Mod. Phys. 95, 035001 (2023). [2] Quantum 5, 417 (2021). [3] Phys. Rev. A 107, 042416 (2023). [4] arXiv:2110.05517 (2021). [5] Phys. Rev. Lett. 130, 240602 (2023). [6] arXiv:2212.08678 (2022). [7] arXiv:2210.11505 (2022). [8] arXiv:2210.06723 (2022). [9] Phys. Rev. Lett. 131, 100803 (2023). [10] PRX Quantum 4, 010328 (2023). Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-mathematical-aspects-of-quantum-learning/?tab=schedule