Structural risk minimization for quantum linear classifiers

Structural risk minimization for quantum linear classifiers

Time Stamp: January 13, 2023 5:28 AM

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.

Abstract

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.

Structural risk minimization for quantum linear classifiers PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Featured image: Illustration of structural risk minimization (source: Mohri, Mehryar, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018).

► 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.
https:/​/​doi.org/​10.1038/​s41586-019-0980-2
arXiv:1804.11326

[2] Maria Schuld and Nathan Killoran. “Quantum machine learning in feature Hilbert spaces”. Physical review letters 122 (2019). arXiv:1803.07128.
https:/​/​doi.org/​10.1103/​PhysRevLett.122.040504
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.
https:/​/​doi.org/​10.1038/​s41586-019-1666-5
arXiv:1910.11333

[4] John Preskill. “Quantum computing in the NISQ era and beyond”. Quantum 2 (2018). arXiv:1801.00862.
https:/​/​doi.org/​10.22331/​q-2018-08-06-79
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.
https:/​/​doi.org/​10.1038/​s42254-021-00348-9
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.
https:/​/​doi.org/​10.1088/​1367-2630/​18/​2/​023023
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.
https:/​/​doi.org/​10.1038/​nature23879
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.
https:/​/​doi.org/​10.1103/​PhysRevX.6.031007
arXiv:1512.06860

[9] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate optimization algorithm” (2014). arXiv:1411.4028.
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.
https:/​/​doi.org/​10.1088/​2058-9565/​ab4eb5
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.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0205133
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.
https:/​/​doi.org/​10.1098/​rspa.2010.0301
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.
https:/​/​doi.org/​10.1038/​s41534-018-0116-9
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.
https:/​/​doi.org/​10.1038/​s41534-017-0017-3
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).
https:/​/​doi.org/​10.1109/​18.661502

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

[18] Matthias C Caro and Ishaun Datta. “Pseudo-dimension of quantum circuits”. Quantum Machine Intelligence 2 (2020). arXiv:2002.01490.
https:/​/​doi.org/​10.1007/​s42484-020-00027-5
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.
https:/​/​doi.org/​10.1103/​PhysRevA.105.062431
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.
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.
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.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1
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.
https:/​/​doi.org/​10.1103/​PhysRevLett.128.080506
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.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.040321
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.
https:/​/​doi.org/​10.1038/​s41467-021-22539-9
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.
https:/​/​doi.org/​10.1038/​s41567-021-01287-z
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).
https:/​/​doi.org/​10.7551/​mitpress/​4175.001.0001

[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).
https:/​/​doi.org/​10.1007/​978-3-319-21852-6_3

[29] Michael J Kearns and Robert E Schapire. “Efficient distribution-free learning of probabilistic concepts”. Journal of Computer and System Sciences 48 (1994).
https:/​/​doi.org/​10.1016/​S0022-0000(05)80062-5

[30] Michael M Wolf. “Mathematical foundations of supervised learning”. https:/​/​www-m5.ma.tum.de/​foswiki/​pub/​M5/​Allgemeines/​MA4801_2020S/​ML_notes_main.pdf (2020).
https:/​/​www-m5.ma.tum.de/​foswiki/​pub/​M5/​Allgemeines/​MA4801_2020S/​ML_notes_main.pdf

[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.
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).
https:/​/​doi.org/​10.1109/​18.705570

[34] Martin Anthony and Peter L Bartlett. “Function learning from interpolation”. Combinatorics, Probability and Computing 9 (2000).
https:/​/​doi.org/​10.1017/​S0963548300004247

[35] Peter L Bartlett and Philip M Long. “Prediction, learning, uniform convergence, and scale-sensitive dimensions”. Journal of Computer and System Sciences 56 (1998).
https:/​/​doi.org/​10.1006/​jcss.1997.1557

[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.
https:/​/​doi.org/​10.1098/​rspa.2007.0113
arXiv:quant-ph/0608142

Cited by

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

[2] 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”, arXiv:2204.10268.

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

[4] 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”, arXiv:2204.10269.

[5] Sofiene Jerbi, Lukas J. Fiderer, Hendrik Poulsen Nautrup, Jonas M. Kübler, Hans J. Briegel, and Vedran Dunjko, “Quantum machine learning beyond kernel methods”, arXiv:2110.13162.

[6] Matthias C. Caro, Elies Gil-Fuster, Johannes Jakob Meyer, Jens Eisert, and Ryan Sweke, “Encoding-dependent generalization bounds for parametrized quantum circuits”, arXiv:2106.03880.

[7] Supanut Thanasilp, Samson Wang, M. Cerezo, and Zoë Holmes, “Exponential concentration and untrainability in quantum kernel methods”, arXiv:2208.11060.

[8] Masahiro Kobayashi, Kohei Nakaji, and Naoki Yamamoto, “Overfitting in quantum machine learning and entangling dropout”, arXiv:2205.11446.

[9] Brian Coyle, “Machine learning applications for noisy intermediate-scale quantum computers”, arXiv:2205.09414.

[10] Evan Peters and Maria Schuld, “Generalization despite overfitting in quantum machine learning models”, arXiv:2209.05523.

[11] Marco Fanizza, Yihui Quek, and Matteo Rosati, “Learning quantum processes without input control”, arXiv:2211.05005.

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

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

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

[15] Yuxuan Du, Yibo Yang, Dacheng Tao, and Min-Hsiu Hsieh, “Demystify Problem-Dependent Power of Quantum Neural Networks on Multi-Class Classification”, arXiv:2301.01597.

The above citations are from SAO/NASA ADS (last updated successfully 2023-01-15 10:53:14). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2023-01-15 10:53:12).

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.

Time Stamp:

More from Quantum Journal