EF1 – Extracting dynamical Laws from Complex Data



Quantum Advantages in Machine Learning

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)