# Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2023.

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

- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [On the relation between trainability and dequantization of variational quantum learning models](https://mlsanity.com/paper/2406.07072/) (2024)
- [Variational quantum simulation: a case study for understanding warm starts](https://mlsanity.com/paper/2404.10044/) (2024)
- [Learning topological states from randomized measurements using variational tensor network tomography](https://mlsanity.com/paper/2406.00193/) (2024)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)
- [The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)](https://mlsanity.com/paper/2602.01054/) (2026)

## Abstract (arXiv)

Kearns' statistical query (SQ) oracle (STOC'93) lends a unifying perspective for most classical machine learning algorithms. This ceases to be true in quantum learning, where many settings do not admit, neither an SQ analog nor a quantum statistical query (QSQ) analog. In this work, we take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle (TOCT'14) and establish a unified perspective bridging the statistical and parametrized learning paradigms in a novel way. We explore the problem of learning from an evaluation oracle, which provides an estimate of function values, and introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries and characterizes the query complexity for learning linear function classes. The framework is directly applicable to the QSQ setting and virtually all algorithms based on loss function optimization. Our first application is to extend prior results on the learnability of output distributions of quantum circuits and Clifford unitaries from the SQ to the (multi-copy) QSQ setting, implying exponential separations between learning stabilizer states from (multi-copy) QSQs versus from quantum samples. Our second application is to analyze some popular quantum machine learning (QML) settings. We gain an intuitive picture of the hardness of many QML tasks which goes beyond existing methods such as barren plateaus and the statistical dimension, and contains crucial setting-dependent implications. Our framework not only unifies the perspective of cost concentration with that of the statistical dimension in a unified language but exposes their connectedness and similarity.