# Sample Complexity of Learning Parametric Quantum Circuits

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 22 references that are in the map.
- First posted on arXiv 19 Jul 2021.

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

- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [On the statistical complexity of quantum circuits](https://mlsanity.com/paper/2101.06154/) (2021)
- [Quantum statistical query learning](https://mlsanity.com/paper/2002.08240/) (2020)
- [Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem](https://mlsanity.com/paper/1810.10938/) (2018)
- [A Theoretical Framework for Learning from Quantum Data](https://mlsanity.com/paper/2107.06406/) (2021)

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

- [Generalization in quantum machine learning from few training data](https://mlsanity.com/paper/2111.05292/) (2021)
- [Exponential concentration in quantum kernel methods](https://mlsanity.com/paper/2208.11060/) (2022)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Quantum Recurrent Neural Networks for Sequential Learning](https://mlsanity.com/paper/2302.03244/) (2023)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [Problem-Dependent Power of Quantum Neural Networks on Multi-Class Classification](https://mlsanity.com/paper/2301.01597/) (2022)
- [Dynamical simulation via quantum machine learning with provable generalization](https://mlsanity.com/paper/2204.10269/) (2022)
- [Learning quantum states and unitaries of bounded gate complexity](https://mlsanity.com/paper/2310.19882/) (2023)
- [Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric](https://mlsanity.com/paper/2303.13462/) (2023)
- [Comparative Performance Analysis of Quantum Machine Learning Architectures for Credit Card Fraud Detection](https://mlsanity.com/paper/2412.19441/) (2024)
- [Transition Role of Entangled Data in Quantum Machine Learning](https://mlsanity.com/paper/2306.03481/) (2023)
- [Data re-uploading in Quantum Machine Learning for time series: application to traffic forecasting](https://mlsanity.com/paper/2501.12776/) (2025)
- [SAQNN: Spectral Adaptive Quantum Neural Network as a Universal Approximator](https://mlsanity.com/paper/2602.09718/) (2026)
- [Quantum automated learning with provable and explainable trainability](https://mlsanity.com/paper/2502.05264/) (2025)

## Abstract (arXiv)

Quantum computers hold unprecedented potentials for machine learning applications. Here, we prove that physical quantum circuits are PAC (probably approximately correct) learnable on a quantum computer via empirical risk minimization: to learn a parametric quantum circuit with at most nc gates and each gate acting on a constant number of qubits, the sample complexity is bounded by tildeO(nc+1). In particular, we explicitly construct a family of variational quantum circuits with O(nc+1) elementary gates arranged in a fixed pattern, which can represent all physical quantum circuits consisting of at most nc elementary gates. Our results provide a valuable guide for quantum machine learning in both theory and practice.