A super-polynomial quantum-classical separation for density modelling

Abstract

Density modelling is the task of learning an unknown probability density function from samples, and is one of the central problems of unsupervised machine learning. In this work, we show that there exists a density modelling problem for which fault-tolerant quantum computers can offer a super-polynomial advantage over classical learning algorithms, given standard cryptographic assumptions. Along the way, we provide a variety of additional results and insights, of potential interest for proving future distribution learning separations between quantum and classical learning algorithms. Specifically, we (a) provide an overview of the relationships between hardness results in supervised learning and distribution learning, and (b) show that any weak pseudo-random function can be used to construct a classically hard density modelling problem. The latter result opens up the possibility of proving quantum-classical separations for density modelling based on weaker assumptions than those necessary for pseudo-random functions.

15 pages, one figure

Cited by in corpus (13)

• Towards provably efficient quantum algorithms for large-scale machine-learning models
• Understanding quantum machine learning also requires rethinking generalization
• Let Quantum Neural Networks Choose Their Own Frequencies
• Neural quantum kernels: training quantum kernels with quantum neural networks
• Efficient MPS representations and quantum circuits from the Fourier modes of classical image data
• Satellite image classification with neural quantum kernels
• Guided Quantum Compression for High Dimensional Data Classification
• Single-shot quantum machine learning
• VQE-generated quantum circuit dataset for machine learning
• Typical Machine Learning Datasets as Low-Depth Quantum Circuits
• Double descent in quantum kernel methods
• Learning Reduced Representations for Quantum Classifiers
• Learning complexity gradually in quantum machine learning models