- 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
-
The paper derives detailed mathematical formulas and attempts to challenge established findings.
-
The appendix provides numerous experimental plots related to the study.
Critical weaknesses
-
The paper only discusses binary classification, limiting the scope of its applicability.
-
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.
-
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.
-
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
-
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.
-
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 for the reviewer's response. However:
-
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.
-
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.
-
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.
-
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].
-
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 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
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
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.
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(dlogd),O((pd+1)p)). 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.
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.
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
Please see point 3 in our remarks regarding the critical weaknesses above.
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