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).
 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).
 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).
 Simon C. Marshall, Casper Gyurik, and Vedran Dunjko, "High Dimensional Quantum Machine Learning With Small Quantum Computers", arXiv:2203.13739.
 Yuxuan Du, Yang Qian, and Dacheng Tao, "Accelerating variational quantum algorithms with multiple quantum processors", arXiv:2106.12819.
The above citations are from Crossref's cited-by service (last updated successfully 2022-10-01 14:39:07) and SAO/NASA ADS (last updated successfully 2022-10-01 14:39:08). 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.