EF1 – Extracting dynamical Laws from Complex Data



Quantum and Classical PAC Learning

Project Heads

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

Project Members

Philipp Schmoll (FU)

Project Duration

01.01.2021 − 31.12.2022

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 then unavoidable noise of quantum devices comes into play and presents much needed rigorous results of steps of variational algorithms.

Related Publications

On the quantum versus classical learnability of discrete distributions
R. Sweke, J.-P. Seifert, D. Hangleiter, J. Eisert
Quantum 5, 417 (2021)