acceptodds
Under review as a conference paper at ICLR 2027

A VC-Dimension View of Capacity and Generalization in Quantum Machine Learning with Classical Data

Abstract

Quantum machine learning (QML) models are often motivated by the large Hilbert spaces accessible to parametrized quantum circuits, but their capacity is ultimately determined by their trainable parameters. We study model capacity through the Vapnik-Chervonenkis (VC) dimension for several QML families. For purely univariate QML classifiers, we derive linear VC dimensions, analogous to univariate classical models. Multivariate uniform re-uploading analyzes the VC dimension from the encoding side, providing an upper bound of for trainable parameters and input dimension , which is consistent with empirical evaluations. Finally, the bounded-reuse trainable Pauli classifier analyzes the VC dimension from the trainable parameter side, obtaining a upper bound, similar to a feedforward neural net. We conclude that asymptotic scaling depends on input dimension and architecture rather than on the model's classical or quantum nature. Empirically, we find that QML models trained on classical data exhibit generalization trends consistent with what VC-bounds predict. Conversely, previous studies have observed strong generalization for very few quantum-data, suggesting that QML generalization behavior is not yet fully understood.

Primary area:
learning theory
Keywords:
quantum machine learning, VC Dimension, Vapnik-Chervonenkis, capacity, generalization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ZWpaOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper utilizes the classical tool of VC-dimension to study the capacity and generalization abilities of quantum machine learning models when learning classical data. The work is set in the context of binary classification, where the authors provide VC bounds for various classes of quantum circuits defined in the paper. Additionally, they investigate through experiments how sample size, parameter count, and input dimension affect generalization. The main conclusion is that for high-capacity, data re-uploading models with a fixed number of parameters, increasing the input dimension leads to worse generalization.

Critical strengths
  1. The paper derives detailed mathematical formulas and attempts to challenge established findings.

  2. The appendix provides numerous experimental plots related to the study.

Critical weaknesses
  1. The paper only discusses binary classification, limiting the scope of its applicability.

  2. The presentation of the paper is somewhat lacking. In section 2.3, it aims to introduce several different types of quantum classifiers, but the descriptions are not sufficiently clear. It would be better to illustrate them with figures for clarity, rather than relying solely on precise mathematical definitions. Furthermore, the classifications in 2.3 are not mutually exclusive, resulting in conceptual confusion.

  3. The phenomenon of poor generalization in data re-uploading models observed in the experiments is not new; prior work [1] has already studied this, which the paper fails to cite. Moreover, the previous work appears to draw an even stronger conclusion: as the input dimension increases, the predictions approach random guessing, rather than just decreased generalization. This raises significant doubts about the novelty of the current paper.

  4. I believe that the treatment of previous work on quantum generalization bounds is not appropriate. For example, previous bounds such as those in [2] consider quantum machine learning scenarios where quantum states come first and then variational parameterized gates, but do not address data re-uploading scenarios.

[1] Wang X, Tao HX, Wu RB. Predictive performance of deep quantum data re-uploading models. arXiv preprint arXiv:2505.20337. 2025 May 24.

[2] Caro MC, Huang HY, Cerezo M, Sharma K, Sornborger A, Cincio L, Coles PJ. Generalization in quantum machine learning from few training data. Nature communications. 2022 Aug 22;13(1):4919.

Questions for authors
  1. Could the authors clarify the differences between the phenomenon of poor generalization for data re-uploading models observed in this work and that in [1]? In fact, it seems the conclusion in [1] is even stronger.

  2. The paper claims that QML is like a feedforward neural network. Does the phenomenon of poor generalization in data re-uploading models also exist in classical models? Classical models seem to retain strong expressivity while also maintaining good generalization performance.

[1] Wang X, Tao HX, Wu RB. Predictive performance of deep quantum data re-uploading models. arXiv preprint arXiv:2505.20337. 2025 May 24.

3 comments

Thank you reviewer ZWpa for the critical feedback on our paper and for giving us a chance to address your concerns. We appreciate the effort that went into reviewing the paper.

Critical Weaknesses

  1. Our focus on binary classification is due to the VC dimension, which is defined based on the binary labelings a model class can realize. While extensions for multiclass classifiers exist, we consider this out of scope for this manuscript.

  2. We agree, the presentation of the paper can and should be improved. We could not include illustrations of the quantum classifiers as we ran out of space for the main part. Figure 3 in appendix C.3 shows an exemplary architecture of the uniform re-uploading classifier. The model classes in 2.3 are mutually non-exclusive, as our goal was to keep them as generic as possible. For a classifier fitting in multiple model families, the lowest upper bound can be applied. E.g. for a bounded-reuse trainable pauli classifier using uniform re-uplaoding, the VCdim is <min⁡(O(dlog⁡d),O((dp+1)p))< \min \bigl( O(d \log d), O\bigl(\bigl(\frac{d}{p}+1\bigr)^p\bigr) \bigr). In the final version, we will add figures illustrating the different families of quantum classifiers and clarify the intuition behind the mutually non-exclusive definition of the classifiers.

  3. Thank you for pointing out the Wang et al. paper, which is very interesting. It shows that the predictive performance of data re-uploading models decreases and the generalization gap increases with increasing input dimension and number of encoding layers (i.e. with increasing parameter count). While we observe similar generalization behavior as Wang et al., our experiments use the train set size as additional variable besides input dimension and number of layers/parameters. Moreover, we analyze additional classes of QML models (trainable Pauli, trainable encoding) and our conclusion focuses on a different aspect: that the generalization behavior of the evaluated QML families follows trends predicted by the VC dimension. We believe this conclusion is a novelty, as it is based on the VC dimension bounds we derived in this work. We will cite the Wang et al. paper in the final version of our manuscript and point out its important finding regarding the predictive performance of data re-uploading models.

  4. Regarding previous work on quantum generalization bounds: We agree that the previous work section in the introduction is rather short. We will extend it in the final manuscript and also explicitely mention the generalization error bound derived by Caro et al. However, their bound is distinct from ours, as they directly bound the generalization error, whereas we bound the VC dimension. A table comparing our bounds with the ones by Caro et al. can be found in our response to reviewer fLRG. Also we want to clarify that in Remark 9 in Supplementary Note 3, Caro et al. state that their results extend to re-uploading classifiers.

Questions

  1. Please see point 3 in our remarks regarding the critical weaknesses above.

  2. Literature suggests that classical re-uploading models achieve better generalization than quantum re-uploading models and classical non re-uploading models: Schreiber et al. [1] showed that classical surrogates of data-reuploading models achieve better generalization on synthetic datasets compared to quantum data-reuploading models. Qiao et al. [2] introduce a quantum-inspired data-reuploading network that outperforms fully-connected layers and state-of-the-art neural network layers.

[1] Schreiber, F. J., Eisert, J., & Meyer, J. J. (2023). Classical Surrogates for Quantum Learning Models. Phys. Rev. Lett., 131, 100803. doi:10.1103/PhysRevLett.131.100803

[2]. Qiao, W., Wang, S., Zhang, P., Ming, Y., & Zhao, J. (2026). Q-RUN: Quantum-inspired data re-uploading networks. Information Processing & Management, 63(7, Part A), 104770. doi:10.1016/j.ipm.2026.104770

Thank you for the reviewer's response. However:

  1. First, the research object of this article is "Capacity and Generalization." If VC dimension can only be limited to binary classification, then it only shows that one should not approach it from the VC-Dimension View, since QML tasks can never always be just binary classification.

  2. I think you can draw figures and put them in the appendix. I still don't understand what you mean by these, such as trainable Pauli, trainable encoding.

  3. This is very strange. Isn't your purpose of bounding VC-dimension to obtain a generalization bound? Although there is Capacity, this is only a theoretical metric and difficult to verify experimentally, so what matters is still the generalization bound. Furthermore, if the big-O notation is removed, is your bound still tight?

Thank you for the response.

  1. Binary classification is a foundational setting for analyzing capacity and generalization. For example the PAC framework has been developed for Boolean concept learning in [1]. Moreover, [2] showed that the nearly-tight VC dimension bounds for ReLU classifiers depend on parameter count and network depth. Finally, [3] use Rademacher complexity (another uniform generalization bound) to analyze capacity in neural networks and obtain their lower bound by considering binary classification. All three papers are highly influential with over 9,500, 1,000 and 900 citations, respectively (accoridng to Google Scholar). Extending the analysis to the multiclass setting is an interesting task for future work, however we consider this out of the scope for the current manuscript. One could use e.g. graph dimension or Natarajan dimension for this [4,5].

  2. We have added figures of the individual model classes in the appendix and referenced them in section 2.3 where we introduce the model classes. We have also switched to amplitude encoding for the trainable pauli classifier. This ensures that the model is in the trainable pauli classifier class but not in the re-uploading classifer class. You can find the revised manuscript on open review. We are currently rerunning the experiments using the trainable pauli classifier with amplitude encoding and will update the figures once the experiments are finished.

3.1 We use VC dimension for both, capacity analysis and generalization bounds. While capacity is a theoretical metric, it is still relevant in practice: it specifies how complicated a pattern can be that the model can express. This is relevant because if a certain class of models can express a complicated pattern using less trainable parameters than another model class, a smaller model might suffice, potentially lowering the resources required to train and host the model. Say model A and B from two different model classes have similar VC dimension and similar generalization gap, however model A uses only a fraction of the trainable parameters of model B. Then, all things equal we would expect that model A requires less resources. Of course, the generalization bound also influences the resources required to train the model, mostly through the train set size.

3.2 Our VC dimension for the univariate re-uploading model is 23d−2n+1\frac{2}{3} d -2n +1 which is exact. For the other QML models, we do not claim that the explicit VC-dimension upper bounds are attained.

[1] Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134-1142.

[2] Bartlett, P. L., Harvey, N., Liaw, C., & Mehrabian, A. (2019). Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63), 1-17.

[3] Neyshabur, B., Tomioka, R. & Srebro, N.. (2015). Norm-Based Capacity Control in Neural Networks. <i>Proceedings of The 28th Conference on Learning Theory</i>, in <i>Proceedings of Machine Learning Research</i> 40:1376-1401 Available from https://proceedings.mlr.press/v40/Neyshabur15.html.

[4] Daniely, A., Sabato, S., Ben-David, S., & Shalev-Shwartz, S. (2015). Multiclass learnability and the ERM principle. The Journal of Machine Learning Research, 16(1), 2377-2404.

[5] Natarajan, B. K. (1989). On learning sets and functions. Machine Learning, 4(1), 67–97. doi:10.1007/BF00114804

Reviewer_ptnrOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates the capacity and generalization behavior of quantum machine learning classifiers on classical data through VC-dimension analysis. The authors derive theoretical capacity bounds for quantum circuits, including re-uploading architecture.

Critical strengths

The paper addresses the question of the generalization in QML which is interesting and important.

Critical weaknesses
  1. The derived VC-based generalization bounds are generally loose and may be uninformative for the training-set sizes considered in the experiments.
  2. Theorem 3.3 establishes an input dimension dependent upper bound of O(d/p+1)p)\mathcal{O}(d/p+1)^p) for multivariate uniform re-uploading classifiers. However, the re-uploading circuits considered in the experiments appear to satisfy the bounded reuse Pauli assumptions of Theorem 3.1, which would additionally imply an O(dlog⁡d)\mathcal{O}(d\log d) upper bound. Thus, the actual VC dimension may be substantially smaller than the bound in Theorem 3.3 and it remains unclear whether the proposed input dimension dependence reflects an intrinsic property of the model capacity
  3. The empirical evidence is insufficient to establish a strong connection between the derived theoretical capacity bounds and practical generalization performance.
  4. The theoretical results rely on specially constructed quantum circuit architectures.
Questions for authors
  1. In Fig.1 and 4, could the authors clarify the theoretical interpretation of the dashed VC-based curves?
  2. The bounded reuse Pauli classifier in Theorem 3.1 providing an O(dlog⁡d)\mathcal{O}(d\log d) upper bound. Since the experimental re-uploading architectures appear to belong to this model family, how does this result compare with the O(d/p+1)p)\mathcal{O}(d/p+1)^p) bound in Theorem 3.3?
  3. Can the theoretical results extend to more general quantum architectures?
1 comment

Thank you reviewer ptnr for the feedback on our paper and for giving us a chance to address your concerns. We appreciate the effort that went into reviewing the paper.

Critical Weaknesses

  1. Yes, we have derived tight bounds only for the univariate n-qubit Re-uploading model. For trainable encoding and the fourier network we derived O(d)O(d) bounds. The other models are more generic which makes it challenging to derive asymptotic tight bounds.

  2. You are right, the re-uploading circuits used in the experiments fulfills the bounded reuse Pauli assumptions. However, in the experiments probing the influence of input dimension dd on the generalization gap (fig. 2), we keep the number of encoding gates and trainable gates (and hence dd) constant. Increasing the input dimension thus leads to less re-uploadings of the individual features (or less neurons in the hidden layer of the feedforward NN). With dd constant across the range of input dimensions, the O(dlog⁡d)O(d \log d) bound of the bounded-reuse Pauli and feedfoward NN would suggest no clear relation between the input dimension and the generalization gap, which is what we observed for the trainable Pauli model and feedforward NN. For the re-uploading model, however, a trend of increasing generalization gap with input dimension can be observed. We treat this as empirical evidence that the VC dimension fo the re-uploading model depends on the input dimension. The model classes in 2.3 are mutually non-exclusive, as our goal was to keep them as general as possible. For a classifier fitting in multiple classes, the lowest upper bound can be applied. E.g. for a bounded-reuse trainable pauli classifier using uniform re-uploading, the VCdim is <max⁡(O(dlog⁡d),O((dp+1)p))< \max \bigl( O(d \log d), O\bigl(\bigl(\frac{d}{p}+1\bigr)^p\bigr) \bigr). We will clarify this in the final version of the manuscript.

  3. We agree, the empirical evidence does not show a strong connection to the derived theoretical bounds. The focus of the experiments is to show that generalization of QML follows trends predicted by VC bounds rather than showing a tight relationship between empirical evidence and the bounds. Moreover, we wanted to create a counterexample to the good generalization of QML that has been observed by other authors, e.g. on quantum phase of matter datasets, by showing that QML does not always generalize well in practice.

  4. In order to define useful VC dimension bounds we must make some assumptions on the model architecture. However, we believe that the trainable Pauli classifier already is a fairly general QML model.

Questions

  1. The dashed curves in Fig. 1a and Fig. 4 plot the VC dimension bound (either exact values or lower bounds). Since the generalization gap increases with the VC dimension for N>>N >> VC dim, the true bound of the respective model is at the dashed line or higher. Hence, the dashed lines are conservative estimates of the maximum generalization gap predicted by the VC dimension. As long as the empirical VC dimension remains below the dashed line, the empirical generalization gap does not deviate from what the VC dimension predicts.

  2. Please see our response to critical weakness 2 above.

  3. Please see our response to critical weakness 3 above.

Reviewer_fLRGOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the capacity of several QML classifiers through the VC dimension, and asks whether PQCs get more capacity per trainable parameter than classical models. The main results are an exact VC dimension for a univariate n-qubit re-uploading classifier, an upper bound for Pauli-generated circuits with bounded parameter reuse, and bounds for a multivariate re-uploading model that depend on the input dimension p. The authors conclude that capacity depends on architecture and input dimension, not on whether the model is quantum. Experiments on 8 classical datasets show that the generalization gaps follow the trends VC theory predicts, although the bounds themselves are vacuous at the dataset sizes usually used in QML.

Critical strengths

The question is relevant. QML is often motivated by the size of the Hilbert space, and looking at capacity per trainable parameter is a useful counterpoint. The exact result for the univariate re-uploading model is clean. The experimental study covers a range of settings, with the code made available. The authors also acknowledge that the bounds are loose.

Critical weaknesses
  • Most of the results in the paper come from applying well-known tools to PQCs, such as sign-pattern counting and the Fourier-spectrum view of data re-uploading. In addition, the paper does not clearly explain how it goes beyond Caro et al. (2021, 2022), who already give generalization bounds for QML models based on the encoding and on the number of trainable gates.
  • The bounds obtained are not always tight. For instance, the upper and lower bounds for the multivariate re-uploading model differ exponentially in p. Furthermore, similarities between upper bounds across model classes do not necessarily imply that these classes have comparable capacities. Therefore, while the results suggest that capacity is determined more by the architecture than by the quantum nature of the model, they do not provide sufficient evidence to firmly establish this conclusion.
  • Figure 1a compares models trained on different datasets and with very different parameter counts, which makes the comparison hard to interpret.
  • The p-dependence result in figure 2b is limited to a single dataset and uses cyclic parameter reuse, which seems to fall outside the scope of Theorem 3.3. A direct capacity measurement, such as random-label fitting as a function of d and p, would provide stronger evidence for the result.
Questions for authors

Besides addressing the above mentioned weaknesses, address the following:

  1. What exactly is new relative to Caro et al. (2021, 2022)? Those papers already give generalization bounds in terms of encoding structure and the number of trainable gates. Can the authors compare their scalings explicitly, for example in a short table next to Table 1?
  2. How sensitive are the gap trends to the optimization choices (restarts, learning rate, initialization)? Would results with matched datasets and matched d across models change the comparison in figure 1a?

Minor Comments:

  • The title says "classical data," but the capacity results don't depend on the data.
  • Please clarify what "parameter efficiency" means, since a higher VC dimension per parameter isn't necessarily a good thing.
2 comments

Thank you reviewer fLRG for the feedback on our paper and for giving us a chance to address your concerns. We appreciate the effort that went into reviewing the paper.

Critical Weaknesses

  1. We agree that the tools we are using to derive the VC dimensions are well-known. Nevertheless, we believe that the VC dimension bounds for different QML model families and the comparison with classical ML families are novel. Additionally, our empirical results seem to confirm the trends predicted by our VC bounds and show bad generalization on small train sets, which is a different perspective than the observed good generalization of QML on quantum phase recognition datasets. For a distinction from the Caro et al. papers, please see our response to question 1 below.

  2. We state in the limitations section that our bounds are not always tight and that they should be improved in further work. We agree that a comparison of loose bounds does not automatically extend to model capacity. Our conclusion was based on the univariate n-qubit re-uploading, trainable encoding and the fourier network which have the same asymptotic bounds as small classical models such as perceptron or shalllow ReLU network. We will update our conclusion in the final manuscript towards: our results suggest that quantum models are not observed to have intrinsically higher capacity than classical ML, however, further work in this direction is required.

  3. Please see our response to question 2 below.

  4. We are sorry for the confusion we caused. That sentence in the model description in appendix C.3 is an artifact from a previous version of the experiments. The re-uploading model in fig. 2b is NOT using cyclic parameter reuse, instead it varies the number of re-uploadings rr. The model uses 60 encoding gates, each encoding one feature, interleaved with 60 trainable gates with 3 parameters each (plus one additional trainable layer before the first encoding layer). With $ p \in \{ 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 \}$ we obtain $ r \in \{ 20, 15, 12, 10, 6, 5, 4, 3, 2, 1 \}$ for d=198d=198 across all configurations without requiring any parameter-reuse. We will fix the description of the experiment in the final manuscript. This experiment require a dataset that allows us to choose input dimension without influencing the difficulty, which makes it difficult to come up with other datasets. We thought about running random-label fitting experiments, however a model class with VC dimension NN requires only some model of the model class to scatter some set of NN samples. Finding exactly that set and showing that no set of size N+1N+1 can be shattered is computationally infeasible for large NN.

Questions

  1. We consider our results complementary to that of Caro et al. We bound the VC dimension rather than the generalization gap directly. We will post a table comparing our scaling with the ones of Caro in the next comment.

  2. We report average results with standard deviation over 10 seeds, and hence show variability associated with random initialization. The learning rate was chosen such that the model achieves low train loss. A drastically higher learning rate would most likely decrease the generalization gap as the train error increases. Fig 1a combines univariate and multivariate models, which is why different datasets are used. The perceptron is an outlier and should use either spline or census_income. We agree that focusing on a single dataset in the main part would have been the better choice and we will update fig 1 with results of all models on the univariate sine dataset in the final manuscript. Matching dd between all models is impossible: for p=1p=1 (since we also have univariate models), the perceptron requires d=p+1=2d=p+1 = 2 parameters. Add the same time, the univariate shallow ReLU uses d=3h+1>2d=3h+1 > 2 with h≥1h \ge 1 and the univariate re-uploading requires d=3n(r+1)>2d=3n(r+1) > 2 with r≥1r \ge 1.

Minor Comments:

  1. We put "classical data" in the title since the data encoding of the quantum models requires classical data. Without that assumption, the results would extend to quantum data, as VC dimension does not depend on the data.

  2. A model class has VC dimension NN if the model can realize all binary labelings of some set of NN samples. While a model with large VC dimension usually requires more samples to achieve a given generalization gap, we argue in the opposite direction: A model with better parameter efficiency needs less trainable parameters to achieve the same VC dimension and hence to realize all 2N′2^{N'} possible labelings of a set of N′N' samples than a low efficiency model. Consequently, the parameter efficient model potentially needs only a smaller model to achieve the same capacity/expressivity. We therefore interpret VC dimension as an effective parameter count and compare its scaling with respect to the number of trainable parameters.

AuthorsOpenReview ↗

Comparison of Generalization Bounds with Caro et al. (2021, 2022)

AspectCaro et al. (2021)Caro et al. (2022)Ours
Model classPQCs with fixed data-encoding Hamiltonians, embedded in bounded real-valued Fourier-function classesPQCs with trainable local quantum channels and arbitrary fixed gates; includes gate sharingTrainable-Pauli classifiers, re-uploading models, trainable encoding models
Quantity boundedRademacher complexity and explicit generalization gap boundGeneralization gap, derived through metric-entropy bounds on quantum-channel classesVC dimension of thresholded binary classifiers
Main structural resourceNumber of encoding frequencies s=∣Ω∣s=\lvert\Omega\rvert together with norm boundsIndependently trainable local gates TT and maximum reuse MMIndependent parameters dd and total parameter occurrences QQ
Generalization-gap bound scalingO~(∥Ω∥N+log⁡(1/δ)N)\widetilde O \left(\sqrt{\frac{\|\Omega\| }{N}}+\sqrt{\frac{\log(1/\delta)}{N}}\right) with probability $ \ge 1 − \delta $O(dlog⁡(Md)N)O\left(\sqrt{\frac{d\log(Md)}{N}}\right) when T=Θ(d)T=\Theta(d) and reuse is boundedO(dlog⁡(ed)log⁡(eNdlog⁡(ed))+log⁡(1/δ)N)O\left(\sqrt{\frac{d\log(ed) \log \left(\frac{eN}{d\log(ed)}\right)+\log(1/\delta)}{N}}\right) for bounded-reuse trainable Pauli classifier
Generalization lossBounded Lipschitz loss on real-valued predictionsBounded observable-based lossBinary 00–11 classification loss
Data re-uploadingIncluded for fixed encoding strategiesIncluded for parameter-independent encoding gatesIncluded if meeting the trainable-Pauli assumptions and additionally as a separate model family
TightnessGeneralization-gap upper bounds not proved tight. No general matching lower bound for the actual PQC classGeneralization-gap upper bounds not proved tight. No general matching lower bound for the gate-count dependenceUpper bounds generally not proved tight. Exact VC dimensions established for specified univariate re-uploading architectures

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.