{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T06:56:32Z","timestamp":1758264992106},"reference-count":39,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T00:00:00Z","timestamp":1602720000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We propose a quantum algorithm for training nonlinear support vector machines (SVM) for feature space learning where classical input data is encoded in the amplitudes of quantum states. Based on the classical SVM-perf algorithm of Joachims \\cite{joachims2006training}, our algorithm has a running time which scales linearly in the number of training examples<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>m<\/mml:mi><\/mml:math>(up to polylogarithmic factors) and applies to the standard soft-margin<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><\/mml:math>-SVM model. In contrast, while classical SVM-perf has demonstrated impressive performance on both linear and nonlinear SVMs, its efficiency is guaranteed only in certain cases: it achieves linear<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>m<\/mml:mi><\/mml:math>scaling only for linear SVMs, where classification is performed in the original input data space, or for the special cases of low-rank or shift-invariant kernels. Similarly, previously proposed quantum algorithms either have super-linear scaling in<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>m<\/mml:mi><\/mml:math>, or else apply to different SVM models such as the hard-margin or least squares<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msub><\/mml:math>-SVM which lack certain desirable properties of the soft-margin<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><\/mml:math>-SVM model. We classically simulate our algorithm and give evidence that it can perform well in practice, and not only for asymptotically large data sets.<\/jats:p>","DOI":"10.22331\/q-2020-10-15-342","type":"journal-article","created":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T13:55:51Z","timestamp":1602770151000},"page":"342","source":"Crossref","is-referenced-by-count":5,"title":["A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time"],"prefix":"10.22331","volume":"4","author":[{"given":"Jonathan","family":"Allcock","sequence":"first","affiliation":[{"name":"Tencent Quantum Laboratory"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chang-Yu","family":"Hsieh","sequence":"additional","affiliation":[{"name":"Tencent Quantum Laboratory"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2020,10,15]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Thorsten Joachims. Training linear SVMs in linear time. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 217\u2013226. ACM, 2006. 10.1145\/1150402.1150429.","DOI":"10.1145\/1150402.1150429"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Bernhard E Boser, Isabelle M Guyon, and Vladimir N Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop on Computational learning theory, pages 144\u2013152. ACM, 1992. 10.1145\/130385.130401.","DOI":"10.1145\/130385.130401"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20 (3): 273\u2013297, 1995. 10.1023\/A:1022627411411.","DOI":"10.1023\/A:1022627411411"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Christopher JC Burges. A tutorial on support vector machines for pattern recognition. Data mining and knowledge discovery, 2 (2): 121\u2013167, 1998. 10.1023\/A:1009715923555.","DOI":"10.1023\/A:1009715923555"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Michael C Ferris and Todd S Munson. Interior-point methods for massive support vector machines. SIAM Journal on Optimization, 13 (3): 783\u2013804, 2002. 10.1137\/S1052623400374379.","DOI":"10.1137\/S1052623400374379"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Olvi L Mangasarian and David R Musicant. Lagrangian support vector machines. Journal of Machine Learning Research, 1 (Mar): 161\u2013177, 2001. 10.1162\/15324430152748218.","DOI":"10.1162\/15324430152748218"},{"key":"6","unstructured":"S Sathiya Keerthi and Dennis DeCoste. A modified finite Newton method for fast solution of large scale linear SVMs. Journal of Machine Learning Research, 6 (Mar): 341\u2013361, 2005."},{"key":"7","doi-asserted-by":"publisher","unstructured":"Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter. Pegasos: Primal Estimated sub-GrAdient SOlver for SVM. Mathematical programming, 127 (1): 3\u201330, 2011. 10.1145\/1273496.1273598.","DOI":"10.1145\/1273496.1273598"},{"key":"8","doi-asserted-by":"crossref","unstructured":"Bernhard Scholkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2001.","DOI":"10.7551\/mitpress\/4175.001.0001"},{"key":"9","unstructured":"Christopher KI Williams and Matthias Seeger. Using the Nystr\u00f6m method to speed up kernel machines. In Advances in Neural Information Processing Systems, pages 682\u2013688, 2001."},{"key":"10","unstructured":"Shai Fine and Katya Scheinberg. Efficient SVM training using low-rank kernel representations. Journal of Machine Learning Research, 2 (Dec): 243\u2013264, 2001."},{"key":"11","unstructured":"Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, pages 1177\u20131184, 2008."},{"key":"12","unstructured":"Thorsten Joachims. Making large-scale SVM learning practical. In Advances in Kernel Methods-Support Vector Learning. MIT-press, 1999."},{"key":"13","doi-asserted-by":"crossref","unstructured":"John C Platt. Fast training of support vector machines using sequential minimal optimization. MIT press, 1999.","DOI":"10.7551\/mitpress\/1130.003.0016"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2 (3): 27, 2011. 10.1145\/1961189.1961199.","DOI":"10.1145\/1961189.1961199"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Ronan Collobert and Samy Bengio. SVMTorch: Support vector machines for large-scale regression problems. Journal of Machine Learning Research, 1 (Feb): 143\u2013160, 2001. 10.1162\/15324430152733142.","DOI":"10.1162\/15324430152733142"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Thorsten Joachims and Chun-Nam John Yu. Sparse kernel SVMs via cutting-plane training. Machine Learning, 76 (2-3): 179\u2013193, 2009. 10.1007\/s10994-009-5126-6.","DOI":"10.1007\/s10994-009-5126-6"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 113 (13): 130503, 2014. 10.1103\/PhysRevLett.113.130503.","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"18","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 (7747): 209\u2013212, 2019. 10.1038\/s41586-019-0980-2.","DOI":"10.1038\/s41586-019-0980-2"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Maria Schuld and Nathan Killoran. Quantum machine learning in feature hilbert spaces. Physical Review Letters, 122 (4): 040504, 2019. 10.1103\/PhysRevLett.122.040504.","DOI":"10.1103\/PhysRevLett.122.040504"},{"key":"20","unstructured":"Iordanis Kerenidis, Anupam Prakash, and D\u00e1niel Szil\u00e1gyi. Quantum algorithms for second-order cone programming and support vector machines. arXiv preprint arXiv:1908.06720, 2019."},{"key":"21","unstructured":"Tomasz Arodz and Seyran Saeedi. Quantum sparse support vector machines. arXiv preprint arXiv:1902.01879, 2019."},{"key":"22","unstructured":"Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear quantum algorithms for training linear and kernel-based classifiers. In Proceedings of the 36th International Conference on Machine Learning. PMLR, 2019."},{"key":"23","doi-asserted-by":"publisher","unstructured":"Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical Review Letters, 100 (16): 160501, 2008. 10.1103\/PhysRevLett.100.160501.","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"24","unstructured":"Anupam Prakash. Quantum algorithms for linear algebra and machine learning. PhD thesis, UC Berkeley, 2014."},{"key":"25","doi-asserted-by":"publisher","unstructured":"Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 217\u2013228, 2019. 10.1145\/3313276.3316310.","DOI":"10.1145\/3313276.3316310"},{"key":"26","unstructured":"Ewin Tang. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. arXiv preprint arXiv:1811.00414, 2018."},{"key":"27","unstructured":"Andr\u00e1s Gily\u00e9n, Seth Lloyd, and Ewin Tang. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv preprint arXiv:1811.04909, 2018."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd. Quantum-inspired algorithms in practice. Quantum, 4: 307, 2020. 10.22331\/q-2020-08-13-307.","DOI":"10.22331\/q-2020-08-13-307"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. 10.1017\/CBO9780511804441.","DOI":"10.1017\/CBO9780511804441"},{"key":"30","unstructured":"Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, and Yasemin Altun. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6 (Sep): 1453\u20131484, 2005."},{"key":"31","doi-asserted-by":"publisher","unstructured":"Jonathan Allcock, Chang-Yu Hsieh, Iordanis Kerenidis, and Shengyu Zhang. Quantum algorithms for feedforward neural networks. ACM Transactions on Quantum Computing, 1 (1), 2020. 10.1145\/3411466.","DOI":"10.1145\/3411466"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. 10.4230\/LIPIcs.ITCS.2017.49.","DOI":"10.4230\/LIPIcs.ITCS.2017.49"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Mario Motta, Chong Sun, Adrian TK Tan, Matthew J O\u2019Rourke, Erika Ye, Austin J Minnich, Fernando GSL Brand\u00e3o, and Garnet Kin-Lic Chan. Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nature Physics, 16 (2): 205\u2013210, 2020. 10.1038\/s41567-019-0704-4.","DOI":"10.1038\/s41567-019-0704-4"},{"key":"34","unstructured":"Chang-Yu Hsieh, Qiming Sun, Shengyu Zhang, and Chee Kong Lee. Unitary-coupled restricted boltzmann machine ansatz for quantum simulations. https:\/\/arxiv.org\/abs\/1912.02988, 2019."},{"key":"35","doi-asserted-by":"publisher","unstructured":"Jonathan Romero, Jonathan P Olson, and Alan Aspuru-Guzik. Quantum autoencoders for efficient compression of quantum data. Quantum Science and Technology, 2 (4): 045001, 2017. 10.1088\/2058-9565\/aa8072.","DOI":"10.1088\/2058-9565\/aa8072"},{"key":"36","unstructured":"Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term processors. arXiv preprint arXiv:1802.06002, 2018."},{"key":"37","unstructured":"Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Isaac, and Nathan Killoran. Quantum embeddings for machine learning. arXiv preprint arXiv:2001.03622, 2020."},{"key":"38","doi-asserted-by":"crossref","unstructured":"Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53\u201374, 2002.","DOI":"10.1090\/conm\/305\/05215"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-10-15-342\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T23:21:48Z","timestamp":1723764108000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-10-15-342\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,15]]},"references-count":39,"URL":"https:\/\/doi.org\/10.22331\/q-2020-10-15-342","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2020,10,15]]},"article-number":"342"}}