{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T17:24:44Z","timestamp":1789147484952,"version":"build-2803163510"},"reference-count":36,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T00:00:00Z","timestamp":1673568000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Dutch Research Council","award":["024.003.037"],"award-info":[{"award-number":["024.003.037"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Quantum machine learning (QML) models based on parameterized quantum circuits are often highlighted as candidates for quantum computing&apos;s near-term \u201ckiller application&apos;&apos;. 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\u00ed\u010dek et al. \\cite{havlivcek:qsvm}, and Schuld and Killoran \\cite{schuld:qsvm}. Firstly, using relationships to well understood classical models, we prove that two model parameters \u2013 i.e., the dimension of the sum of the images and the Frobenius norm of the observables used by the model \u2013 closely control the models&apos; complexity and therefore its generalization performance. Secondly, using ideas inspired by process tomography, we prove that these model parameters also closely control the models&apos; 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.<\/jats:p>","DOI":"10.22331\/q-2023-01-13-893","type":"journal-article","created":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T05:44:33Z","timestamp":1673588673000},"page":"893","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":32,"title":["Structural risk minimization for quantum linear classifiers"],"prefix":"10.22331","volume":"7","author":[{"given":"Casper","family":"Gyurik","sequence":"first","affiliation":[{"name":"LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dyon","family":"Vreumingen, van","sequence":"additional","affiliation":[{"name":"LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, Netherlands"},{"name":"QuSoft, Centrum Wiskunde & Informatica (CWI), Science Park 123, 1098 XG Amsterdam, Netherlands"},{"name":"Institute of Physics, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vedran","family":"Dunjko","sequence":"additional","affiliation":[{"name":"LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, Netherlands"},{"name":"LION, Leiden University, Niels Bohrweg 2, 2333 CA Leiden, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2023,1,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Vojt\u011bch Havl\u00ed\u010dek, Antonio D C\u00f3rcoles, 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.","DOI":"10.1038\/s41586-019-0980-2"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Maria Schuld and Nathan Killoran. ``Quantum machine learning in feature Hilbert spaces''. Physical review letters 122 (2019). arXiv:1803.07128.","DOI":"10.1103\/PhysRevLett.122.040504"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41586-019-1666-5"},{"key":"3","doi-asserted-by":"publisher","unstructured":"John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2 (2018). arXiv:1801.00862.","DOI":"10.22331\/q-2018-08-06-79"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s42254-021-00348-9"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Al\u00e1n Aspuru-Guzik. ``The theory of variational hybrid quantum-classical algorithms''. New Journal of Physics 18 (2016). arXiv:1509.04279.","DOI":"10.1088\/1367-2630\/18\/2\/023023"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/nature23879"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Peter JJ O\u2019Malley, 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.","DOI":"10.1103\/PhysRevX.6.031007"},{"key":"8","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028."},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/2058-9565\/ab4eb5"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.quant-ph\/0205133"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1098\/rspa.2010.0301"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41534-018-0116-9"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Diego Rist\u00e8, Marcus P Da Silva, Colm A Ryan, Andrew W Cross, Antonio D C\u00f3rcoles, 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.","DOI":"10.1038\/s41534-017-0017-3"},{"key":"14","unstructured":"Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. ``Foundations of machine learning''. MIT press. (2018)."},{"key":"15","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1109\/18.661502"},{"key":"16","doi-asserted-by":"crossref","unstructured":"Maria Schuld. ``Supervised quantum machine learning models are kernel methods'' (2021). arXiv:2101.11020.","DOI":"10.1007\/978-3-030-83098-4_6"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Matthias C Caro and Ishaun Datta. ``Pseudo-dimension of quantum circuits''. Quantum Machine Intelligence 2 (2020). arXiv:2002.01490.","DOI":"10.1007\/s42484-020-00027-5"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang. ``On the statistical complexity of quantum circuits'' (2021). arXiv:2101.06154.","DOI":"10.1103\/PhysRevA.105.062431"},{"key":"19","unstructured":"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."},{"key":"20","unstructured":"Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang. ``Rademacher complexity of noisy quantum circuits'' (2021). arXiv:2103.03139."},{"key":"21","doi-asserted-by":"publisher","unstructured":"Amira Abbas, David Sutter, Christa Zoufal, Aur\u00e9lien Lucchi, Alessio Figalli, and Stefan Woerner. ``The power of quantum neural networks''. Nature Computational Science 1 (2021). arXiv:2011.00027.","DOI":"10.1038\/s43588-021-00084-1"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.128.080506"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Leonardo Banchi, Jason Pereira, and Stefano Pirandola. ``Generalization in quantum machine learning: A quantum information standpoint''. PRX Quantum 2 (2021). arXiv:2102.08991.","DOI":"10.1103\/PRXQuantum.2.040321"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41467-021-22539-9"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. ``A rigorous and robust quantum speed-up in supervised machine learning''. Nature Physics 17, 1013\u20131017 (2021). arXiv:2010.02174.","DOI":"10.1038\/s41567-021-01287-z"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Bernhard Sch\u00f6lkopf, Alexander J Smola, Francis Bach, et al. ``Learning with kernels: support vector machines, regularization, optimization, and beyond''. MIT press. (2002).","DOI":"10.7551\/mitpress\/4175.001.0001"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1007\/978-3-319-21852-6_3"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Michael J Kearns and Robert E Schapire. ``Efficient distribution-free learning of probabilistic concepts''. Journal of Computer and System Sciences 48 (1994).","DOI":"10.1016\/S0022-0000(05)80062-5"},{"key":"29","unstructured":"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)."},{"key":"30","unstructured":"Dyon van Vreumingen. ``Quantum feature space learning: characterisation and possible advantages''. Master's thesis. Leiden University. (2020)."},{"key":"31","unstructured":"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."},{"key":"32","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1109\/18.705570"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Martin Anthony and Peter L Bartlett. ``Function learning from interpolation''. Combinatorics, Probability and Computing 9 (2000).","DOI":"10.1017\/S0963548300004247"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Peter L Bartlett and Philip M Long. ``Prediction, learning, uniform convergence, and scale-sensitive dimensions''. Journal of Computer and System Sciences 56 (1998).","DOI":"10.1006\/jcss.1997.1557"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. ``The learnability of quantum states''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 463 (2007). arXiv:quant-ph\/0608142.","DOI":"10.1098\/rspa.2007.0113"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-01-13-893\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T05:44:37Z","timestamp":1673588677000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-01-13-893\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,13]]},"references-count":36,"URL":"https:\/\/doi.org\/10.22331\/q-2023-01-13-893","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,13]]},"article-number":"893"}}