PaperlayerView exact revision on arXiv

Source-linked AI summary

On the statistical complexity of quantum circuits

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

arXiv:2101.06154v1quant-phcs.LGstat.ML

TL;DR

The paper asks how quantum neural-network statistical complexity depends on circuit structure and resources, a question that has been less characterized than for classical networks. It uses Rademacher complexity and a magic measure based on the (p,q) group norm to derive bounds for circuits treated as whole channels or layer by layer. The bounds relate complexity to magic and circuit parameters, including depth and width in the layered setting.

  • Problem

    How statistical complexity depends on quantum-circuit structure and resources has remained largely unaddressed, despite its relevance to characterizing quantum neural networks.

    Source: §I · p. 1

  • Method

    The paper uses Rademacher complexity and introduces a magic resource measure for quantum channels based on the (p,q) group norm.

    Source: §I · p. 1

  • Results

    The bounds depend on magic and input/output qubit counts when a whole circuit is treated as one channel, and additionally on depth and width when layers are treated separately.

    Source: §I · p. 2

  • Takeaways & Limitations

    The results characterize how quantum-circuit statistical complexity depends on resources and structure parameters such as depth and width.

    Source: §III · p. 4

    Generalizing the Rademacher-complexity results to topological entropy is left for future work.

    Source: §III · p. 4

Abstract

from arXiv · show

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.

I. INTRODUCTION

Understanding how neural-network structure affects statistical complexity is a theoretical machine-learning problem; for quantum neural networks, how circuit structure and resources affect complexity has remained largely unaddressed. This paper studies that question using Rademacher complexity and bounds for two ways of treating circuit layers.

I. INTRODUCTION

  • Quantum neural-network complexity has been less characterized, including how it depends on circuit structure and resources.The paper identifies this dependence as a largely unaddressed question.Source: §I · p. 1
  • The paper uses Rademacher complexity and a magic resource measure based on the (p,q) group norm to study quantum circuits.The resource measure applies to quantum channels associated with the circuits.Source: §I · p. 1
  • Treating the full circuit as one channel yields bounds depending on magic and input/output qubit counts, while treating layers separately also brings in depth and width.The bounds characterize statistical complexity in both settings.Source: §I · pp. 1–2

II. MAIN RESULTS

The main results frame quantum circuits as real-valued hypothesis functions and use Rademacher complexity to characterize the richness of their function class. The measure is defined over independent input samples and is used as a statistical-complexity measure.

II. MAIN RESULTS

  • Each quantum circuit defines a real-valued function, and a set of circuits defines the corresponding function class.The class is denoted F∘C.Source: §II · p. 2
  • The learning setup uses independent input-label samples drawn from an unknown distribution and compares empirical with expected error.Their difference is called generalization error.Source: §II · p. 2
  • Rademacher complexity measures the richness of the circuit-defined hypothesis class on independent samples.The paper uses this quantity as a measure of statistical complexity.Source: §II · p. 2

1. Rademacher complexity of arbitrary quantum channel

For circuits treated as single quantum channels, the paper uses the channel representation's (p,q) group norm as a magic resource measure and bounds Rademacher complexity in terms of resources and input/output qubit counts.

1. Rademacher complexity of arbitrary quantum channel

  • The (p,q) group norm of a quantum gate's representation matrix can quantify the amount of magic in the gate.The paper applies this norm to quantum-channel representation matrices.Source: §1 · p. 2
  • The arbitrary-channel bound is for circuits from n0 input qubits to n1 output qubits with bounded (p,q) norm.The theorem bounds the Rademacher complexity on m samples.Source: §1 · p. 2
  • The resulting upper bound depends on the magic resource measure and the number of input and output qubits.The representation vectors of the observable and input states enter the bound through Kp(S,H).Source: §1 · p. 2

2. Rademacher complexity of unital quantum channels

For unital channels, the paper bounds Rademacher complexity using the (p,q) group norm of a modified representation matrix. The stated theorem assumes a traceless observable and circuits with bounded modified norm.

2. Rademacher complexity of unital quantum channels

  • For unital channels, the modified representation matrix is the bottom-right (4^n2 − 1) × (4^n2 − 1) block of the channel representation matrix.The corresponding modified representation vector omits the identity component.Source: §2 · p. 3
  • The (p,q) group norm of a unital channel's modified representation matrix is treated as a magic resource measure.The theorem considers unital circuits with bounded modified norm.Source: §2 · p. 3
  • For a traceless observable, the theorem bounds Rademacher complexity for unital circuits from n0 to n1 qubits with bounded modified norm.The bound is stated on m samples.Source: §2 · p. 3

B. Rademacher complexity of depth-l quantum circuits

For depth-l circuits with bounded layer resources, the paper bounds Rademacher complexity in relation to circuit depth, width, and magic. The choice of (p,q) can reduce the width dependence from exponential to polynomial.

B. Rademacher complexity of depth-l quantum circuits

  • The circuit resource measure represents the average amount of magic over its layers, with circuits specified by their layer channels and width vector.The circuit is composed as Φ_l∘Φ_{l−1}∘···∘Φ_1.Source: B. Rademacher complexity of depth-l… · p. 3
  • For depth-l circuits with bounded resource, the Rademacher complexity satisfies bounds that depend on depth, width, and the resource measure of magic.The theorem also specifies N_i=4^n_i−1 and uses K̂_p(S,H) defined in Eq. (10).Source: B. Rademacher complexity of depth-l… · pp. 3–4
  • Choosing p,q appropriately can reduce the bound’s exponential dependence on the width vector to polynomial dependence.The paper gives p*=q=Ω(∥n⃗∥_1/log∥n⃗∥_1) or p*=q=∞ as examples.Source: B. Rademacher complexity of depth-l… · p. 3
  • For unital channels, including unitary channels, the paper modifies the resource measure used in its bounds.The passage refers to the modified measure but does not specify its formula.Source: B. Rademacher complexity of depth-l… · p. 3
  • The paper also considers geometric-mean and path-norm resource measures, and reports similar complexity results for these alternatives.The authors note that multiple circuit realizations of the same channel can have different resource values, motivating a minimum-resource measure over realizations with fixed depth and width.Source: B. Rademacher complexity of depth-l… · p. 4

III. CONCLUSION

The paper introduces a (p,q) group-norm measure of magic and proves Rademacher-complexity bounds for quantum circuits in terms of depth, width, and magic. It identifies extensions to other complexity measures and arbitrary channel bases as directions for further work.

III. CONCLUSION

  • Quantum-circuit Rademacher complexity is bounded by depth, width, and amount of magic, with width dependence determined by the choice of (p,q).The bounds reveal how statistical complexity depends on circuit resources and structure.Source: §III · p. 4
  • The (p,q) group norm defines a resource measure of magic for quantum channels and layered quantum circuits.Source: §III · p. 4
  • The authors state that Rademacher-complexity results can be extended to VC dimension and metric entropy, given their close relationship.Source: §III · p. 4
  • Generalizing the results to topological entropy and to arbitrary channel bases, including phase space point operator bases, is left for future work.Topological entropy has been used to measure the complexity of classical neural networks [61].Source: §III · p. 4

1. (p,q) group norm of the representation matrix of a single quantum channel

The (p,q) group norm of a channel’s Pauli-basis representation is introduced as a resource measure of magic, with Clifford unitaries marking its unit-resource case in specified parameter regimes. Bounds on Rademacher complexity for channels with bounded norm connect statistical complexity to channel resources and input/output sizes.

1. (p,q) group norm of the representation matrix of a single quantum channel

  • Lemma 11 states that, for a unitary channel, the norm equals 1 if and only if the unitary is Clifford when 0 < p < 2.Source: §1 · p. 8
  • The (p,q) group norm of a channel’s Pauli-basis representation is proposed as a resource measure of magic.The representation matrix is defined using Pauli operators, and its group norm aggregates row-vector norms.Source: §1 · pp. 7–8
  • The norm is invariant under left or right multiplication by a Clifford unitary, and its tensor-product behavior is multiplicative.The proposition also lists convexity for p ≥ 1 and q ≥ 1.Source: §1 · p. 8

2. Bounds on the Rademacher complexity of quantum channels

  • The Rademacher complexity of channels with bounded (p,q) norm is bounded in terms of the norm and channel input/output sizes.The theorem gives bounds on m samples for channels from n0 to n1 qubits.Source: §2 · p. 10

1. (p,q) group norm of the modified representation matrix of unital channels

For unital channels, a modified representation matrix supports a (p,q) group-norm magic measure with faithfulness and Clifford-invariance properties in specified regimes. The resulting Rademacher-complexity bounds assume a traceless observable, while the appendix frames deep circuits as sequences of channel layers.

2. Rademacher complexity of single unital quantum circuit

  • For unital circuits with bounded modified (p,q) norm, the Rademacher complexity is bounded when the observable is traceless.The theorem concerns circuits from n0 to n1 qubits and m samples.Source: §2 · p. 14

Appendix C: Deep quantum circuits

  • A depth-l circuit is represented as an ordered sequence of channel layers, with layer i mapping n_{i-1} qubits to n_i qubits.The appendix introduces three magic-resource measures for circuits using the (p,q) group norm.Source: Appendix C · p. 15

1. Multiplication (p,q) depth-norm

The multiplication (p,q) depth-norm quantifies circuit resources by combining layer norms, and the paper uses bounded depth-norms to bound Rademacher complexity. Its Clifford properties and fixed-structure variational-circuit result clarify how the measure applies across layers and parameterized circuits.

1. Multiplication (p,q) depth-norm

  • For unitary layers, the multiplication depth-norm is a magic resource measure, equals 1 exactly for Clifford circuits in stated regimes, and is invariant under Clifford circuits.The measure is multiplicative under circuit composition and has the listed tensor-product property.Source: §1 · p. 15
  • For fixed-structure depth-l variational circuits, the circuit depth-norm is bounded by the product of layerwise bounds, yielding a Rademacher-complexity bound.Fixed structure means the position of each parameterized gate is fixed.Source: §1 · p. 17

2. Summation (p,q) depth-norm

This section defines depth-based (p,q) norms, characterizes their resource properties for quantum circuits, and gives Rademacher-complexity bounds for classes with bounded norms, including deep unital circuits under a traceless-observable assumption. It also includes the final proof step, invoking Lemmas 33 and 14 to complete the theorem’s proof.

2. Summation (p,q) depth-norm

  • For unitary layers, the summation depth-norm is a magic resource measure; it is faithful to Clifford circuits and has Clifford monotonicity direction determined by p.At r = 1, the norm is described as the average resource amount per layer; faithfulness is stated for 0 < p < 2 and p > 2, with opposite monotonicity directions under Clifford circuits.Source: §2 · p. 17
  • Theorem 28 and Proposition 29 give Rademacher-complexity bounds for depth-l circuit classes with bounded summation depth-norm, including the ν1,∞ specialization.Theorem 28 is stated for bounded ν(r)_{p,q}; Proposition 29 treats bounded ν1,∞.Source: §2 · p. 18

3. (p,q) path norm

  • The path-norm is a magic resource measure for unitary-layer circuits, is faithful exactly on Clifford circuits, is invariant under Clifford composition, and supports Rademacher-complexity bounds for bounded-norm classes.The stated faithfulness condition is 0 < p ≤ 1 and q > 0.Source: §3 · pp. 19–20

Appendix D: Deep unital quantum circuits

  • Appendix D considers depth-l unital circuits with traceless observable H and uses a modified representation matrix in which only I maps to I.Source: Appendix D · p. 21

1. Modified multiplication (p,q) depth-norm

  • For modified multiplication depth-norms, Clifford circuits characterize the faithful value and Clifford composition leaves the norm invariant; bounded-norm unital circuit classes receive complexity bounds, including fixed-structure variational circuits.For 0 < p < 2 the norm is at least 1, while for p > 2 it is at most 1; the fixed-structure variational result is stated as a Rademacher-complexity bound.Source: §1 · pp. 21–23

2. Modified summation (p,q) depth-norm

  • The modified summation depth-norm is faithful to Clifford circuits, has Clifford monotonicity direction determined by p, and yields Rademacher-complexity bounds for bounded-norm unital circuits.Source: §2 · p. 23

3. Modified (p,q) path-norm

  • The modified path-norm is faithful to Clifford circuits and invariant under Clifford composition, and bounded-norm unital circuit classes satisfy Rademacher-complexity bounds.Source: §3 · p. 24

2. Summation (p,q) depth-norm

  • The last inequality follows from Lemma 33, and applying Lemma 14 completes the theorem’s proof.Source: §3 · p. 25
Loading 2101.06154v1…