Journal
QUANTUM
Volume 5, Issue -, Pages -Publisher
VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF
DOI: 10.22331/q-2021-03-23-417
Keywords
-
Funding
- BMWi, under the PlanQK initiative
- Berlin Institute for the Foundations of Learning and Data
- Einstein Foundation Berlin
- BMBF Post-Quantum-Cryptography framework
- BMWi under the PlanQK initiative
- DFG [CRC 183, EI 519/14-1, EF1-11]
- Templeton Foundation
Ask authors/readers for more resources
This study compares the performance of classical and quantum learners for generative modeling within the Probably Approximately Correct (PAC) framework. The results show that quantum learners exhibit a provable advantage over classical learners in efficiently learning certain discrete probability distributions.
Here we study the comparative power of classical and quantum learners for generative modelling within the Probably Approximately Correct (PAC) framework. More specifically we consider the following task: Given samples from some unknown discrete probability distribution, output with high probability an efficient algorithm for generating new samples from a good approximation of the original distribution. Our primary result is the explicit construction of a class of discrete probability distributions which, under the decisional Diffie-Hellman assumption, is provably not efficiently PAC learnable by a classical generative modelling algorithm, but for which we construct an efficient quantum learner. This class of distributions therefore provides a concrete example of a generative modelling problem for which quantum learners exhibit a provable advantage over classical learning algorithms. In addition, we discuss techniques for proving classical generative modelling hardness results, as well as the relationship between the PAC learnability of Boolean functions and the PAC learnability of discrete probability distributions.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available