**Project Heads**

Klaus-Robert Müller (TU), Jens Eisert (FU)

**Project Members**

Simon Cichy (01/2023 -), Yihui Quek (10/2021 – 03/2022), Philipp Schmoll (04/2021 – 03/2022)

**Project Duration**

First funding period: 01.01.2021 − 31.12.2022; Second funding period: 01.01.2023 − 31.12.2025

**Located at**

FU Berlin

Machine learning and specifically deep learning techniques are revolutionizing the way we think of algorithms making predictions or decisions based on training data and how we look at mathematical modeling in the first place. Machine learning is undoubtedly enjoying an enormous impact in a wide range of applications of image classification, language recognition, computer vision, and model building in physics and chemistry. Just as the practical development of algorithmic design in machine learning and artificial intelligence goes hand in hand with an improved mathematical understanding, there is another important development coming into play: This is the perspective of near-term quantum devices, instances of existing quantum computers, offering additional speedups in tasks of learning, exploiting coherence and quantum features in appropriately set up quantum algorithms. This development is triggered by the insights that suitable quantum devices are just becoming available and advantages are expected to become feasible in the near future. Indeed, there is no denying that the question in what way quantum-assisted machine learning may provide advantages over the best known classical algorithms is much in the focus of present research. In this enormously rapid development, providing a substantial body of heuristic studies, however, it is sometimes overlooked that a rigorous understanding of this emerging field of research is still painfully lacking. It is such a rigorous and careful approach that is going to be pursued here, putting an emphasis on the key make or break question in quantum-assisted machine learning: Can one prove a quantum advantage in learning?

**This project sets out to develop a comprehensive mathematical understanding of quantum-assisted machine learning in a field largely driven by heuristic approaches. It asks in what provable way quantum devices can offer advantages in quantum-assisted PAC learning over classical computers. It also explains how persistent those advantages are when the unavoidable noise of quantum devices comes into play and presents much needed rigorous results of steps of variational algorithms.**

**Related Publications
**

*A single T-gate makes distribution learning hard *

M. Hinsche, M. Ioannou, A. Nietner, J. Haferkamp, Y. Quek, D. Hangleiter, J.-P. Seifert, J. Eisert, R. Sweke

Physical Review Letters 130, 240602 (2023), arXiv:2207.03140

*A super-polynomial quantum-classical separation for density modelling*

N. Pirnay, R. Sweke, J. Eisert, J.-P. Seifert,

Physical Review A 107, 042416 (2023), arXiv:2207.03140

*A note on lower bounds to variational problems with guarantees
*

J. Eisert

Physical Review A, in press (2023), arXiv:2301.06142

*Towards provably efficient quantum algorithms for large-scale machine learning models*

J. Liu, M. Liu, J.-P. Liu, Z. Ye, Y. Alexeev, J. Eisert, L. Jiang

arXiv:2303.03428 (2023)

*Understanding quantum machine learning also requires rethinking generalization*

E. Gil-Fuster, J. Eisert, C. Bravo-Prieto

arXiv:2306.13461 (2023)

*Learnability of the output distributions of local quantum circuits *

M. Hinsche, M. Ioannou, A. Nietner, J. Haferkamp, Y. Quek, D. Hangleiter, J.-P. Seifert, J. Eisert, R. Sweke

arXiv:2110.05517 (2021)

*Classical surrogates for quantum learning models*

F. Schreiber, J. Eisert, J. J. Meyer

Physical Review Letters, in press (2023), arXiv:2206.11740

*Exploiting symmetry in variational quantum machine learning*

J. J. Meyer, M. Mularski, E. Gil-Fuster, A. A. Mele, F. Arzani, A. Wilms, J. Eisert

PRX Quantum 4, 010328 (2023), arXiv:2205.06217

*A super-polynomial quantum advantage for combinatorial optimization problems *

N. Pirnay, V. Ulitzsch, F. Wilde, J. Eisert, J.-P. Seifert

arXiv:2212.08678 (2022)

*Non-recursive perturbative gadgets without subspace restrictions and applications to variational quantum algorithms*

S. Cichy, P. K. Faehrmann, S. Khatri, J. Eisert

arXiv:2210.03099 (2022)

*Encoding-dependent generalization bounds for parametrized quantum circuits *

M. C. Caro, E. Gil-Fuster, J. Jakob Meyer, J. Eisert, R. Sweke

Quantum 5, 582 (2021)

*On the quantum versus classical learnability of discrete distributions*

R. Sweke, J.-P. Seifert, D. Hangleiter, J. Eisert

Quantum 5, 417 (2021)