# Pseudo-dimension of quantum circuits

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

## Key facts

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

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

- [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)
- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Understanding quantum machine learning also requires rethinking generalization](https://mlsanity.com/paper/2306.13461/) (2023)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [On the statistical complexity of quantum circuits](https://mlsanity.com/paper/2101.06154/) (2021)
- [On the relation between trainability and dequantization of variational quantum learning models](https://mlsanity.com/paper/2406.07072/) (2024)
- [Structural risk minimization for quantum linear classifiers](https://mlsanity.com/paper/2105.05566/) (2021)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Quantum Deep Hedging](https://mlsanity.com/paper/2303.16585/) (2023)
- [High Dimensional Quantum Machine Learning With Small Quantum Computers](https://mlsanity.com/paper/2203.13739/) (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)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric](https://mlsanity.com/paper/2303.13462/) (2023)
- [Non-asymptotic Approximation Error Bounds of Parameterized Quantum Circuits](https://mlsanity.com/paper/2310.07528/) (2023)
- [Effects of quantum resources on the statistical complexity of quantum circuits](https://mlsanity.com/paper/2102.03282/) (2021)
- [A kernel-based quantum random forest for improved classification](https://mlsanity.com/paper/2210.02355/) (2022)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [Unleashing the Expressive Power of Pulse-Based Quantum Neural Networks](https://mlsanity.com/paper/2402.02880/) (2024)
- [Entanglement-induced provable and robust quantum learning advantages](https://mlsanity.com/paper/2410.03094/) (2024)
- [A learning theory for quantum photonic processors and beyond](https://mlsanity.com/paper/2209.03075/) (2022)
- [Concept learning of parameterized quantum models from limited measurements](https://mlsanity.com/paper/2408.05116/) (2024)
- [Stability and Generalization of Quantum Neural Networks](https://mlsanity.com/paper/2501.12737/) (2025)
- [A PAC-Bayesian approach to generalization for quantum models](https://mlsanity.com/paper/2603.22964/) (2026)
- [A Hybrid Quantum-Classical Hamiltonian Learning Algorithm](https://mlsanity.com/paper/2103.01061/) (2021)
- [Image Compression and Classification Using Qubits and Quantum Deep Learning](https://mlsanity.com/paper/2110.05476/) (2021)
- [Clifford Circuits can be Properly PAC Learned if and only if textsfRP=textsfNP](https://mlsanity.com/paper/2204.06638/) (2022)
- [A Theory of Finite-Noise Optima and Generalization in Quantum Machine Learning](https://mlsanity.com/paper/2608.24229/) (2026)

## Abstract (arXiv)

We characterize the expressive power of quantum circuits with the pseudo-dimension, a measure of complexity for probabilistic concept classes. We prove pseudo-dimension bounds on the output probability distributions of quantum circuits; the upper bounds are polynomial in circuit depth and number of gates. Using these bounds, we exhibit a class of circuit output states out of which at least one has exponential state complexity, and moreover demonstrate that quantum circuits of known polynomial size and depth are PAC-learnable.