# Quantum statistical query learning

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2020.

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

- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Enhancing Quantum Adversarial Robustness by Randomized Encodings](https://mlsanity.com/paper/2212.02531/) (2022)
- [Flexible learning of quantum states with generative query neural networks](https://mlsanity.com/paper/2202.06804/) (2022)
- [Sample Complexity of Learning Parametric Quantum Circuits](https://mlsanity.com/paper/2107.09078/) (2021)
- [Quantum Local Differential Privacy and Quantum Statistical Query Model](https://mlsanity.com/paper/2203.03591/) (2022)
- [Generative quantum advantage for classical and quantum problems](https://mlsanity.com/paper/2509.09033/) (2025)
- [Private learning implies quantum stability](https://mlsanity.com/paper/2102.07171/) (2021)
- [On the Hardness of PAC-learning Stabilizer States with Noise](https://mlsanity.com/paper/2102.05174/) (2021)
- [A unifying framework for differentially private quantum algorithms](https://mlsanity.com/paper/2307.04733/) (2023)
- [Differential Privacy Amplification in Quantum and Quantum-inspired Algorithms](https://mlsanity.com/paper/2203.03604/) (2022)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Learning unitaries with quantum statistical queries](https://mlsanity.com/paper/2310.02254/) (2023)
- [Learning Quantum Processes with Quantum Statistical Queries](https://mlsanity.com/paper/2310.02075/) (2023)
- [Quantum advantage for learning shallow neural networks with natural data distributions](https://mlsanity.com/paper/2503.20879/) (2025)
- [Clifford Circuits can be Properly PAC Learned if and only if textsfRP=textsfNP](https://mlsanity.com/paper/2204.06638/) (2022)
- [Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes](https://mlsanity.com/paper/2308.12304/) (2023)
- [When AI meets quantum information: A comprehensive review](https://mlsanity.com/paper/2607.00365/) (2026)
- [Advantage of Entangled Learning Rules in Quantum Measurement Class Learning](https://mlsanity.com/paper/2610.07328/) (2026)

## Abstract (arXiv)

We propose a learning model called the quantum statistical learning QSQ model, which extends the SQ learning model introduced by Kearns to the quantum setting. Our model can be also seen as a restriction of the quantum PAC learning model: here, the learner does not have direct access to quantum examples, but can only obtain estimates of measurement statistics on them. Theoretically, this model provides a simple yet expressive setting to explore the power of quantum examples in machine learning. From a practical perspective, since simpler operations are required, learning algorithms in the QSQ model are more feasible for implementation on near-term quantum devices. We prove a number of results about the QSQ learning model. We first show that parity functions, (log n)-juntas and polynomial-sized DNF formulas are efficiently learnable in the QSQ model, in contrast to the classical setting where these problems are provably hard. This implies that many of the advantages of quantum PAC learning can be realized even in the more restricted quantum SQ learning model. It is well-known that weak statistical query dimension, denoted by WSQDIM(C), characterizes the complexity of learning a concept class C in the classical SQ model. We show that log(WSQDIM(C)) is a lower bound on the complexity of QSQ learning, and furthermore it is tight for certain concept classes C. Additionally, we show that this quantity provides strong lower bounds for the small-bias quantum communication model under product distributions. Finally, we introduce the notion of private quantum PAC learning, in which a quantum PAC learner is required to be differentially private. We show that learnability in the QSQ model implies learnability in the quantum private PAC model. Additionally, we show that in the private PAC learning setting, the classical and quantum sample complexities are equal, up to constant factors.