PaperlayerView exact revision on arXiv

Source-linked AI summary

Encoding-dependent generalization bounds for parametrized quantum circuits

Matthias C. Caro, Elies Gil-Fuster, Johannes Jakob Meyer, Jens Eisert, Ryan Sweke

arXiv:2106.03880v3quant-phcs.ITmath.ITstat.ML

TL;DR

Existing PQC generalization bounds did not explicitly capture how data encoding affects generalization. The paper derives encoding-dependent complexity and generalization bounds, then uses them to compare encoding strategies and support structural risk minimization.

  • Problem

    Prior PQC generalization bounds did not depend explicitly on architectural hyperparameters of the data-encoding strategy.

    Source: §1 · p. 2

  • Method

    The paper bounds PQC model-class complexity using Rademacher complexity and metric entropy, then derives uniform generalization bounds with explicit data-encoding dependence.

    Source: §8 · p. 31

  • Results

    The derived uniform bounds apply to PQC models with data re-uploading and permit comparisons of data-encoding strategies from a generalization perspective.

    Source: §8 · p. 31

  • Takeaways & Limitations

    The bounds can support structural risk minimization over data-encoding hyperparameters, but do not guide selection of the remaining architectural hyperparameters.

    Source: §7 · p. 29

    The relation between the trigonometric-series coefficients and the circuit and observable is not fully understood; the analysis uses only the frequency set.

    Source: §3 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

The introduction asks whether PQC models can be given out-of-sample guarantees that explicitly reflect their data-encoding strategy. It develops this question through encoding-dependent complexity bounds and their use in model selection.

1 Introduction

  • The paper studies whether trained PQC models can have guaranteed expected performance on new data drawn from the training distribution.It frames the choice of model around expected out-of-sample performance rather than training performance alone.Source: §1 · p. 2
  • Earlier bounds considered encoding-first circuits, whereas this work also considers data re-uploading, with trainable and encoding blocks interleaved.The introduction notes that data re-uploading has been shown to affect expressive power.Source: §1 · p. 2
  • Prior PQC generalization bounds did not explicitly show how changing the data-encoding strategy affects generalization performance.The paper makes this dependence explicit through architectural hyperparameters associated with data encoding.Source: §1 · p. 2
  • The analysis uses generalized trigonometric polynomials, whose accessible frequencies are determined by the data-encoding strategy, to derive complexity-based generalization bounds.It then relates frequency counts to encoding strategies and proposes combining bounds with empirical risk through structural risk minimization.Source: §1 · p. 2

1.1 Structure of this work

  • The paper proceeds from statistical learning theory and PQC representations to prior work, bounds, encoding comparisons, and discussion.Figure 1 visualizes the manuscript's logical flow.Source: §1.1 · p. 3, Figure 1 · p. 3

2 Motivation: Generalization bounds, sample complexities and model selection

This section motivates uniform generalization bounds as tools for estimating out-of-sample risk and selecting model complexity. It connects those goals to encoding-dependent bounds for PQC hypothesis classes.

2 Motivation: Generalization bounds, sample complexities and model selection

  • Generalization bounds combine empirical risk with an upper bound on the generalization gap to bound a hypothesis's true risk.Uniform bounds apply the same gap bound to every hypothesis in a class for fixed sample size and confidence threshold.Source: §2 · p. 5
  • A uniform generalization bound can also upper-bound the sample size needed to ensure a specified gap threshold with a chosen probability.The bound may not be tight, so the resulting sample-size estimate is an upper bound on the minimum sufficient size.Source: §2 · p. 5
  • Structural risk minimization selects a model by combining its empirical risk with a generalization-gap bound, rather than minimizing empirical risk alone.Increasing model complexity can reduce empirical risk while increasing the gap bound, so the combined upper bound on true risk can have a minimum.Source: §2 · pp. 5–6
  • The paper asks for PQC bounds that depend explicitly on data-encoding hyperparameters and grow polynomially with the relevant encoding parameter for some strategies.Such bounds could support structural risk minimization across multiple architectural hyperparameters.Source: §2 · p. 7

3 Parametrized quantum circuit based model classes

The section defines PQC model classes with separate data-encoding and trainable gates, then represents their predictions using trigonometric functions whose accessible frequencies depend on the encoding strategy.

3 Parametrized quantum circuit based model classes

  • The prediction is the expectation value of an observable, with inputs taken as d-dimensional real vectors in [0, 2π).The interval is chosen as a natural fit for angle-parameterized hardware gates, though the authors note that data can be rescaled.Source: Figure 3 · p. 8, §3 · p. 8
  • Data coordinates enter through Hamiltonian-evolution gates, while trainable parameters enter through separate gates that may be arranged arbitrarily in the circuit.The model permits data re-uploading and does not require a fixed placement of the two gate types.Source: §3 · p. 8
  • Hamiltonian data-encoding gates let the model output be expanded as a generalized trigonometric polynomial whose frequency set depends on the encoding strategy.The coefficients depend on circuit parametrization and observable, whereas the frequency set is determined by the encoding strategy, including its Hamiltonian spectra.Source: §3 · p. 9
  • The number of encoding gates, N, is one encoding-strategy hyperparameter used to express the model class and target encoding-dependent bounds.The total gate count is the sum of the gate counts for each data coordinate.Source: §3 · p. 9
  • The analysis enlarges the model class to allow any observable with operator norm at most B and a universal trainable component, isolating encoding-strategy dependence.This class contains models that optimize both trainable-gate parameters and the measurement observable.Source: §3 · p. 9
  • Hamiltonian eigenvalue differences determine a gate’s frequencies, and multiple encoding gates combine their frequency sets through sumsets.Intermediate trainable unitaries change basis but do not alter the combined frequency set; the sumset construction extends recursively across encoding gates.Source: §3 · pp. 10–11
  • The coefficient dependence on circuit and observable is an open question, while the analysis relies only on the frequency set.Intermediate classes may offer a path to tighter bounds that depend on both the encoding and trainable parts.Source: §3 · pp. 9–10

4 Prior and related work

The review compares prior PQC generalization bounds by architecture restrictions, the quantities in their bounds, and their complexity measures. It contrasts encoding-first work with this paper’s goal of bounds that expose encoding-strategy hyperparameters for model selection.

4 Prior and related work

  • Prior PQC generalization work is classified by architecture restrictions, bound quantities, and the complexity measures used to derive bounds.The review distinguishes encoding-first approaches from this paper’s allowance for data re-uploading and explicit encoding-strategy dependence.Source: §4 · p. 11

4.1 Encoding-independent complexity and generalization bounds

  • Ref. bounds pseudo-dimension for encoding-first 2-local PQCs, while Refs. [29] and extend covering-number and agnostic-setting generalization analyses.These bounds are encoding-independent and depend on trainable-circuit size and depth, gate count, or observable operator norm.Source: §4.1 · pp. 11–12
  • Ref. [32] bounds VC-dimension by parametrized-observable rank and fat-shattering dimension by its Frobenius norm; Ref. [27] gives encoding-independent Rademacher and Gaussian complexity bounds in terms of resource-channel repetitions.Source: §4.1 · p. 12

4.2 Encoding-dependent complexity and generalization bounds

  • This paper seeks bounds expressed explicitly through encoding-strategy hyperparameters, unlike prior bounds whose encoding dependence is implicit and may require experiments to assess.The stated aim is to facilitate model selection by structural risk minimization.Source: §4 · p. 11, §4.2 · p. 12
  • Refs. and [31] use effective dimension and information-theoretic quantities, but their dependence on encoding strategy is not generally explicit in architectural hyperparameters.Ref. reports experimentally observed encoding dependence of effective dimension; Ref. [31] uses mutual information involving the postencoding state and classical data.Source: §4.2 · pp. 12–13
  • Refs. [26] and [28] give Rademacher bounds with implicit encoding dependence, while Ref. studies VC-dimension for a hardware-efficient ansatz with a specific encoding.Ref. [28] uses circuit size, depth, and magic; Ref. [26] also considers noisy models, and Ref. combines light-cone arguments with trigonometric representations.Source: §4.2 · p. 13
  • Ref. uses encoding- and training-data-dependent kernel-complexity quantities that can be difficult to express analytically, unlike the paper’s direct hyperparameter-based bounds.The procedure evaluates a geometric quantity first, then computes a model-complexity parameter if the model passes that test.Source: §4.2 · pp. 12–13

5 Generalization bounds for generalized trigonometric polynomials

This section derives generalization guarantees for generalized trigonometric polynomial classes by bounding complexity with Rademacher complexity and covering numbers, including sufficient training-set sizes for small generalization error. It examines dependence on frequency spectra and coefficient norms, relates the bounds to PQC models through class inclusion, and discusses proof approaches across norm regimes, with conditional extensions to general encoding strategies.

5 Generalization bounds for generalized trigonometric polynomials

  • Under Conjecture 1, suitable bounds for generalized trigonometric polynomials imply bounds for PQCs with general encoding strategies, including potentially non-integer frequency spectra.For integer frequency vectors, the section states that the coefficient bound can be chosen as 2B; the general-spectrum extension is conditional on the conjecture.Source: §5 · pp. 14–15

5.1 Generalization bounds for generalized trigonometric polynomials via Rademacher complexity

  • The Rademacher-complexity approach bounds the GTP class and yields a high-probability generalization guarantee, with Hoeffding-like 1/sqrt(m) scaling not expected to improve without further assumptions.One proof embeds the class in a single-hidden-layer neural network with sinusoidal activations; another avoids counting a continuum of frequencies when the class uses a discrete spectrum.Source: §5 · p. 15, §5.1 · pp. 16, 18, 19

5 Generalization bounds for generalized trigonometric polynomials

  • Metric-entropy bounds use the frequency count to determine the coefficient-space dimension, and chaining yields a generalization bound with the same leading-order scaling as the Rademacher approach.The section presents both approaches because they can differ when the coefficient constraint changes from a 2-norm to a general p-norm.Source: §5 · p. 16

5.1 Generalization bounds for generalized trigonometric polynomials via Rademacher complexity

  • Corollary 8 gives a sufficient training-set size for the generalization gap to be at most ε with probability at least 1 − δ, uniformly over H̃_B,Ω.The guarantee applies to i.i.d. training data under any probability measure P on [0, 2π)^d × R.Source: §5.1 · p. 20
  • The Rademacher-complexity analysis extends to bounded p-norm Fourier coefficients, with the generalization bound depending on the Hölder-conjugate exponent q and logarithmically on |Ω|.The authors note that structural properties such as sparsity may make p-norm analyses with p ≠ 2 useful.Source: §5.1 · pp. 20–21

5.2 Generalization bounds for generalized trigonometric polynomials via covering numbers

  • Lemma 10 bounds the covering number of the generalized trigonometric-polynomial class, and Theorem 11 uses covering-number control to derive a generalization bound.The theorem assumes a bounded Lipschitz loss and gives a high-probability guarantee for every function in the specified class.Source: §5.2 · pp. 21–22
  • Corollary 12 gives a sufficient training-set size for the generalization gap to be at most ε with probability at least 1 − δ, uniformly over F_B,Ω.The stated guarantee assumes an L-Lipschitz bounded loss and i.i.d. training data.Source: §5.2 · p. 24
  • For constant B̃, covering-number bounds have the same leading order in |Ω| across p-norms; the Rademacher approach is preferable for p < 2, while covering numbers are typically preferable for p > 2.The covering-number approach improves only logarithmic terms for 1 ≤ p < 2.Source: §5.2 · p. 24

6 Encoding-dependent generalization bounds for parametrized quantum circuits

The section derives PQC generalization bounds by representing model classes as generalized trigonometric polynomials whose frequencies are determined by the data-encoding strategy. It then compares how different encoding choices affect complexity growth and structural risk minimization.

6 Encoding-dependent generalization bounds for parametrized quantum circuits

  • The PQC model class is treated as a subset of generalized trigonometric polynomials, with frequency set Ω determined solely by encoding strategy D.Bounds in terms of |Ω(D)| are converted into bounds involving encoding hyperparameters such as the number of gates N and locality κ.Source: §6 · p. 25
  • The frequency sets for separate input coordinates combine multiplicatively because their frequencies are linearly independent.Source: §6 · p. 25
  • Repeating the same Hamiltonian gives polynomial scaling in the repetition count, with an exponent depending on the number of distinct frequencies it generates.Source: §6 · p. 27
  • The section gives bounds for four encoding cases: tensor-product Hamiltonians, a repeated single Hamiltonian with T frequencies, a repeated κ-local Hamiltonian, and possibly different κ-local Hamiltonians.The stated cases assume integer frequencies per data coordinate.Source: §6 · pp. 27–28
  • The bounds can in principle cover any encoding strategy once its corresponding |Ω(D)| is identified; extending cases (b)–(d) to non-integer frequencies is conditional on Conjecture 1.Source: §6 · p. 28

6.1 Comparison of data-encoding strategies from a generalization perspective

  • The comparison motivates structural risk minimization over encoding strategies, while the authors caution that their bounds need not be tight.Source: §6.1 · pp. 28–29
  • Repeated Pauli Hamiltonians, a fixed κ-local Hamiltonian, or a fixed Hamiltonian with 2T + 1 frequencies yield polynomial complexity and generalization bounds in N; N different κ-local Hamiltonians can yield exponential worst-case bounds.The exponential case uses Hamiltonians designed to maximize frequency differences, and the bounds may not be tight.Source: §6.1 · p. 29
  • For structural risk minimization, increasing the number of encoding gates N while holding κ or T fixed gives polynomial bounds, whereas increasing κ or T at fixed N gives exponential or doubly exponential bounds.The authors therefore favor increasing the number of encoding gates while keeping κ and/or T constant.Source: §6.1 · p. 29

7 Discussion

The discussion applies encoding-dependent bounds to structural risk minimization and explains how they can complement bounds on other architectural parameters. It also identifies complexity regimes and open questions that constrain how informative uniform bounds may be.

Structural risk minimization

  • Encoding-dependent bounds support choosing data-encoding hyperparameters by minimizing an upper bound on true risk.They do not guide choices for the trainable parts of the circuit; the authors suggest combining applicable bounds with a union bound for multi-dimensional selection.Source: §7 · pp. 29–30
  • Combining bounds for different architectural hyperparameters enables multi-dimensional structural risk minimization, including choices such as encoding and trainable-gate counts.The proposed union-bound approach generalizes to an arbitrary number of hyperparameters.Source: §7 · pp. 29–30

Open questions

  • Deriving a single bound that depends simultaneously on encoding and trainable-circuit parameters remains an open question.The authors suggest that characterizing structure in generalized trigonometric-polynomial coefficients could help; those coefficients depend on both encoding and trainable circuit parts.Source: §7 · p. 30

Limits of uniform bounds

  • Uniform generalization bounds can be trivial for sufficiently complex classes that fit randomly labeled data with zero empirical risk.The cited concern applies to classes capable of fitting unstructured data, typically requiring at least as many model parameters as training examples.Source: §7 · p. 30
  • The authors expect their bounds to be useful in the moderate-complexity regime, but they may cease to be meaningful as PQC models become overparameterized.They identify non-uniform bounds for PQCs and tests of behavior on randomly relabeled data as future research directions.Source: §7 · pp. 30–31

8 Conclusion

The paper derives encoding-dependent complexity and generalization bounds for PQC models, applies them to model selection, and describes their expected scope and limits.

Conclusion

  • The paper derives Rademacher complexity and metric entropy bounds for PQC model classes, then uses them to obtain uniform generalization bounds.The bounds depend explicitly on data-encoding architectural hyperparameters and apply to models incorporating data re-uploading.Source: §8 · p. 31
  • The bounds support comparing encoding strategies and, for certain strategies, selecting models through structural risk minimization.Combined with existing complementary bounds, they also support multi-dimensional structural risk minimization.Source: §8 · p. 31
  • The authors expect the bounds to be useful for models with fewer parameters than available data samples, but potentially not in the overparameterized regime.They identify several open questions and future research directions related to this limitation.Source: §8 · p. 31

A Auxiliary results from statistical learning theory

The appendix collects classical statistical-learning results used in the proofs, including tools for bounding Rademacher complexity and metric entropy.

Auxiliary results

  • Massart’s, Talagrand’s, and Dudley’s results are included among the classical tools used in the proofs.Massart’s lemma concerns a finite set in a Euclidean ball; the cited passages identify the other results by name and setting.Source: A Auxiliary results from statistical… · pp. 31–32
  • The appendix includes a Rademacher-complexity progression result that bounds a function class using the complexity of a base class.The result assumes a Lipschitz function and a base class that includes the zero function.Source: A Auxiliary results from statistical… · pp. 31–32
  • A layered-network result provides an upper bound on empirical Rademacher complexity under stated architectural assumptions.The supplied passages identify hidden layers and bounded neuron biases among those assumptions.Source: A Auxiliary results from statistical… · p. 32
Loading 2106.03880v3…