On the Quantum versus Classical Learnability of Discrete Distributions

Abstract

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.

arXiv commentMain theorem has been strengthened to provide a separation with respect to the TV-distance and an additional section on verification of learners has been included. Accepted in Quantum

References in corpus (23)

• Auto-Encoding Variational Bayes
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• Normalizing Flows: An Introduction and Review of Current Methods
• Quantum generative adversarial learning
• Quantum generative adversarial networks
• A generative modeling approach for benchmarking and training shallow quantum circuits
• Average-case complexity versus approximate simulation of commuting quantum computations
• Differentiable Learning of Quantum Circuit Born Machine
• Demonstration of quantum advantage in machine learning
• Quantum generative adversarial learning in a superconducting quantum circuit
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Quantum learning robust to noise
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• Quantum Wasserstein Generative Adversarial Networks
• Learning with Errors is easy with quantum samples
• Sample complexity of device-independently certified "quantum supremacy"
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Statistical Limits of Supervised Quantum Learning
• A short note on learning discrete distributions

Cited by in corpus (52)

• A rigorous and robust quantum speed-up in supervised machine learning
• Information-theoretic bounds on quantum advantage in machine learning
• Is quantum advantage the right goal for quantum machine learning?
• Quantum machine learning beyond kernel methods
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Quantum computing models for artificial neural networks
• Towards provably efficient quantum algorithms for large-scale machine-learning models
• Enhancing Generative Models via Quantum Correlations
• Understanding quantum machine learning also requires rethinking generalization
• NISQ Computers: A Path to Quantum Supremacy
• Shadows of quantum machine learning
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage
• Anomaly detection with variational quantum generative adversarial networks
• Quantum Machine Learning for Digital Health? A Systematic Review
• Classical surrogates for quantum learning models
• Variational inference with a quantum computer
• Trainability barriers and opportunities in quantum generative modeling
• A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models
• Completely Quantum Neural Networks
• Classical versus Quantum: comparing Tensor Network-based Quantum Circuits on LHC data
• Interpretable Quantum Advantage in Neural Sequence Learning
• Tree tensor network classifiers for machine learning: from quantum-inspired to quantum-assisted
• A single $T$-gate makes distribution learning hard
• A performance characterization of quantum generative models
• Foundations for Near-Term Quantum Natural Language Processing
• Data re-uploading with a single qudit
• On the expressivity of embedding quantum kernels
• A super-polynomial quantum-classical separation for density modelling
• Noise-Resistant Quantum State Compression Readout
• Neural quantum kernels: training quantum kernels with quantum neural networks
• Hyperparameter Importance of Quantum Neural Networks Across Small Datasets
• Efficient MPS representations and quantum circuits from the Fourier modes of classical image data
• Demonstration of a bosonic quantum classifier with data re-uploading
• A Continuous Variable Born Machine
• Satellite image classification with neural quantum kernels
• Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation
• Quantum Natural Policy Gradients: Towards Sample-Efficient Reinforcement Learning
• Generative Invertible Quantum Neural Networks
• Quantum delegated and federated learning via quantum homomorphic encryption
• Encoding-dependent generalization bounds for parametrized quantum circuits
• Single-shot quantum machine learning
• A learning theory for quantum photonic processors and beyond
• Quantum generative modeling for financial time series with temporal correlations
• Generalization Bounds in Hybrid Quantum-Classical Machine Learning Models
• Typical Machine Learning Datasets as Low-Depth Quantum Circuits
• ORQVIZ: Visualizing High-Dimensional Landscapes in Variational Quantum Algorithms
• Double descent in quantum kernel methods
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Quantum fidelity kernel with a trapped-ion simulation platform
• TabularQGAN: A quantum generative model for tabular data synthesis
• Variational Quantum Generative Modeling by Sampling Expectation Values of Tunable Observables
• Learning complexity gradually in quantum machine learning models