# On the statistical complexity of quantum circuits

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

## Key facts

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

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

- [A Survey on Deep Learning in Medical Image Analysis](https://mlsanity.com/paper/1702.05747/) (2017)
- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Recent Trends in Deep Learning Based Natural Language Processing](https://mlsanity.com/paper/1708.02709/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Efficient Learning for Deep Quantum Neural Networks](https://mlsanity.com/paper/1902.10445/) (2019)
- [Quantum machine learning: a classical perspective](https://mlsanity.com/paper/1707.08561/) (2017)
- [Continuous-variable quantum neural networks](https://mlsanity.com/paper/1806.06871/) (2018)
- [Trainability of Dissipative Perceptron-Based Quantum Neural Networks](https://mlsanity.com/paper/2005.12458/) (2020)
- [Machine learning & artificial intelligence in the quantum domain](https://mlsanity.com/paper/1709.02779/) (2017)
- [Dropout improves Recurrent Neural Networks for Handwriting Recognition](https://mlsanity.com/paper/1312.4569/) (2013)
- [Pseudo-dimension of quantum circuits](https://mlsanity.com/paper/2002.01490/) (2020)
- [Detecting Unexpected Obstacles for Self-Driving Cars: Fusing Deep Learning and Geometric Modeling](https://mlsanity.com/paper/1612.06573/) (2016)
- [Depth-Width Trade-offs for Neural Networks via Topological Entropy](https://mlsanity.com/paper/2010.07587/) (2020)
- [A mathematical theory of resources](https://mlsanity.com/paper/1409.5531/) (2014)

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

- [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)
- [Theory for Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.08566/) (2022)
- [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)
- [Recent advances for quantum classifiers](https://mlsanity.com/paper/2108.13421/) (2021)
- [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)
- [The dilemma of quantum neural networks](https://mlsanity.com/paper/2106.04975/) (2021)
- [Sample Complexity of Learning Parametric Quantum Circuits](https://mlsanity.com/paper/2107.09078/) (2021)
- [Dynamical simulation via quantum machine learning with provable generalization](https://mlsanity.com/paper/2204.10269/) (2022)
- [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)
- [Understanding Generalization in Quantum Machine Learning with Margins](https://mlsanity.com/paper/2411.06919/) (2024)
- [Accelerating variational quantum algorithms with multiple quantum processors](https://mlsanity.com/paper/2106.12819/) (2021)
- [Unleashing the Expressive Power of Pulse-Based Quantum Neural Networks](https://mlsanity.com/paper/2402.02880/) (2024)
- [Stability and Generalization of Quantum Neural Networks](https://mlsanity.com/paper/2501.12737/) (2025)
- [Quantum Reservoir Computing and Risk Bounds](https://mlsanity.com/paper/2501.08640/) (2025)
- [Data-Dependent Generalization Bounds for Parameterized Quantum Models Under Noise](https://mlsanity.com/paper/2412.11451/) (2024)
- [On the Generalization of Adversarially Trained Quantum Classifiers](https://mlsanity.com/paper/2504.17690/) (2025)
- [A Theory of Finite-Noise Optima and Generalization in Quantum Machine Learning](https://mlsanity.com/paper/2608.24229/) (2026)
- [Measurement-Budget Allocation in Quantum Learning with Finite-Shot Generalization Guarantees](https://mlsanity.com/paper/2608.24891/) (2026)

## Abstract (arXiv)

In theoretical machine learning, the statistical complexity is a notion that measures the richness of a hypothesis space. In this work, we apply a particular measure of statistical complexity, namely the Rademacher complexity, to the quantum circuit model in quantum computation and study how the statistical complexity depends on various quantum circuit parameters. In particular, we investigate the dependence of the statistical complexity on the resources, depth, width, and the number of input and output registers of a quantum circuit. To study how the statistical complexity scales with resources in the circuit, we introduce a resource measure of magic based on the (p,q) group norm, which quantifies the amount of magic in the quantum channels associated with the circuit. These dependencies are investigated in the following two settings: (i) where the entire quantum circuit is treated as a single quantum channel, and (ii) where each layer of the quantum circuit is treated as a separate quantum channel. The bounds we obtain can be used to constrain the capacity of quantum neural networks in terms of their depths and widths as well as the resources in the network.