Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2101.06154 · Physical Review A

Statistical complexity of quantum circuits

Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, Yaobo Zhang

Published Jun 17, 2022• 52 citations
arXivHTMLPDF

Abstract

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 magic resource measure based on the $(p,q)$ group norm, which quantifies the amount of magic resource 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.

DOI
10.1103/physreva.105.062431

Related papers

Effects of quantum resources and noise on the statistical complexity of quantum circuits

Kaifeng Bu, Dax Enshan Koh, Lu Li +2 more

Abstract We investigate how the addition of quantum resources changes the statistical complexity of quantum circuits by utilizing the framework of quantum resource theories. Measures of statistical complexity that we consider include the Rademacher complexity and the Gaussian complexity, which are well-known measures in computational learning theory that quantify the richness of classes of real-valued functions. We derive bounds for the statistical complexities of quantum circuits that have limited access to certain resources and apply our results to two special cases: (a) stabilizer circuits that are supplemented with a limited number of T gates and (b) instantaneous quantum polynomial-time Clifford circuits that are supplemented with a limited number of CCZ gates. We show that the increase in the statistical complexity of a quantum circuit when an additional quantum channel is added to it is upper bounded by the free robustness of the added channel. Moreover, as noise in quantum systems is a major obstacle to implementing many quantum algorithms on large quantum circuits, we also study the effects of noise on the Rademacher complexity of quantum circuits. Finally, we derive bounds for the generalization error associated with learning from training data arising from quantum circuits.

arXiv:2102.03282•Quantum Science and Technology•Jan 23, 2023•24 citations

Rademacher Complexity Bounds for Parameterized Quantum Circuits Generated by Pauli Strings

Hiroshi Ohno

In this study, we analyze the Rademacher complexity $ \mathcal{R}_{M} $ of a parameterized unitary whose generators are chosen from $ n $-qubit Pauli strings. Although generalization bounds for quantum machine learning models have been studied in several settings, explicit Rademacher-complexity bounds for parameterized unitaries generated by Pauli strings remain less transparent. We derive simple scaling bounds in terms of the number of parameters $ L $ and the number of training samples $ M $: $ \mathcal{O}(\frac{L^{\frac{3}{2}}}{\sqrt{M}}) $ for the full parameter domain and $ \mathcal{O}(\frac{L}{\sqrt{M}}) $ for a restricted parameter domain. Furthermore, we compare the obtained results with those for a classical linear model class and suggest a potential statistical-complexity advantage when the norms of both the input and the parameter in the classical model scale with the number of parameters. Numerical experiments provide qualitative evidence consistent with the predicted scaling.

quant-pharXiv:2605.29546•May 29, 2026•0 citations

Rademacher complexity of noisy quantum circuits

Kaifeng Bu, Dax Enshan Koh, Lu Li +2 more

Noise in quantum systems is a major obstacle to implementing many quantum algorithms on large quantum circuits. In this work, we study the effects of noise on the Rademacher complexity of quantum circuits, which is a measure of statistical complexity that quantifies the richness of classes of functions generated by these circuits. We consider noise models that are represented by convex combinations of unitary channels and provide both upper and lower bounds for the Rademacher complexities of quantum circuits characterized by these noise models. In particular, we find a lower bound for the Rademacher complexity of noisy quantum circuits that depends on the Rademacher complexity of the corresponding noiseless quantum circuit as well as the free robustness of the circuit. Our results show that the Rademacher complexity of quantum circuits decreases with the increase in noise.

arXiv:2103.03139•Mar 4, 2021•5 citations

Encoding-dependent generalization bounds for parametrized quantum circuits

Matthias C. Caro, Elies Gil-Fuster, Johannes Jakob Meyer +2 more

A large body of recent work has begun to explore the potential of parametrized quantum circuits (PQCs) as machine learning models, within the framework of hybrid quantum-classical optimization. In particular, theoretical guarantees on the out-of-sample performance of such models, in terms of generalization bounds, have emerged. However, none of these generalization bounds depend explicitly on how the classical input data is encoded into the PQC. We derive generalization bounds for PQC-based models that depend explicitly on the strategy used for data-encoding. These imply bounds on the performance of trained PQC-based models on unseen data. Moreover, our results facilitate the selection of optimal data-encoding strategies via structural risk minimization, a mathematically rigorous framework for model selection. We obtain our generalization bounds by bounding the complexity of PQC-based models as measured by the Rademacher complexity and the metric entropy, two complexity measures from statistical learning theory. To achieve this, we rely on a representation of PQC-based models via trigonometric functions. Our generalization bounds emphasize the importance of well-considered data-encoding strategies for PQC-based models.

•Jan 1, 2021•101 citations

Encoding-dependent generalization bounds for parametrized quantum circuits

Matthias C. Caro, Elies Gil-Fuster, Johannes Jakob Meyer +2 more

A large body of recent work has begun to explore the potential of parametrized quantum circuits (PQCs) as machine learning models, within the framework of hybrid quantum-classical optimization. In particular, theoretical guarantees on the out-of-sample performance of such models, in terms of generalization bounds, have emerged. However, none of these generalization bounds depend explicitly on how the classical input data is encoded into the PQC. We derive generalization bounds for PQC-based models that depend explicitly on the strategy used for data-encoding. These imply bounds on the performance of trained PQC-based models on unseen data. Moreover, our results facilitate the selection of optimal data-encoding strategies via structural risk minimization, a mathematically rigorous framework for model selection. We obtain our generalization bounds by bounding the complexity of PQC-based models as measured by the Rademacher complexity and the metric entropy, two complexity measures from statistical learning theory. To achieve this, we rely on a representation of PQC-based models via trigonometric functions. Our generalization bounds emphasize the importance of well-considered data-encoding strategies for PQC-based models.

arXiv:2106.03880•Quantum•Nov 17, 2021•4 citations

Encoding dependent generalization bounds for parametrized quantum circuits

Caro, M.C., Gil Fuster, E., Meyer, J.J. +2 more

A large body of recent work has begun to explore the potential of parametrized quantum circuits PQCs as machine learning models, within the framework of hybrid quantum classical optimization. In particular, theoretical guarantees on the out of sample performance of such models, in terms of generalization bounds, have emerged. However, none of these generalization bounds depend explicitly on how the classical input data is encoded into the PQC. We derive generalization bounds for PQC based models that depend explicitly on the strategy used for data encoding. These imply bounds on the performance of trained PQC based models on unseen data. Moreover, our results facilitate the selection of optimal data encoding strategies via structural risk minimization, a mathematically rigorous framework for model selection. We obtain our generalization bounds by bounding the complexity of PQC based models as measured by the Rademacher complexity and the metric entropy, two complexity measures from statistical learning theory. To achieve this, we rely on a representation of PQC based models via trigonometric functions. Our generalization bounds emphasize the importance of well considered data encoding strategies for PQC based models

•Jan 1, 2021•2 citations
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 magic resource measure based on the (p,q)(p,q)(p,q) group norm, which quantifies the amount of magic resource 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.
Abstract We investigate how the addition of quantum resources changes the statistical complexity of quantum circuits by utilizing the framework of quantum resource theories. Measures of statistical complexity that we consider include the Rademacher complexity and the Gaussian complexity, which are well-known measures in computational learning theory that quantify the richness of classes of real-valued functions. We derive bounds for the statistical complexities of quantum circuits that have limited access to certain resources and apply our results to two special cases: (a) stabilizer circuits that are supplemented with a limited number of T gates and (b) instantaneous quantum polynomial-time Clifford circuits that are supplemented with a limited number of CCZ gates. We show that the increase in the statistical complexity of a quantum circuit when an additional quantum channel is added to it is upper bounded by the free robustness of the added channel. Moreover, as noise in quantum systems is a major obstacle to implementing many quantum algorithms on large quantum circuits, we also study the effects of noise on the Rademacher complexity of quantum circuits. Finally, we derive bounds for the generalization error associated with learning from training data arising from quantum circuits.
In this study, we analyze the Rademacher complexity $ \mathcal{R}_{M} $ of a parameterized unitary whose generators are chosen from $ n $-qubit Pauli strings. Although generalization bounds for quantum machine learning models have been studied in several settings, explicit Rademacher-complexity bounds for parameterized unitaries generated by Pauli strings remain less transparent. We derive simple scaling bounds in terms of the number of parameters $ L $ and the number of training samples $ M $: $ \mathcal{O}(\frac{L^{\frac{3}{2}}}{\sqrt{M}}) $ for the full parameter domain and $ \mathcal{O}(\frac{L}{\sqrt{M}}) $ for a restricted parameter domain. Furthermore, we compare the obtained results with those for a classical linear model class and suggest a potential statistical-complexity advantage when the norms of both the input and the parameter in the classical model scale with the number of parameters. Numerical experiments provide qualitative evidence consistent with the predicted scaling.
Noise in quantum systems is a major obstacle to implementing many quantum algorithms on large quantum circuits. In this work, we study the effects of noise on the Rademacher complexity of quantum circuits, which is a measure of statistical complexity that quantifies the richness of classes of functions generated by these circuits. We consider noise models that are represented by convex combinations of unitary channels and provide both upper and lower bounds for the Rademacher complexities of quantum circuits characterized by these noise models. In particular, we find a lower bound for the Rademacher complexity of noisy quantum circuits that depends on the Rademacher complexity of the corresponding noiseless quantum circuit as well as the free robustness of the circuit. Our results show that the Rademacher complexity of quantum circuits decreases with the increase in noise.
A large body of recent work has begun to explore the potential of parametrized quantum circuits (PQCs) as machine learning models, within the framework of hybrid quantum-classical optimization. In particular, theoretical guarantees on the out-of-sample performance of such models, in terms of generalization bounds, have emerged. However, none of these generalization bounds depend explicitly on how the classical input data is encoded into the PQC. We derive generalization bounds for PQC-based models that depend explicitly on the strategy used for data-encoding. These imply bounds on the performance of trained PQC-based models on unseen data. Moreover, our results facilitate the selection of optimal data-encoding strategies via structural risk minimization, a mathematically rigorous framework for model selection. We obtain our generalization bounds by bounding the complexity of PQC-based models as measured by the Rademacher complexity and the metric entropy, two complexity measures from statistical learning theory. To achieve this, we rely on a representation of PQC-based models via trigonometric functions. Our generalization bounds emphasize the importance of well-considered data-encoding strategies for PQC-based models.
A large body of recent work has begun to explore the potential of parametrized quantum circuits (PQCs) as machine learning models, within the framework of hybrid quantum-classical optimization. In particular, theoretical guarantees on the out-of-sample performance of such models, in terms of generalization bounds, have emerged. However, none of these generalization bounds depend explicitly on how the classical input data is encoded into the PQC. We derive generalization bounds for PQC-based models that depend explicitly on the strategy used for data-encoding. These imply bounds on the performance of trained PQC-based models on unseen data. Moreover, our results facilitate the selection of optimal data-encoding strategies via structural risk minimization, a mathematically rigorous framework for model selection. We obtain our generalization bounds by bounding the complexity of PQC-based models as measured by the Rademacher complexity and the metric entropy, two complexity measures from statistical learning theory. To achieve this, we rely on a representation of PQC-based models via trigonometric functions. Our generalization bounds emphasize the importance of well-considered data-encoding strategies for PQC-based models.
A large body of recent work has begun to explore the potential of parametrized quantum circuits PQCs as machine learning models, within the framework of hybrid quantum classical optimization. In particular, theoretical guarantees on the out of sample performance of such models, in terms of generalization bounds, have emerged. However, none of these generalization bounds depend explicitly on how the classical input data is encoded into the PQC. We derive generalization bounds for PQC based models that depend explicitly on the strategy used for data encoding. These imply bounds on the performance of trained PQC based models on unseen data. Moreover, our results facilitate the selection of optimal data encoding strategies via structural risk minimization, a mathematically rigorous framework for model selection. We obtain our generalization bounds by bounding the complexity of PQC based models as measured by the Rademacher complexity and the metric entropy, two complexity measures from statistical learning theory. To achieve this, we rely on a representation of PQC based models via trigonometric functions. Our generalization bounds emphasize the importance of well considered data encoding strategies for PQC based models