Structural risk minimization for quantum linear classifiers

Casper Gyurik1, Dyon Vreumingen, van1,2,3, and Vedran Dunjko1,4

1LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, Netherlands
2QuSoft, Centrum Wiskunde & Informatica (CWI), Science Park 123, 1098 XG Amsterdam, Netherlands
3Institute of Physics, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands
4LION, Leiden University, Niels Bohrweg 2, 2333 CA Leiden, Netherlands

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Quantum machine learning (QML) models based on parameterized quantum circuits are often highlighted as candidates for quantum computing's near-term “killer application''. However, the understanding of the empirical and generalization performance of these models is still in its infancy. In this paper we study how to balance between training accuracy and generalization performance (also called structural risk minimization) for two prominent QML models introduced by Havlíček et al. [1], and Schuld and Killoran [2]. Firstly, using relationships to well understood classical models, we prove that two model parameters – i.e., the dimension of the sum of the images and the Frobenius norm of the observables used by the model – closely control the models' complexity and therefore its generalization performance. Secondly, using ideas inspired by process tomography, we prove that these model parameters also closely control the models' ability to capture correlations in sets of training examples. In summary, our results give rise to new options for structural risk minimization for QML models.

► BibTeX data

► References

[1] Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. ``Supervised learning with quantum-enhanced feature spaces''. Nature 567 (2019). arXiv:1804.11326.

[2] Maria Schuld and Nathan Killoran. ``Quantum machine learning in feature Hilbert spaces''. Physical review letters 122 (2019). arXiv:1803.07128.

[3] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. ``Quantum supremacy using a programmable superconducting processor''. Nature 574 (2019). arXiv:1910.11333.

[4] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2 (2018). arXiv:1801.00862.

[5] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. ``Variational quantum algorithms''. Nature Reviews Physics 3 (2021). arXiv:2012.09265.

[6] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. ``The theory of variational hybrid quantum-classical algorithms''. New Journal of Physics 18 (2016). arXiv:1509.04279.

[7] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. ``Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets''. Nature 549 (2017). arXiv:1704.05018.

[8] Peter JJ O’Malley, Ryan Babbush, Ian D Kivlichan, Jonathan Romero, Jarrod R McClean, Rami Barends, Julian Kelly, Pedram Roushan, Andrew Tranter, Nan Ding, et al. ``Scalable quantum simulation of molecular energies''. Physical Review X 6 (2016). arXiv:1512.06860.

[9] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028.

[10] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. ``Parameterized quantum circuits as machine learning models''. Quantum Science and Technology 4 (2019). arXiv:1906.07682.

[11] Barbara M Terhal and David P DiVincenzo. ``Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games''. Quantum Information & Computation 4 (2004). arXiv:quant-ph/​0205133.

[12] Michael J Bremner, Richard Jozsa, and Dan J Shepherd. ``Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467 (2011). arXiv:1005.1407.

[13] Edward Grant, Marcello Benedetti, Shuxiang Cao, Andrew Hallam, Joshua Lockhart, Vid Stojevic, Andrew G Green, and Simone Severini. ``Hierarchical quantum classifiers''. npj Quantum Information 4 (2018). arXiv:1804.03680.

[14] Diego Ristè, Marcus P Da Silva, Colm A Ryan, Andrew W Cross, Antonio D Córcoles, John A Smolin, Jay M Gambetta, Jerry M Chow, and Blake R Johnson. ``Demonstration of quantum advantage in machine learning''. npj Quantum Information 3 (2017). arXiv:1512.06069.

[15] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. ``Foundations of machine learning''. MIT press. (2018).

[16] Peter L Bartlett. ``The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network''. IEEE transactions on Information Theory 44 (1998).

[17] Maria Schuld. ``Supervised quantum machine learning models are kernel methods'' (2021). arXiv:2101.11020.

[18] Matthias C Caro and Ishaun Datta. ``Pseudo-dimension of quantum circuits''. Quantum Machine Intelligence 2 (2020). arXiv:2002.01490.

[19] Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang. ``On the statistical complexity of quantum circuits'' (2021). arXiv:2101.06154.

[20] Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang. ``Effects of quantum resources on the statistical complexity of quantum circuits'' (2021). arXiv:2102.03282.

[21] Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang. ``Rademacher complexity of noisy quantum circuits'' (2021). arXiv:2103.03139.

[22] Amira Abbas, David Sutter, Christa Zoufal, Aurélien Lucchi, Alessio Figalli, and Stefan Woerner. ``The power of quantum neural networks''. Nature Computational Science 1 (2021). arXiv:2011.00027.

[23] Yuxuan Du, Zhuozhuo Tu, Xiao Yuan, and Dacheng Tao. ``Efficient measure for the expressivity of variational quantum algorithms''. Physical Review Letters 128 (2022). arXiv:2104.09961.

[24] Leonardo Banchi, Jason Pereira, and Stefano Pirandola. ``Generalization in quantum machine learning: A quantum information standpoint''. PRX Quantum 2 (2021). arXiv:2102.08991.

[25] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean. ``Power of data in quantum machine learning''. Nature communications 12 (2021). arXiv:2011.01938.

[26] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. ``A rigorous and robust quantum speed-up in supervised machine learning''. Nature Physics 17, 1013–1017 (2021). arXiv:2010.02174.

[27] Bernhard Schölkopf, Alexander J Smola, Francis Bach, et al. ``Learning with kernels: support vector machines, regularization, optimization, and beyond''. MIT press. (2002).

[28] Vladimir N Vapnik and A Ya Chervonenkis. ``On the uniform convergence of relative frequencies of events to their probabilities''. In Measures of complexity. Springer (2015).

[29] Michael J Kearns and Robert E Schapire. ``Efficient distribution-free learning of probabilistic concepts''. Journal of Computer and System Sciences 48 (1994).

[30] Michael M Wolf. ``Mathematical foundations of supervised learning''. https:/​/​​foswiki/​pub/​M5/​Allgemeines/​MA4801_2020S/​ML_notes_main.pdf (2020).

[31] Dyon van Vreumingen. ``Quantum feature space learning: characterisation and possible advantages''. Master's thesis. Leiden University. (2020).

[32] Jae-Eun Park, Brian Quanz, Steve Wood, Heather Higgins, and Ray Harishankar. ``Practical application improvement to quantum svm: theory to practice'' (2020). arXiv:2012.07725.

[33] John Shawe-Taylor, Peter L. Bartlett, Robert C. Williamson, and Martin Anthony. ``Structural risk minimization over data-dependent hierarchies''. IEEE Transactions on Information Theory (1998).

[34] Martin Anthony and Peter L Bartlett. ``Function learning from interpolation''. Combinatorics, Probability and Computing 9 (2000).

[35] Peter L Bartlett and Philip M Long. ``Prediction, learning, uniform convergence, and scale-sensitive dimensions''. Journal of Computer and System Sciences 56 (1998).

[36] Scott Aaronson. ``The learnability of quantum states''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 463 (2007). arXiv:quant-ph/​0608142.

Cited by

[1] Sofiene Jerbi, Lukas J. Fiderer, Hendrik Poulsen Nautrup, Jonas M. Kübler, Hans J. Briegel, and Vedran Dunjko, "Quantum machine learning beyond kernel methods", Nature Communications 14 1, 517 (2023).

[2] Aastha Sharma, Harsh Kumar Sharma, and Kirti Sharma, 2023 10th IEEE Uttar Pradesh Section International Conference on Electrical, Electronics and Computer Engineering (UPCON) 982 (2023) ISBN:979-8-3503-8247-1.

[3] Evan Peters and Maria Schuld, "Generalization despite overfitting in quantum machine learning models", Quantum 7, 1210 (2023).

[4] Elies Gil-Fuster, Jens Eisert, and Carlos Bravo-Prieto, "Understanding quantum machine learning also requires rethinking generalization", Nature Communications 15 1, 2277 (2024).

[5] Javeria Amin, Muhammad Almas Anjum, Rida Zahra, Muhammad Imran Sharif, Seifedine Kadry, and Lukas Sevcik, "Pest Localization Using YOLOv5 and Classification Based on Quantum Convolutional Network", Agriculture 13 3, 662 (2023).

[6] Diego Tancara, Hossein T. Dinani, Ariel Norambuena, Felipe F. Fanchini, and Raúl Coto, "Kernel-based quantum regressor models learning non-Markovianity", Physical Review A 107 2, 022402 (2023).

[7] Elies Gil-Fuster, Jens Eisert, and Vedran Dunjko, "On the expressivity of embedding quantum kernels", Machine Learning: Science and Technology 5 2, 025003 (2024).

[8] Leonardo Banchi, Jason Luke Pereira, Sharu Theresa Jose, and Osvaldo Simeone, "Statistical Complexity of Quantum Learning", Advanced Quantum Technologies 2300311 (2024).

[9] 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).

[10] 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).

[11] Joe Gibbs, Zoë Holmes, Matthias C. Caro, Nicholas Ezzell, Hsin-Yuan Huang, Lukasz Cincio, Andrew T. Sornborger, and Patrick J. Coles, "Dynamical simulation via quantum machine learning with provable generalization", Physical Review Research 6 1, 013241 (2024).

[12] 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).

[13] 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, 4919 (2022).

[14] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao, "Learnability of Quantum Neural Networks", PRX Quantum 2 4, 040337 (2021).

[15] Matthias C. Caro, Elies Gil-Fuster, Johannes Jakob Meyer, Jens Eisert, and Ryan Sweke, "Encoding-dependent generalization bounds for parametrized quantum circuits", Quantum 5, 582 (2021).

[16] Brian Coyle, "Machine learning applications for noisy intermediate-scale quantum computers", arXiv:2205.09414, (2022).

[17] 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).

[18] Masahiro Kobayashi, Kouhei Nakaji, and Naoki Yamamoto, "Overfitting in quantum machine learning and entangling dropout", arXiv:2205.11446, (2022).

[19] Dylan Herman, Rudy Raymond, Muyuan Li, Nicolas Robles, Antonio Mezzacapo, and Marco Pistoia, "Expressivity of Variational Quantum Machine Learning on the Boolean Cube", arXiv:2204.05286, (2022).

[20] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao, "Erratum: Learnability of Quantum Neural Networks [PRX QUANTUM 2, 040337 (2021)]", PRX Quantum 3 3, 030901 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-19 10:07:36) and SAO/NASA ADS (last updated successfully 2024-04-19 10:07:37). The list may be incomplete as not all publishers provide suitable and complete citation data.