Source-linked AI summary
Understanding quantum machine learning also requires rethinking generalization
Elies Gil-Fuster, Jens Eisert, Carlos Bravo-Prieto
TL;DR
Uniform quantum generalization bounds offer limited evidence about performance on unseen data, and it remained unclear whether randomization tests would reveal similar limits for quantum models. The authors test QNNs on randomized data and provide an analytical construction; these models fit random data, while the reasons for successful generalization remain unknown.
Problem
It remained unclear whether randomization tests would reveal limits in the uniform generalization bounds that dominate QML, which are intended to guarantee performance on unseen data.
Source: §I · p. 1, D. Implications · p. 7Method
The paper applies randomization tests to QNNs and analytically constructs polynomially sized QNNs that fit arbitrary labels to quantum states.
Source: §III · p. 9Results
QNNs fit random data, including randomized labels and quantum states, and polynomially sized QNNs can fit arbitrary labeling of data sets.
Source: §III · p. 9Takeaways & Limitations
Uniform generalization bounds must be vacuous in regimes where models fit a large fraction of random data, but good generalization with few data remains possible.
Source: §III · p. 9The reasons why QML models may generalize successfully remain undiscovered.
Source: §III · p. 9
Abstract
from arXiv · showhide
Quantum machine learning models have shown successful generalization performance even when trained with few data. In this work, through systematic randomization experiments, we show that traditional approaches to understanding generalization fail to explain the behavior of such quantum models. Our experiments reveal that state-of-the-art quantum neural networks accurately fit random states and random labeling of training data. This ability to memorize random data defies current notions of small generalization error, problematizing approaches that build on complexity measures such as the VC dimension, the Rademacher complexity, and all their uniform relatives. We complement our empirical results with a theoretical construction showing that quantum neural networks can fit arbitrary labels to quantum states, hinting at their memorization ability. Our results do not preclude the possibility of good generalization with few training data but rather rule out any possible guarantees based only on the properties of the model family. These findings expose a fundamental challenge in the conventional understanding of generalization in quantum machine learning and highlight the need for a paradigm shift in the study of quantum models for machine learning tasks.
I. INTRODUCTION
Classical randomization tests exposed limits in uniform generalization bounds, but their implications for quantum models remained uncertain. This work applies analogous tests to current-scale QML models, finding that they fit randomized data while leaving the reasons for successful generalization unexplained.
I. INTRODUCTION
- Numerical randomization tests on specific state-of-the-art large classical neural networks challenged established uniform generalization bounds, which cannot distinguish hypotheses with good out-of-sample performance from those that completely overfit the training data.VC dimension and Rademacher complexity were inadequate in explaining the generalization behavior of large classical neural networks.Source: §I · p. 1
- Whether analogous randomization tests would expose the same limitations for quantum models was an open question, since current QML models are much smaller than large classical networks.Prior quantum generalization work focused essentially uniquely on uniform variants.Source: §I · pp. 1–2
- Quantum models fit randomized labels and states, challenging uniform generalization bounds as explanations of their behavior.The paper also gives a construction in which PQCs fit training sets of polynomial size in the number of qubits.Source: §I · p. 2
- The experiments challenge guarantees of good generalization from uniform bounds with few data, but do not explain why QML models sometimes generalize well [58] [71].The reasons for their successful generalization remain elusive.Source: §I · p. 2
A. Statistical learning theory background
Statistical learning theory distinguishes expected risk from training-set empirical risk and uses their difference to characterize generalization. The section contrasts the conventional bias–variance picture with models that can fit training data while still generalizing well.
A. Statistical learning theory background
- The generalization gap is the difference between a model’s expected risk on the data distribution and its empirical risk on the training set.The expected risk measures predictive accuracy on data sampled from the distribution, while empirical risk evaluates performance on the restricted training set.Source: A. Statistical learning theory… · p. 3
- Complexity measures such as VC dimension and Rademacher complexity describe the whole function family, not an individual function..Source: A. Statistical learning theory… · p. 3
- The conventional bias–variance account treats expected risk as a trade-off between two components, with model selection aiming to balance them.The goal is to minimize expected risk, which is unattainable by construction.Source: A. Statistical learning theory… · p. 3
- The conventional account associates underfitting with high bias and imperfect training classification, and overfitting with high variance and perfect training classification that may generalize poorly.The paper notes that modern learning models can instead fit data while generalizing well, and presents analogous behavior for current-scale, non-overparameterized PQCs.Source: A. Statistical learning theory… · p. 3
B. Randomization tests
The authors apply randomization tests to quantum models by comparing training on original and randomized data. Their experiments show that QML models can fit random and partially corrupted labels, as well as labels assigned to random quantum states.
B. Randomization tests
- The tests compare QNN training accuracy on true labels with accuracy on randomized labels, then examine randomized input states as well.The approach builds on randomization tests from non-parametric statistics.Source: B. Randomization tests · p. 3
- Existing QML models can accurately fit random labels and labels assigned to random quantum states.The experiments report a large generalization gap after randomization without changing circuit structure, parameter count, training-set size, or learning algorithm.Source: B. Randomization tests · p. 3
- As label noise rises, generalization error steadily increases, while QNNs can extract residual signal and fit the noisy portion by brute-force memorization.The authors state that existing QML models accurately fit partially corrupted labels.Source: B. Randomization tests · p. 3
- Training remains largely unaffected by removing state-label correlation, and label randomization changes no task property other than the data itself.The paper presents these as additional findings about the trainability and controlled nature of its randomization tests.Source: B. Randomization tests · p. 3
C. Numerical results
In quantum-phase classification, QCNNs can fit random labels and random states, yet their test performance remains at guessing levels. Corruption experiments show that the models also fit noise while retaining signal from uncorrupted labels.
C. Numerical results
- The experiments used a QCNN to classify four quantum phases from ground states of the generalized cluster Hamiltonian.The QCNN interleaves convolutional layers with pooling layers that reduce the state dimension.Source: C. Numerical results · p. 4
- Random-label and random-state experiments produced large generalization gaps; random-label gaps approached 0.75, with the largest reported for training sets up to N = 10.The random-state gap followed a similar trend, and test accuracy in both settings failed to surpass random guessing.Source: C. Numerical results · pp. 5–6, Figure 3 · p. 6
- With label corruption increasing from r = 0 to r = 1, test error rose toward 75% while training accuracy remained 100%.The authors report that the QCNN extracted remaining signal while fitting noise; at r = 1, fitting random labels was slightly faster on average than fitting real labels.Source: C. Numerical results · p. 5, Figure 3 · p. 6
- The random-state protocol replaced amplitudes with normalized Gaussian samples based on each state's amplitude mean and variance, and QCNNs still fit small training sets perfectly.The resulting generalization gap resembled that for random labels and decreased as training-set size grew.Source: C. Numerical results · pp. 5–6
D. Implications
The paper examines whether uniform generalization bounds can meaningfully constrain the gap between training and expected performance. Its experiments show that bounds remain applicable to randomized data even when models fit that data, making them vacuous or impractically large in the observed regimes.
D. Implications
- Generalization bounds aim to control the uncertain difference between empirical training risk and expected risk, but typical guarantees depend on model-family complexity and apply uniformly across hypotheses.The paper notes that many such bounds also hold irrespective of the data distribution.Source: D. Implications · p. 7
- Because randomized distributions leave the uniform bound unchanged, fitting uncorrelated data can yield large empirical gaps while the same bound still applies.With uniformly random labels among M classes, expected error is close to its maximum for any hypothesis.Source: D. Implications · p. 7
- The bound is vacuous for training sets up to the largest observed size N′ that a model can fit on random data, and remains impractically large beyond N′ in a further regime.This empirical lower bound arises without specifying a complexity measure.Source: D. Implications · pp. 7–8
- The findings apply to every uniform generalization bound, regardless of derivation, supporting a shift in how QML generalization is studied.They do not explain why QML models can generalize well in some settings.Source: D. Implications · p. 8
E. Analytical results
The analytical results establish sufficient conditions under which quantum circuits and parameterized quantum circuits can fit arbitrary labels to finite sets of quantum states. These constructions are conditional, not a claim that fitting is always possible in the worst case.
E. Analytical results
- The results give sufficient conditions for fitting arbitrary training sets, not a guarantee that fitting is possible in every worst-case scenario.Finite sample expressivity means memorizing arbitrary data on fixed-size subsets; if a model realizes every labeling of a training set, uniform generalization bounds become trivial.Source: E. Analytical results · p. 8
- When the states’ Gram matrix W is well-conditioned, a polynomial-depth quantum circuit can be constructed to produce any chosen real labels as expectation values on those states.The theorem provides a constructive fit for a finite set of states and labels.Source: E. Analytical results · p. 8
- The first construction requires query access to the input states on every circuit execution and uses a SWAP-test circuit unlike usual QML ansätze.The authors therefore propose a more restricted alternative aimed at PQCs, using efficiently preparable state approximations; examples include protocols inspired by classical shadows or tensor networks.Source: E. Analytical results · pp. 8–9
- For polynomially many distinguishable states, a polynomial-depth PQC can be constructed to realize any real labeling, provided the stated distinguishability condition holds.The construction also requires efficient state preparation, inner-product computation, and a well-conditioned matrix of state approximations.Source: E. Analytical results · pp. 8–9
III. DISCUSSION
The discussion reports that quantum neural networks can fit randomized data, while arguing that uniform generalization bounds do not explain this behavior. These findings leave open why QML models may generalize well and caution against treating quantum and classical models as interchangeable.
III. DISCUSSION
- QNNs fit randomized labels and quantum states, and polynomially sized QNNs can fit arbitrary dataset labelings.These results do not rule out good generalization with few training data; the reasons for successful generalization remain unknown.Source: §III · p. 9
- Uniform bounds applied to QCNNs are trivially loose, so the same bounds are vacuous for less restricted, larger models.The discussion identifies this implication because QCNNs are more restricted than deeper, higher-variance architectures.Source: §III · p. 9
- The findings do not exclude good generalization with few training data, but the reasons it might occur remain undiscovered.The paper's results instead indicate that uniform-bound arguments cannot guarantee it.Source: §III · p. 9
- The randomization experiments used training-set sizes that had supported successful phase classification, countering the explanation that random-data fitting arose only from tiny samples.The authors conclude that these sets were large enough for the original task.Source: §III · pp. 9–10
- Although the study and Ref. both examine leading models on state-of-the-art tasks, their different platforms, model functions, and tasks warrant caution in comparing outcomes.Similar results across the quantum and classical studies should not be taken for granted.Source: §III · p. 10
- The authors distinguish small QCNNs from large classical networks: QCNN parameter counts scale logarithmically with qubit number while quantum-state dimensions scale exponentially.They suggest that QML generalization mechanisms may differ from those in classical machine learning.Source: §III · p. 10
A. Numerical methods
The numerical methods describe how the experiments' quantum states and circuits were simulated, and how the QCNN parameters were optimized. Different state-generation and simulation choices were used for the two experimental settings.
A. Numerical methods
- The numerical-methods section covers implementations for random and real labels, random states, and partially corrupted labels.It includes the computation techniques used in these experimental settings.Source: A. Numerical methods · p. 10
- For random and real labels, ground-state vectors were obtained using variational matrix product states, and 16- and 32-qubit QCNN simulations used bond dimension χ = 40.Further increasing the bond dimension produced no noticeable changes in the results.Source: A. Numerical methods · p. 10
- For random states and partially corrupted labels, ground states were obtained by direct Hamiltonian diagonalization for QCNNs with n ∈ {8, 10, 12} qubits.These circuits were simulated using Qibo.Source: A. Numerical methods · p. 10
- Across implementations, parameters were randomly initialized and updated with CMA-ES, a stochastic, derivative-free optimization method.The study's generated code is also available in Ref..Source: A. Numerical methods · p. 10
B. Analytical methods
The analytical methods construct auxiliary states from available approximation protocols and use their inner-product matrix to determine whether arbitrary labels can be represented. A convex semidefinite program tests whether a well-conditioned matrix can be obtained.
B. Analytical methods
- The algorithm can combine multiple approximation states into each auxiliary state and cast coefficient selection as a linear optimization problem with a positive-semidefinite constraint.The target is a well-conditioned resulting matrix; individual auxiliary states need not be close to their corresponding original states if that condition holds.Source: B. Analytical methods · pp. 10–11
- Theorem 3 uses a convex semidefinite program to decide in polynomial time whether coefficients can make the auxiliary-state inner-product matrix well-conditioned, and to output such coefficients when possible.The theorem assumes polynomially many linearly independent input states, efficiently preparable approximations, and polynomial-time computation of tr(ρiσj_k).Source: B. Analytical methods · p. 11
- Algorithm 1 combines available approximation protocols by selecting coefficients for auxiliary states, returning 0 if no combination satisfies the distinguishability condition.Theorem 3 establishes the algorithm's correctness.Source: B. Analytical methods · pp. 10–11
- When the original Gram matrix is well-conditioned and the approximations include each original state, coefficients can preserve good conditioning; if all approximations are |0⟩⟨0|, no suitable coefficients exist.The described algorithm handles these cases in polynomial time.Source: B. Analytical methods · p. 12
- The intermediate states can be formed as linear combinations of auxiliary states without leaving the parameterized quantum circuit framework.The construction's success depends on the distinguishability condition and a well-conditioned resulting matrix.Source: B. Analytical methods · pp. 11–12
Appendix A: Proof of Theorem 1
The appendices give constructive expressivity results: a well-conditioned Gram matrix permits a quantum circuit to realize arbitrary labels on given states, and a distinguishability condition extends the construction to parameterized quantum circuits using approximations.
Appendix A: Proof of Theorem 1
- If the Gram matrix of the input states is well-conditioned, a polynomial-depth quantum circuit can realize any real labels as expectation values on those states.The construction uses an intermediate variable obtained by solving a linear system with the Gram matrix.Source: Appendix A · p. 15
- Theorem 1's observable can be estimated with an unbiased estimator whose error decreases linearly with the number of repetitions.The proof describes estimating state overlaps, for example with the SWAP test.Source: Appendix A · p. 16
Appendix B: Proof of Theorem 2
- Theorem 2 constructs a polynomial-depth parameterized quantum circuit that can realize arbitrary real labels when the input states satisfy the distinguishability condition.The proof replaces the original states with efficiently prepared approximations and constructs intermediate states from them.Source: Appendix B · pp. 16, 18
- Theorem 2's construction uses an auxiliary register to encode weights and controlled operations to select among state-preparation unitaries within the circuit.The auxiliary register has ⌈log2(N)⌉ qubits; the method incorporates sampling and sign information into the parameterized circuit.Source: Appendix B · p. 17