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:2103.03139

Rademacher complexity of noisy quantum circuits

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

Published Mar 4, 2021• 17 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2103.03139

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•27 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

Statistical complexity of quantum circuits

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

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.

arXiv:2101.06154•Physical Review A•Jun 17, 2022•64 citations

Upper bounds on the noise threshold for fault-tolerant quantum computing

Julia Kempe, Oded Regev, Falk Unger +1 more

We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary $k$-qubit gates each of whose input wires is subject to depolarizing noise of strength $p$, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for $p>1-\Theta(1/\sqrt{k})$, the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of $k=2$, our bound is $p>35.7\%$. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes $29.3\%$. These bounds on $p$ are numerically better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, in which the effects of depolarizing noise are very easy to describe.

arXiv:0802.1464•Quantum Information and Computation•May 1, 2010•12 citations

Quantum Reservoir Computing and Risk Bounds

Naomi Mona Chmielewski, Nina H. Amini, Joseph Mikael

We propose a way to bound the generalisation errors of several classes of quantum reservoirs using the Rademacher complexity. We give specific, parameter-dependent bounds for two particular quantum reservoir classes. We analyse how the generalisation bounds scale with growing numbers of qubits. Applying our results to classes with polynomial readout functions, we find that the risk bounds converge in the number of training samples. The explicit dependence on the quantum reservoir and readout parameters in our bounds can be used to control the generalisation error to a certain extent. It should be noted that the bounds scale exponentially with the number of qubits n. The upper bounds on the Rademacher complexity can be applied to other reservoir classes that fulfill a few hypotheses on the quantum dynamics and the readout function.

arXiv:2501.08640•Jan 15, 2025•4 citations

Unitary designs, complexity, and information dynamics in random and noisy quantum systems

Ryotaro Suzuki

The intersection of physics and information theory has advanced rapidly in the past few decades. Information-theoretic concepts have been employed to formulate physical laws, while quantum information processing, such as quantum computation and communication, has been developed both theoretically and experimentally. Simultaneously, understanding the universal or specific behaviors of quantum many-body systems has remained a central challenge since shortly after the inception of quantum mechanics. This is studied in part by statistical mechanics, which models complex many-body systems using simple ensembles. In this thesis, we investigate information-theoretic problems in quantum many-body dynamics that lie at the intersection of these avenues. To begin with, we investigate the extent of randomness, captured by unitary designs, in random quantum circuits. Quantum circuits serve as discrete models for random many-body quantum dynamics. Specifically, we study how the internal structure of random gates influences the generation of randomness in quantum circuits. We demonstrate that the spectral gap of structured random circuits can be larger than that of unstructured ones, implying that the former can converge to designs faster than the latter. In this analysis, free-fermionic techniques play a crucial role in obtaining exact results on the spectrum of second-moment operators. We then investigate the effect of quantum measurements on the quantum complexity in random circuits. Here, the quantum complexity of a state is defined as the minimum number of local gates required for its exact preparation in quantum circuits. We prove that in monitored random quantum circuits, the complexity undergoes a measurement-induced phase transition by leveraging techniques from percolation theory. Above the critical measurement rate, the complexity saturates quickly. Below the threshold, it grows at least linearly for an exponentially long time. Finally, we discuss quantum communication scenarios in noisy quantum dynamics, where we simulate the identity channel by combining a given noisy quantum dynamics and our quantum operational strategies. Specifically, we consider multi-time noisy processes and optimize our strategies to simulate near-noiseless channels, both of which are mathematically formulated using quantum combs. We introduce formal concepts of simulation and capacity for quantum combs, and we derive lower-bounds on the minimum simulation error in terms of semidefinite programming (SDP). We impose certain conditions on our strategies, such as the positive partial transpose (PPT) preserving constraint. We then analyze these SDPs for simple models, such as the depolarizing process, to determine their fundamental communication limits.

•Jan 1, 2026•0 citations
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.
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.
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.
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary kkk-qubit gates each of whose input wires is subject to depolarizing noise of strength ppp, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for p>1−Θ(1/k)p>1-\Theta(1/\sqrt{k})p>1−Θ(1/k​), the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of k=2k=2k=2, our bound is p>35.7%p>35.7\%p>35.7%. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes 29.3%29.3\%29.3%. These bounds on ppp are numerically better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, in which the effects of depolarizing noise are very easy to describe.
We propose a way to bound the generalisation errors of several classes of quantum reservoirs using the Rademacher complexity. We give specific, parameter-dependent bounds for two particular quantum reservoir classes. We analyse how the generalisation bounds scale with growing numbers of qubits. Applying our results to classes with polynomial readout functions, we find that the risk bounds converge in the number of training samples. The explicit dependence on the quantum reservoir and readout parameters in our bounds can be used to control the generalisation error to a certain extent. It should be noted that the bounds scale exponentially with the number of qubits n. The upper bounds on the Rademacher complexity can be applied to other reservoir classes that fulfill a few hypotheses on the quantum dynamics and the readout function.
The intersection of physics and information theory has advanced rapidly in the past few decades. Information-theoretic concepts have been employed to formulate physical laws, while quantum information processing, such as quantum computation and communication, has been developed both theoretically and experimentally. Simultaneously, understanding the universal or specific behaviors of quantum many-body systems has remained a central challenge since shortly after the inception of quantum mechanics. This is studied in part by statistical mechanics, which models complex many-body systems using simple ensembles. In this thesis, we investigate information-theoretic problems in quantum many-body dynamics that lie at the intersection of these avenues. To begin with, we investigate the extent of randomness, captured by unitary designs, in random quantum circuits. Quantum circuits serve as discrete models for random many-body quantum dynamics. Specifically, we study how the internal structure of random gates influences the generation of randomness in quantum circuits. We demonstrate that the spectral gap of structured random circuits can be larger than that of unstructured ones, implying that the former can converge to designs faster than the latter. In this analysis, free-fermionic techniques play a crucial role in obtaining exact results on the spectrum of second-moment operators. We then investigate the effect of quantum measurements on the quantum complexity in random circuits. Here, the quantum complexity of a state is defined as the minimum number of local gates required for its exact preparation in quantum circuits. We prove that in monitored random quantum circuits, the complexity undergoes a measurement-induced phase transition by leveraging techniques from percolation theory. Above the critical measurement rate, the complexity saturates quickly. Below the threshold, it grows at least linearly for an exponentially long time. Finally, we discuss quantum communication scenarios in noisy quantum dynamics, where we simulate the identity channel by combining a given noisy quantum dynamics and our quantum operational strategies. Specifically, we consider multi-time noisy processes and optimize our strategies to simulate near-noiseless channels, both of which are mathematically formulated using quantum combs. We introduce formal concepts of simulation and capacity for quantum combs, and we derive lower-bounds on the minimum simulation error in terms of semidefinite programming (SDP). We impose certain conditions on our strategies, such as the positive partial transpose (PPT) preserving constraint. We then analyze these SDPs for simple models, such as the depolarizing process, to determine their fundamental communication limits.