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.
Given the emerging availability of "noisy intermediate scale quantum" devices, a variety of approaches have been proposed for using such devices in supervised learning. One particularly important way in which these approaches differ, is in the way the classical data is entered into the quantum classification algorithm. In light of this, and given the importance of generalization bounds, it is natural to ask whether one can determine how the appropriate notions of complexity for generalization depend on the different strategies for encoding classical data into the quantum classifier.
In this work, we answer this question by quantifying rigorously how various notions of complexity depend on the strategy for encoding data into a quantum classifier. These results immediately allow us to state generalization bounds for such quantum classification algorithms. With these, we can give concrete recommendations for choosing classical-to-quantum encoding strategies.
 Vedran Dunjkoand Hans J Briegel ``Machine learning & artificial intelligence in the quantum domain: A review of recent progress'' Rep. Prog. Phys. 81, 074001 (2018).
 N. Wiebe, A. Kapoor, and K. Svore, ``Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning'' Quant. Inf. Comp. 15, 0318 (2015).
 S. Lloyd, M. Mohseni, and P. Rebentrost, ``Quantum algorithms for supervised and unsupervised machine learning'' arXiv:1307.0411 (2013).
 R. Sweke, J.-P. Seifert, D. Hangleiter, and J. Eisert, ``On the quantum versus classical learnability of discrete distributions'' Quantum 5, 417 (2021).
 Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme, ``A rigorous and robust quantum speed-up in supervised machine learning'' Nature Physics 17, 1013–1017 (2021) Bandiera_abtest: a Cg_type: Nature Research Journals Number: 9 Primary_atype: Research Publisher: Nature Publishing Group Subject_term: Computational science;Information theory and computation;Quantum information Subject_term_id: computational-science;information-theory-and-computation;quantum-information.
 K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik, ``Noisy intermediate-scale quantum (NISQ) algorithms'' arXiv:2101.08448 (2021).
 J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, ``The theory of variational hybrid quantum-classical algorithms'' New J. Phys. 18, 023023 (2016).
 M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles, ``Variational quantum algorithms'' Nature Reviews Physics 3, 625–644 (2021) Bandiera_abtest: a Cg_type: Nature Research Journals Number: 9 Primary_atype: Reviews Publisher: Nature Publishing Group Subject_term: Computer science;Quantum information;Quantum simulation Subject_term_id: computer-science;quantum-information;quantum-simulation.
 Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini, ``Parameterized quantum circuits as machine learning models'' Quant. Sc. Tech. 4, 043001 (2019).
 S. Sim, P. D. Johnson, and A. Aspuru-Guzik, ``Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms'' Adv. Quant. Tech. 2, 1900070 (2019).
 Thomas Hubregtsen, Josef Pichlmeier, Patrick Stecher, and Koen Bertels, ``Evaluation of parameterized quantum circuits: on the relation between classification accuracy, expressibility, and entangling capability'' Quant. Mach. Int. 3, 1–19 (2021).
 M. Schuld ``Quantum machine learning models are kernel methods'' arXiv:2101.11020 (2021).
 A. Pérez-Salinas, A. Cervera-Lierta, E. Gil-Fuster, and J. I. Latorre, ``Data re-uploading for a universal quantum classifier'' Quantum 4, 226 (2020).
 C. Bishop ``Pattern recognition and machine learning'' Springer (2006).
 B. Schölkopfand A. J. Smola ``Learning with kernels: support vector machines, regularization, optimization, and beyond'' MIT Press (2002).
 M. Mohri, A. Rostamizadeh, and A. Talwalkar, ``Foundations of machine learning'' MIT Press (2018).
 Nick Littlestoneand Manfred Warmuth ``Relating data compression and learnability'' Technical report, University of California Santa Cruz (1986).
 Amira Abbas, David Sutter, Christa Zoufal, Aurélien Lucchi, Alessio Figalli, and Stefan Woerner, ``The power of quantum neural networks'' Nature Computational Science 1, 403–409 (2021).
 K. Bu, D. E. Koh, L. Li, Q. Luo, and Y. Zhang, ``On the statistical complexity of quantum circuits'' arXiv:2101.06154 (2021).
 K. Bu, D. E. Koh, L. Li, Q. Luo, and Y. Zhang, ``Effects of quantum resources on the statistical complexity of quantum circuits'' arXiv:2102.03282 (2021).
 K. Bu, D. E. Koh, L. L., Q. Luo, and Y. Zhang, ``Rademacher complexity of noisy quantum circuits'' arXiv:2103.03139 (2021).
 Y. Du, Z. Tu, X. Yuan, and D. Tao, ``An efficient measure for the expressivity of variational quantum algorithms'' arXiv:2104.09961 (2021).
 H.-Y. Huang, M. Broughton, M. Mohseni, R. Babbush, S. Boixo, H. Neven, and J. R. McClean, ``Power of data in quantum machine learning'' Nature Comm. 12, 1–9 (2021).
 L. Banchi, J. Pereira, and S. Pirandola, ``Generalization in quantum machine learning: A quantum information perspective'' arXiv:2102.08991 (2021).
 C. Gyurik, D. van Vreumingen, and V. Dunjko, ``Structural risk minimization for quantum linear classifiers'' arXiv:2105.05566 (2021).
 M. Schuld, R. Sweke, and J. J. Meyer, ``Effect of data encoding on the expressive power of variational quantum-machine-learning models'' Phys. Rev. A 103, 032430 (2021).
 M. M Wolf ``Mathematical foundations of machine learning'' (2020).
 Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals, ``Understanding deep learning requires rethinking generalization'' arXiv:1611.03530 (2016).
 Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio, ``Fantastic generalization measures and where to find them'' arXiv:1912.02178 (2019).
 V. Bergholm, J. Izaac, M. Schuld, C. Gogolin, M. S. Alam, S. Ahmed, J. M. Arrazola, C. Blank, A. Delgado, S. Jahangiri, K. McKiernan, J. J. Meyer, Z. Niu, A. Száva, and N. Killoran, ``PennyLane: Automatic differentiation of hybrid quantum-classical computations'' arXiv:1811.04968 (2020).
 Chih-Chieh Chen, Masaya Watabe, Kodai Shiba, Masaru Sogabe, Katsuyoshi Sakamoto, and Tomah Sogabe, ``On the Expressibility and Overfitting of Quantum Circuit Learning'' ACM Transactions on Quantum Computing 2, 1–24 (2021).
 P. Massart ``Some applications of concentration inequalities to statistics'' Annales de la Faculté des sciences de Toulouse : Mathématiques Ser. 6, 9, 245–303 (2000).
 Beng Yee Gan, Daniel Leykam, and Dimitris G. Angelakis, "Fock state-enhanced expressivity of quantum machine learning models", EPJ Quantum Technology 9 1, 16 (2022).
 Charles Moussa, Jan N. van Rijn, Thomas Bäck, and Vedran Dunjko, Lecture Notes in Computer Science 13601, 32 (2022) ISBN:978-3-031-18839-8.
 Masahiro Kobayashi, Kouhei Nakaji, and Naoki Yamamoto, "Overfitting in quantum machine learning and entangling dropout", Quantum Machine Intelligence 4 2, 30 (2022).
 Charles Moussa, Yash J. Patel, Vedran Dunjko, Thomas Bäck, and Jan N. van Rijn, "Hyperparameter importance and optimization of quantum neural networks across small datasets", Machine Learning (2023).
 Chih-Chieh Chen, Masaru Sogabe, Kodai Shiba, Katsuyoshi Sakamoto, and Tomah Sogabe, "General Vapnik–Chervonenkis dimension bounds for quantum circuit learning", Journal of Physics: Complexity 3 4, 045007 (2022).
 Wenhui Ren, Weikang Li, Shibo Xu, Ke Wang, Wenjie Jiang, Feitong Jin, Xuhao Zhu, Jiachen Chen, Zixuan Song, Pengfei Zhang, Hang Dong, Xu Zhang, Jinfeng Deng, Yu Gao, Chuanyu Zhang, Yaozu Wu, Bing Zhang, Qiujiang Guo, Hekang Li, Zhen Wang, Jacob Biamonte, Chao Song, Dong-Ling Deng, and H. Wang, "Experimental quantum adversarial learning with programmable superconducting qubits", Nature Computational Science 2 11, 711 (2022).
 Weikang Li, Zhi-de Lu, and Dong-Ling Deng, "Quantum Neural Network Classifiers: A Tutorial", SciPost Physics Lecture Notes 61 (2022).
 Annie E. Paine, Vincent E. Elfving, and Oleksandr Kyriienko, "Quantum Quantile Mechanics: Solving Stochastic Differential Equations for Generating Time‐Series", Advanced Quantum Technologies 6 10, 2300065 (2023).
 Franz J. Schreiber, Jens Eisert, and Johannes Jakob Meyer, "Classical Surrogates for Quantum Learning Models", Physical Review Letters 131 10, 100803 (2023).
 Maxwell T. West, Shu-Lok Tsang, Jia S. Low, Charles D. Hill, Christopher Leckie, Lloyd C. L. Hollenberg, Sarah M. Erfani, and Muhammad Usman, "Towards quantum enhanced adversarial robustness in machine learning", Nature Machine Intelligence 5 6, 581 (2023).
 Sharu Theresa Jose and Osvaldo Simeone, 2023 IEEE Information Theory Workshop (ITW) 532 (2023) ISBN:979-8-3503-0149-6.
 Maniraman Periyasamy, Nico Meyer, Christian Ufrecht, Daniel D. Scherer, Axel Plinge, and Christopher Mutschler, 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) 31 (2022) ISBN:978-1-6654-9113-6.
 Gennaro De Luca and Yinong Chen, 2022 6th Asian Conference on Artificial Intelligence Technology (ACAIT) 1 (2022) ISBN:978-1-6654-5311-0.
 Simon C. Marshall, Casper Gyurik, and Vedran Dunjko, "High Dimensional Quantum Machine Learning With Small Quantum Computers", Quantum 7, 1078 (2023).
 Alexey Melnikov, Mohammad Kordzanganeh, Alexander Alodjants, and Ray-Kuang Lee, "Quantum machine learning: from physics to software engineering", Advances in Physics: X 8 1, 2165452 (2023).
 Yuxuan Du, Yibo Yang, Dacheng Tao, and Min-Hsiu Hsieh, "Problem-Dependent Power of Quantum Neural Networks on Multiclass Classification", Physical Review Letters 131 14, 140601 (2023).
 S. Shin, Y. S. Teo, and H. Jeong, "Exponential data encoding for quantum supervised learning", Physical Review A 107 1, 012422 (2023).
 Annie E. Paine, Vincent E. Elfving, and Oleksandr Kyriienko, "Quantum kernel methods for solving regression problems and differential equations", Physical Review A 107 3, 032428 (2023).
 Matthias C. Caro, Hsin-Yuan Huang, Nicholas Ezzell, Joe Gibbs, Andrew T. Sornborger, Lukasz Cincio, Patrick J. Coles, and Zoë Holmes, "Out-of-distribution generalization for learning quantum dynamics", Nature Communications 14 1, 3751 (2023).
 Yuxuan Du, Yang Qian, Xingyao Wu, and Dacheng Tao, "A Distributed Learning Scheme for Variational Quantum Algorithms", IEEE Transactions on Quantum Engineering 3, 1 (2022).
 Haoyuan Cai, Qi Ye, and Dong-Ling Deng, "Sample complexity of learning parametric quantum circuits", Quantum Science and Technology 7 2, 025014 (2022).
 Matthias C. Caro, Hsin-Yuan Huang, M. Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J. Coles, "Generalization in quantum machine learning from few training data", Nature Communications 13 1, 4919 (2022).
 M. Cerezo, Guillaume Verdon, Hsin-Yuan Huang, Lukasz Cincio, and Patrick J. Coles, "Challenges and opportunities in quantum machine learning", Nature Computational Science 2 9, 567 (2022).
 Dylan Herman, Rudy Raymond, Muyuan Li, Nicolas Robles, Antonio Mezzacapo, and Marco Pistoia, "Expressivity of Variational Quantum Machine Learning on the Boolean Cube", IEEE Transactions on Quantum Engineering 4, 1 (2023).
 Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).
 Weikang Li and Dong-Ling Deng, "Recent advances for quantum classifiers", Science China Physics, Mechanics, and Astronomy 65 2, 220301 (2022).
 Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao, "Learnability of Quantum Neural Networks", PRX Quantum 2 4, 040337 (2021).
 André J. Ferreira-Martins, Leandro Silva, Alberto Palhares, Rodrigo Pereira, Diogo O. Soares-Pinto, Rafael Chaves, and Askery Canabarro, "Detecting quantum phase transitions in a frustrated spin chain via transfer learning of a quantum classifier algorithm", arXiv:2309.15339, (2023).
 Alberto Manzano, David Dechant, Jordi Tura, and Vedran Dunjko, "Parametrized Quantum Circuits and their approximation capacities in the context of quantum machine learning", arXiv:2307.14792, (2023).
The above citations are from Crossref's cited-by service (last updated successfully 2023-11-28 21:02:58) and SAO/NASA ADS (last updated successfully 2023-11-28 21:02:59). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.