{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T18:18:51Z","timestamp":1772561931210,"version":"3.50.1"},"reference-count":34,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T00:00:00Z","timestamp":1704931200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Quantum support vector machines employ quantum circuits to define the kernel function. It has been shown that this approach offers a provable exponential speedup compared to any known classical algorithm for certain data sets. The training of such models corresponds to solving a convex optimization problem either via its primal or dual formulation. Due to the probabilistic nature of quantum mechanics, the training algorithms are affected by statistical uncertainty, which has a major impact on their complexity. We show that the dual problem can be solved in <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>O<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:msup><mml:mi>M<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mn>4.67<\/mml:mn><\/mml:mrow><\/mml:msup><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:msup><mml:mi>&amp;#x03B5;<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> quantum circuit evaluations, where <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>M<\/mml:mi><\/mml:math> denotes the size of the data set and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>&amp;#x03B5;<\/mml:mi><\/mml:math> the solution accuracy compared to the ideal result from exact expectation values, which is only obtainable in theory. We prove under an empirically motivated assumption that the kernelized primal problem can alternatively be solved in <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>O<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mo movablelimits=\"true\" form=\"prefix\">min<\/mml:mo><mml:mo fence=\"false\" stretchy=\"false\">{<\/mml:mo><mml:msup><mml:mi>M<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:msup><mml:mi>&amp;#x03B5;<\/mml:mi><mml:mn>6<\/mml:mn><\/mml:msup><mml:mo>,<\/mml:mo><mml:mspace width=\"thinmathspace\"\/><mml:mn>1<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:msup><mml:mi>&amp;#x03B5;<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mn>10<\/mml:mn><\/mml:mrow><\/mml:msup><mml:mo fence=\"false\" stretchy=\"false\">}<\/mml:mo><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> evaluations by employing a generalization of a known classical algorithm called Pegasos. Accompanying empirical results demonstrate these analytical complexities to be essentially tight. In addition, we investigate a variational approximation to quantum support vector machines and show that their heuristic training achieves considerably better scaling in our experiments.<\/jats:p>","DOI":"10.22331\/q-2024-01-11-1225","type":"journal-article","created":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T14:14:40Z","timestamp":1704982480000},"page":"1225","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":46,"title":["The complexity of quantum support vector machines"],"prefix":"10.22331","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5891-3289","authenticated-orcid":false,"given":"Gian","family":"Gentinetta","sequence":"first","affiliation":[{"name":"Institute of Physics, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"},{"name":"IBM Quantum, IBM Research Europe \u2013 Zurich"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0309-9021","authenticated-orcid":false,"given":"Arne","family":"Thomsen","sequence":"additional","affiliation":[{"name":"Department of Physics, ETH Zurich"},{"name":"IBM Quantum, IBM Research Europe \u2013 Zurich"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9779-8888","authenticated-orcid":false,"given":"David","family":"Sutter","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM Research Europe \u2013 Zurich"}]},{"given":"Stefan","family":"Woerner","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM Research Europe \u2013 Zurich"}]}],"member":"9598","published-online":{"date-parts":[[2024,1,11]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd. Quantum machine learning. Nature, 549(7671):195\u2013202, 2017. DOI: 10.1038\/nature23474.","DOI":"10.1038\/nature23474"},{"key":"1","doi-asserted-by":"publisher","unstructured":"V. Havl\u00ed\u010dek, A. D. C\u00f3rcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567(7747):209\u2013212, 2019. DOI: 10.1038\/s41586-019-0980-2.","DOI":"10.1038\/s41586-019-0980-2"},{"key":"2","doi-asserted-by":"publisher","unstructured":"A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli, and S. Woerner. The power of quantum neural networks. Nature Computational Science, 1(June), 2020. DOI: 10.1038\/s43588-021-00084-1.","DOI":"10.1038\/s43588-021-00084-1"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Y. Liu, S. Arunachalam, and K. Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 2021. DOI: 10.1038\/s41567-021-01287-z.","DOI":"10.1038\/s41567-021-01287-z"},{"key":"4","doi-asserted-by":"publisher","unstructured":"S. Aaronson. Read the fine print. Nature Physics, 11(4):291\u2013293, 2015. DOI: 10.1038\/nphys3272.","DOI":"10.1038\/nphys3272"},{"key":"5","doi-asserted-by":"publisher","unstructured":"E. Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 217\u2013228, New York, NY, USA, 2019. Association for Computing Machinery. DOI: 10.1145\/3313276.3316310.","DOI":"10.1145\/3313276.3316310"},{"key":"6","doi-asserted-by":"publisher","unstructured":"N.-H. Chia, A. Gily\u00e9n, T. Li, H.-H. Lin, E. Tang, and C. Wang. Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning, page 387\u2013400. Association for Computing Machinery, New York, NY, USA, 2020. Available online: https:\/\/doi.org\/10.1145\/3357713.3384314.","DOI":"10.1145\/3357713.3384314"},{"key":"7","unstructured":"T. Li, S. Chakrabarti, and X. Wu. Sublinear quantum algorithms for training linear and kernel-based classifiers. In International Conference on Machine Learning, pages 3815\u20133824. PMLR, 2019."},{"key":"8","doi-asserted-by":"publisher","unstructured":"S. Thanasilp, S. Wang, M. Cerezo, and Z. Holmes. Exponential concentration and untrainability in quantum kernel methods, 2022. DOI: 10.48550\/ARXIV.2208.11060.","DOI":"10.48550\/ARXIV.2208.11060"},{"key":"9","doi-asserted-by":"crossref","unstructured":"S. Shalev-Shwartz and N. Srebro. SVM optimization: Inverse dependence on training set size. Proceedings of the 25th International Conference on Machine Learning, pages 928\u2013935, 2008.","DOI":"10.1145\/1390156.1390273"},{"key":"10","unstructured":"A. Thomsen. Comparing quantum neural networks and quantum support vector machines. Master&apos;s thesis, ETH Zurich, 2021-09-06. DOI: 20.500.11850\/527559."},{"key":"11","doi-asserted-by":"publisher","unstructured":"B. E. Boser, I. M. Guyon, and V. N. Vapnik. A Training Algorithm for Optimal Margin Classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT &apos;92, pages 144\u2013152, New York, NY, USA, 1992. Association for Computing Machinery. DOI: 10.1145\/130385.130401.","DOI":"10.1145\/130385.130401"},{"key":"12","doi-asserted-by":"crossref","unstructured":"C. Cortes and V. Vapnik. Support-vector networks. In Machine Learning, pages 273\u2013297, 1995.","DOI":"10.1007\/BF00994018"},{"key":"13","doi-asserted-by":"crossref","unstructured":"V. N. Vapnik. The Nature of Statistical Learning Theory. Springer Science+Business Media, LLC, 2000.","DOI":"10.1007\/978-1-4757-3264-1"},{"key":"14","unstructured":"F. Pedregosa et al. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12(85):2825\u20132830, 2011. Available online: http:\/\/jmlr.org\/papers\/v12\/pedregosa11a.html."},{"key":"15","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"16","doi-asserted-by":"publisher","unstructured":"S. Shalev-Shwartz, Y. Singer, N. Srebro, and A. Cotter. Pegasos: Primal estimated sub-gradient solver for SVM. Mathematical Programming, 127(1):3\u201330, 2011. DOI: 10.1007\/s10107-010-0420-4.","DOI":"10.1007\/s10107-010-0420-4"},{"key":"17","doi-asserted-by":"publisher","unstructured":"M. D. S. Anis et al. Qiskit: An Open-source Framework for Quantum Computing, 2021. DOI: 10.5281\/zenodo.2573505.","DOI":"10.5281\/zenodo.2573505"},{"key":"18","doi-asserted-by":"publisher","unstructured":"P. Rebentrost, M. Mohseni, and S. Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 113(3):1\u20135, 2014. DOI: 10.1103\/PhysRevLett.113.130503.","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"19","unstructured":"J. K\u00fcbler, S. Buchholz, and B. Sch\u00f6lkopf. The inductive bias of quantum kernels. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 12661\u201312673. Curran Associates, Inc., 2021. Available online: https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2021\/file\/69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf."},{"key":"20","doi-asserted-by":"publisher","unstructured":"V. Heyraud, Z. Li, Z. Denis, A. Le Boit\u00e9, and C. Ciuti. Noisy quantum kernel machines. Phys. Rev. A, 106:052421, 2022. DOI: 10.1103\/PhysRevA.106.052421.","DOI":"10.1103\/PhysRevA.106.052421"},{"key":"21","unstructured":"C. J. C. Burges and C. J. C. Burges. A Tutorial on Support Vector Machines for Pattern Recognition. Data Mining and Knowledge Discovery, 2:121\u2013167, 1998. Available online: https:\/\/www.microsoft.com\/en-us\/research\/publication\/a-tutorial-on-support-vector-machines-for-pattern-recognition\/."},{"key":"22","doi-asserted-by":"publisher","unstructured":"M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 12(1):1791, 2021. DOI: 10.1038\/s41467-021-21728-w.","DOI":"10.1038\/s41467-021-21728-w"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Belis, Vasilis, Gonz\u00e1lez-Castillo, Samuel, Reissel, Christina, Vallecorsa, Sofia, Combarro, El\u00edas F., Dissertori, G\u00fcnther, and Reiter, Florentin. Higgs analysis with quantum classifiers. EPJ Web Conf., 251:03070, 2021. DOI: 10.1051\/epjconf\/202125103070.","DOI":"10.1051\/epjconf\/202125103070"},{"key":"24","doi-asserted-by":"publisher","unstructured":"M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles. Variational quantum algorithms. Nature Reviews Physics, 3(9):625\u2013644, 2021. DOI: 10.1038\/s42254-021-00348-9.","DOI":"10.1038\/s42254-021-00348-9"},{"key":"25","unstructured":"R. McGibborn et al. quadprog: Quadratic programming solver (python). https:\/\/github.com\/quadprog\/quadprog, 2022."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Applied Optimization. Springer, 2004. DOI: 10.1007\/978-1-4419-8853-9.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"27","unstructured":"J. Spall. An Overview of the Simultaneous Perturbation Method for Efficient Optimization. John Hopkins APL Technical Digest, 19(4), pages 482\u2013492, 1998."},{"key":"28","doi-asserted-by":"publisher","unstructured":"G. Gentinetta, A. Thomsen, D. Sutter, and S. Woerner. Code for manuscript ``The complexity of quantum support vector machines\". 2022. DOI: https:\/\/doi.org\/10.5281\/zenodo.6303725.","DOI":"10.5281\/zenodo.6303725"},{"key":"29","doi-asserted-by":"publisher","unstructured":"T. Hubregtsen, D. Wierichs, E. Gil-Fuster, P.-J. H. S. Derks, P. K. Faehrmann, and J. J. Meyer. Training quantum embedding kernels on near-term quantum computers. Phys. Rev. A, 106:042431, 2022. DOI: 10.1103\/PhysRevA.106.042431.","DOI":"10.1103\/PhysRevA.106.042431"},{"key":"30","doi-asserted-by":"publisher","unstructured":"R. Lata\u0142a. Some estimates of norms of random matrices. Proceedings of the American Mathematical Society, 133(5):1273\u20131282, 2005. DOI: 10.1090\/s0002-9939-04-07800-1.","DOI":"10.1090\/s0002-9939-04-07800-1"},{"key":"31","doi-asserted-by":"publisher","unstructured":"R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. Compressed Sensing: Theory and Applications, pages 210\u2013268, 2009. DOI: 10.1017\/CBO9780511794308.006.","DOI":"10.1017\/CBO9780511794308.006"},{"key":"32","doi-asserted-by":"publisher","unstructured":"T. Hofmann, B. Sch\u00f6lkopf, and A. J. Smola. Kernel methods in machine learning. Annals of Statistics, 36(3):1171\u20131220, 2008. DOI: 10.1214\/009053607000000677.","DOI":"10.1214\/009053607000000677"},{"key":"33","doi-asserted-by":"publisher","unstructured":"J. W. Daniel. Stability of the solution of definite quadratic programs. Mathematical Programming, 5(1):41\u201353, 1973. DOI: 10.1007\/BF01580110.","DOI":"10.1007\/BF01580110"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-01-11-1225\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T14:15:29Z","timestamp":1704982529000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-01-11-1225\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,11]]},"references-count":34,"URL":"https:\/\/doi.org\/10.22331\/q-2024-01-11-1225","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,11]]},"article-number":"1225"}}