# Learnability of the output distributions of local quantum circuits

arXiv: https://arxiv.org/abs/2110.05517 · HTML: https://mlsanity.com/paper/2110.05517/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 69 references that are in the map.
- First posted on arXiv 11 Oct 2021.

## Builds on (most cited first, 17 of 17)

- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Parameterized quantum circuits as machine learning models](https://mlsanity.com/paper/1906.07682/) (2019)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Quantum generative adversarial networks](https://mlsanity.com/paper/1804.08641/) (2018)
- [Learning in Implicit Generative Models](https://mlsanity.com/paper/1610.03483/) (2016)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Noisy intermediate-scale quantum (NISQ) algorithms](https://mlsanity.com/paper/2101.08448/) (2021)
- [The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine](https://mlsanity.com/paper/1904.02214/) (2019)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learning](https://mlsanity.com/paper/1907.03741/) (2019)
- [Quantum Wasserstein Generative Adversarial Networks](https://mlsanity.com/paper/1911.00111/) (2019)
- [A General Characterization of the Statistical Query Complexity](https://mlsanity.com/paper/1608.02198/) (2016)
- [Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm](https://mlsanity.com/paper/1910.02071/) (2019)
- [Stabiliser states are efficiently PAC-learnable](https://mlsanity.com/paper/1705.00345/) (2017)
- [On the Hardness of PAC-learning Stabilizer States with Noise](https://mlsanity.com/paper/2102.05174/) (2021)
- [Learnability and Complexity of Quantum Samples](https://mlsanity.com/paper/2010.11983/) (2020)

## Built on by (most cited first, 7 of 7)

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Generalization Metrics for Practical Quantum Advantage in Generative Models](https://mlsanity.com/paper/2201.08770/) (2022)
- [Power of Quantum Generative Learning](https://mlsanity.com/paper/2205.04730/) (2022)
- [Generative Invertible Quantum Neural Networks](https://mlsanity.com/paper/2302.12906/) (2023)
- [Quantum advantage for learning shallow neural networks with natural data distributions](https://mlsanity.com/paper/2503.20879/) (2025)
- [Equivariant Quantum Graph Circuits](https://mlsanity.com/paper/2112.05261/) (2021)
- [A supplemental investigation of non-linearity in quantum generative models with respect to simulatability and optimization](https://mlsanity.com/paper/2302.00788/) (2023)

## Abstract (arXiv)

There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries -- including those for training quantum circuit Born machines -- our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective.