Source-linked AI summary
Rademacher complexity of noisy quantum circuits
Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, Yaobo Zhang
TL;DR
Noise limits the use of large quantum circuits, while prior Rademacher-complexity analyses considered noiseless circuits. This paper bounds the complexity of circuits with mixed-unitary noise and finds that it decreases as noise increases.
Problem
Earlier Rademacher-complexity analyses were restricted to noiseless circuits, despite noise being a challenge for implementing quantum algorithms on near-term hardware.
Source: §I · p. 1Method
The paper models noise with mixed-unitary channels and derives upper and lower bounds for noisy-circuit Rademacher complexity.
Source: §I · pp. 1–2Results
The Rademacher complexity is nonincreasing under noise, and its lower bound depends on the corresponding noiseless circuit’s complexity and free robustness.
Source: §I · p. 2, A. Upper bound · p. 3Takeaways & Limitations
For the mixed-unitary noise models considered, quantum-circuit Rademacher complexity decreases as the amount of noise increases.
Source: §I · p. 2
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper asks how noise changes quantum circuits’ Rademacher complexity, a measure used to bound learning generalization. It studies mixed-unitary noise and bounds the complexity of noisy circuits.
I. INTRODUCTION
- Noisy, error-prone quantum computers and open questions about quantum machine-learning models’ advantages are two fundamental challenges motivating this work.The introduction notes that current hardware is too noisy for many algorithms at large input sizes with sufficiently small error.Source: §I · p. 1
- Prior work studied quantum-model complexity using pseudo-dimension and fat-shattering dimension, while this work’s earlier analyses of Rademacher complexity covered noiseless circuits.The earlier Rademacher-complexity studies examined circuit structure and quantum resources.Source: §I · p. 1
- Those noiseless-only analyses leave open how quantum circuits’ Rademacher complexity changes under noise, a relevant question for noise-susceptible NISQ circuits.The introduction contrasts this gap with studies of how noise affects classical simulability.Source: §I · p. 1
- The paper studies noise models represented by mixed-unitary channels, including depolarizing and dephasing channels, and derives upper and lower bounds for noisy-circuit Rademacher complexity.Mixed-unitary channels are convex combinations of unitary channels.Source: §I · pp. 1–2
- The lower bound depends on both the corresponding noiseless circuit’s Rademacher complexity and the circuit’s free robustness.Source: §I · p. 2
- The Rademacher complexity of a quantum circuit decreases as the amount of noise increases.Source: §I · p. 2
II. METHODS
The methods model circuit outputs as real-valued functions evaluated on encoded samples, then incorporate local mixed-unitary noise. They define when such noise is compatible with a circuit class.
II. METHODS
- A circuit acts on an encoded sample and a Hermitian observable is measured; the resulting expected outcome defines f_C, and circuits in C induce the class F ◦ C.The Rademacher complexity is defined on m independent samples using Rademacher random variables ε_i.Source: §II · p. 2
- Local noise channels may act on one or multiple registers and are modeled as convex combinations of unitary channels.For the results to be meaningful, the authors further assume the channel’s non-identity mixture weights sum to at most 1/2.Source: §II · p. 2
- For qubit systems, the channels described by this mixed-unitary model are precisely the unital channels, including depolarizing and dephasing channels.A unital channel fixes the identity operator.Source: §II · p. 2
- A mixed-unitary channel D is C-compatible when its unitary decomposition can replace the local noise so that every resulting circuit remains in C.The figure illustrates this definition; the depolarizing channel is given as C-compatible for Clifford circuits because its Pauli components are Clifford gates.Source: §II · p. 2, Figure 1 · p. 2
A. Upper bound
The section establishes that noise does not increase circuit-class Rademacher complexity in general, then develops sample-wise upper bounds for fixed-structure circuits under bounded resources and local depolarizing noise.
A. Upper bound
- For C-compatible noise channels, Proposition 2 provides a Rademacher-complexity relationship for all integers k ≥ 0.Source: A. Upper bound · p. 3
- Circuit Rademacher complexity is nonincreasing under noise in general.The stated proposition attributes the equality in its argument to invariance under convex combinations.Source: A. Upper bound · p. 3
- The fixed-structure analysis bounds resources using the (1,∞) group norm of channel representations in the Pauli basis.Source: A. Upper bound · p. 3
- For fixed-structure, bounded-resource circuits with local depolarizing noise after each gate, Propositions 3 and Corollary 4 provide sample-wise upper bounds.Source: A. Upper bound · pp. 3–4
B. Lower bound
This section develops lower bounds for noisy-circuit Rademacher complexity, including bounds related to noiseless circuits and free robustness. It compares the bounds for depolarizing and dephasing noise.
B. Lower bound
- The section states relationships for m independent samples under C-compatibility and recovery-map conditions.Source: B. Lower bound · p. 4
- Introducing free robustness yields a better lower bound that depends on the noiseless circuits and noise parameters.Source: B. Lower bound · pp. 4–5
- When a recovery map exists, its representation-vector l1 norm can lower-bound robustness, and finite norm permits the stated decomposition.Source: B. Lower bound · p. 4
- A recovery map lets noisy circuits be expressed as linear combinations of circuits in the corresponding noiseless class.Source: B. Lower bound · p. 4
- For depolarizing noise, Proposition 8 gives a better bound than Proposition 5; for dephasing noise, the two bounds are the same.Source: B. Lower bound · p. 4
- For fixed structure and bounded resource, noisy-circuit Rademacher complexity has a lower bound tied to the corresponding noiseless circuits.The stated bound applies to m independent samples.Source: B. Lower bound · pp. 4–5
IV. CONCLUDING REMARKS
The conclusion states that the study investigates how noise affects quantum-circuit Rademacher complexity.
IV. CONCLUDING REMARKS
- The study investigates how noise affects the Rademacher complexity of quantum circuits.Source: §IV · p. 5
Appendix A: Proof of Proposition 3
The proof aims to establish a bound over channels subject to a matrix-norm constraint.
Appendix A: Proof of Proposition 3
- The proof proceeds by establishing a bound over channels satisfying a matrix-norm constraint.Source: Appendix A · p. 6
Appendix B: Proof of Proposition 5
The proof rewrites the noisy channel using its unitary-channel mixture and then applies the triangle inequality.
Appendix B: Proof of Proposition 5
- The proof expresses the noisy channel as a mixture of the identity action and unitary-channel actions, then applies the triangle inequality.Source: Appendix B · p. 7
Appendix C: Proof of Theorem 6
The proof uses invariance of Rademacher complexity under convex combinations to justify an equality.
Appendix C: Proof of Theorem 6
- The proof’s equality follows from Rademacher complexity being invariant under convex combinations.The proof also invokes the definition of γ_k,k+1 for a noisy quantum circuit.Source: Appendix C · p. 7