{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T21:43:20Z","timestamp":1757540600623,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T00:00:00Z","timestamp":1660521600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T00:00:00Z","timestamp":1660521600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigated the potential application of quantum computing using the Kronecker kernel to pairwise classification and have devised a way to apply the Harrow-Hassidim-Lloyd (HHL)-based quantum support vector machine algorithm. Pairwise classification can be used to predict relationships among data and is used for problems such as link prediction and chemical interaction prediction. However, in pairwise classification using a Kronecker kernel, it is very costly to calculate the Kronecker product of the kernel matrices when there is a large amount of data. We found that the Kronecker product of kernel matrices can be represented more efficiently in time and space in quantum computing than that in classical computing. We also found that a pairwise classifier can be effectively trained by applying the HHL-based quantum support vector machine algorithm to the Kronecker kernel matrix. In an experiment comparing a classical algorithm with a quantum support vector machine with a Kronecker kernel run on a quantum computing simulator, the misclassification rate of the latter was almost the same as that of the former for the same pairwise classification problem in some cases. This indicates that a quantum support vector machine with a Kronecker kernel algorithm can achieve accuracy equivalent to that of the classical algorithm more efficiently and scalably. This finding paves the way for applying quantum machine learning to predicting relationships in large-scale data.<\/jats:p>","DOI":"10.1007\/s42484-022-00082-0","type":"journal-article","created":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T10:02:59Z","timestamp":1660557779000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Pairwise classification using quantum support vector machine with Kronecker kernel"],"prefix":"10.1007","volume":"4","author":[{"given":"Taisei","family":"Nohara","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8124-3578","authenticated-orcid":false,"given":"Satoshi","family":"Oyama","sequence":"additional","affiliation":[]},{"given":"Itsuki","family":"Noda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,15]]},"reference":[{"key":"82_CR1","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute F, Arya K, Babbush R et al (2019) Quantum supremacy using a programmable superconducting processor. Nature 574:505\u2013510. https:\/\/doi.org\/10.1038\/s41586-019-1666-5","journal-title":"Nature"},{"key":"82_CR2","doi-asserted-by":"publisher","unstructured":"Ben-Hur A, Noble WS\u00a0(2005) Kernel methods for predicting protein-protein interactions. JBioinformatics 21:38\u201346. https:\/\/doi.org\/10.1093\/bioinformatics\/bti1016","DOI":"10.1093\/bioinformatics\/bti1016"},{"key":"82_CR3","volume-title":"Pattern recognition and machine learning","author":"CM Bishop","year":"2006","unstructured":"Bishop CM (2006) Pattern recognition and machine learning. Springer, Singapore"},{"key":"82_CR4","doi-asserted-by":"publisher","first-page":"1920","DOI":"10.1137\/16M1087072","volume":"46","author":"AM Childs","year":"2017","unstructured":"Childs AM, Kothari R, Somma RD (2017) Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing 46:1920\u20131950. https:\/\/doi.org\/10.1137\/16M1087072","journal-title":"SIAM Journal on Computing"},{"key":"82_CR5","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/BF00994018","volume":"20","author":"C Cortes","year":"1995","unstructured":"Cortes C, Vapnik V (1995) Support-vector networks. Machine Learning 20:273\u2013297. https:\/\/doi.org\/10.1007\/BF00994018","journal-title":"Machine Learning"},{"key":"82_CR6","unstructured":"Dervovic D, Herbster M, Mountney P, et al (2018) Quantum linear systems algorithms: a primer. Preprint at https:\/\/arxiv.org\/abs\/1802.08227"},{"key":"82_CR7","volume-title":"The master algorithm: How the quest for the ultimate learning machine will remake our world","author":"P Domingos","year":"2015","unstructured":"Domingos P (2015) The master algorithm: How the quest for the ultimate learning machine will remake our world. Basic Books Inc, New York"},{"issue":"052","key":"82_CR8","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1103\/PhysRevA.78.052310","volume":"78","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti V, Lloyd S, Maccone L (2008) Architectures for a quantum random access memory. Phys Rev A 78(052):310. https:\/\/doi.org\/10.1103\/PhysRevA.78.052310","journal-title":"Phys Rev A"},{"key":"82_CR9","doi-asserted-by":"publisher","unstructured":"Grover LK (1996) A fast quantum mechanical algorithm for database search. In: Proceedings of the twenty-eighth annual ACM symposium on theory of computing. Philadelphia, Pennsylvania, USA. pp 212\u2013219. https:\/\/doi.org\/10.1145\/237814.237866","DOI":"10.1145\/237814.237866"},{"issue":"150","key":"82_CR10","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"AW Harrow","year":"2009","unstructured":"Harrow AW, Hassidim A, Lloyd S (2009) Quantum algorithm for linear systems of equations. Phys Rev Lett 103(150):502. https:\/\/doi.org\/10.1103\/PhysRevLett.103.150502","journal-title":"Phys Rev Lett"},{"key":"82_CR11","doi-asserted-by":"publisher","first-page":"409","DOI":"10.6028\/jres.049.044","volume":"49","author":"MR Hestenes","year":"1952","unstructured":"Hestenes MR, Stiefel E (1952) Methods of conjugate gradients for solving linear systems. Journal of research of the National Bureau of Standards 49:409\u2013436","journal-title":"Journal of research of the National Bureau of Standards"},{"key":"82_CR12","unstructured":"Jacot A, Gabriel F, Hongler C (2018) Neural tangent kernel: Convergence and generalization in neural networks. In: Bengio S, Wallach H, Larochelle H et al (eds) Advances in Neural Information Processing Systems, vol 31. Curran Associates Inc"},{"key":"82_CR13","doi-asserted-by":"publisher","unstructured":"Kashima H, Oyama S, Yamanishi Y\u00a0et al (2010) Cartesian kernel: An efficient alternative to the pairwise kernel. IEICE Transactions on Information and Systems E93.D:2672\u20132679. https:\/\/doi.org\/10.1587\/transinf.E93.D.2672","DOI":"10.1587\/transinf.E93.D.2672"},{"key":"82_CR14","doi-asserted-by":"publisher","unstructured":"Kay A (2019) Quantikz. https:\/\/doi.org\/10.17637\/RH.7000520, tutorial is in https:\/\/arxiv.org\/abs\/1809.03842","DOI":"10.17637\/RH.7000520"},{"issue":"140","key":"82_CR15","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1103\/PhysRevLett.114.140504","volume":"114","author":"Z Li","year":"2015","unstructured":"Li Z, Liu X, Xu N et al (2015) Experimental realization of a quantum support vector machine. Physical Review Letters 114(140):504. https:\/\/doi.org\/10.1103\/PhysRevLett.114.140504","journal-title":"Physical Review Letters"},{"key":"82_CR16","doi-asserted-by":"crossref","unstructured":"Liu YA, Liu XL, Li FN, et al (2021) Closing the \u201cquantum supremacy\u201d gap: Achieving real-time simulation of a random quantum circuit using a new sunway supercomputer. In: Proceedings of the international conference for high performance computing, networking, storage and analysis. Association for Computing Machinery, New York, NY, USA","DOI":"10.1145\/3458817.3487399"},{"key":"82_CR17","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1038\/nphys3029","volume":"10","author":"S Lloyd","year":"2014","unstructured":"Lloyd S, Mohseni M, Rebentrost P (2014) Quantum principal component analysis. Nature physics 10:631\u2013633. https:\/\/doi.org\/10.1038\/nphys3029","journal-title":"Nature physics"},{"key":"82_CR18","unstructured":"Nielsen MA, Chuang IL (2010) Quantum computation and quantum information: 10th Anniversary Edition. Cambridge University Press, Cambridge"},{"key":"82_CR19","doi-asserted-by":"publisher","unstructured":"Oyama S, Manning CD (2004) Using feature conjunctions across examples for learning pairwise classifiers. https:\/\/doi.org\/10.1007\/978-3-540-30115-8_31, paper presented at the 15th European Conference on Machine Learning(ECML), 322\u2013333\u00a0","DOI":"10.1007\/978-3-540-30115-8_31"},{"issue":"130","key":"82_CR20","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1103\/physrevlett.113.130503","volume":"113","author":"P Rebentrost","year":"2014","unstructured":"Rebentrost P, Mohseni M, Lloyd S (2014) Quantum support vector machine for big data classification. Physical Review Letters 113(130):503. https:\/\/doi.org\/10.1103\/physrevlett.113.130503","journal-title":"Physical Review Letters"},{"key":"82_CR21","doi-asserted-by":"crossref","unstructured":"Sch\u00f6lkopf B, Smola AJ\u00a0(2002) Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press, Cambridge, MA","DOI":"10.7551\/mitpress\/4175.001.0001"},{"key":"82_CR22","doi-asserted-by":"publisher","unstructured":"Sheikh AS, Guigour\u00e8s R, Koriagin E, et al (2019) A deep learning system for predicting size and fit in fashion e-commerce. In: Proceedings of the 13th ACM conference on recommender systems. Association for Computing Machinery, Copenhagen, Denmark, pp 110\u2013118. https:\/\/doi.org\/10.1145\/3298689.3347006","DOI":"10.1145\/3298689.3347006"},{"key":"82_CR23","doi-asserted-by":"crossref","unstructured":"Shor PW (1994) Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th annual symposium on foundations of computer science. pp 124\u2013134","DOI":"10.1109\/SFCS.1994.365700"},{"key":"82_CR24","doi-asserted-by":"publisher","first-page":"5505","DOI":"10.1038\/s41467-020-19267-x","volume":"11","author":"S Stocker","year":"2020","unstructured":"Stocker S, Cs\u00e1nyi G, Reuter K et al (2020) Machine learning in chemical reaction space. Nature Communications 11:5505. https:\/\/doi.org\/10.1038\/s41467-020-19267-x","journal-title":"Nature Communications"},{"key":"82_CR25","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1023\/A:1018628609742","volume":"9","author":"JAK Suykens","year":"1999","unstructured":"Suykens JAK, Vandewalle J (1999) Least squares support vector machine classifiers. Neural Processing Letters 9:293\u2013300. https:\/\/doi.org\/10.1023\/A:1018628609742","journal-title":"Neural Processing Letters"},{"key":"82_CR26","unstructured":"Yang J, Awan AJ, Vall-Llosera G (2019) Support vector machines on noisy intermediate scale quantum computers. Preprint at http:\/\/arxiv.org\/abs\/1909.11988"},{"key":"82_CR27","doi-asserted-by":"publisher","first-page":"477","DOI":"10.2197\/ipsjjip.25.477","volume":"25","author":"S Yokoi","year":"2017","unstructured":"Yokoi S, Kajino H, Kashima H (2017) Link prediction in sparse networks by incidence matrix factorization. Journal of Information Processing 25:477\u2013485. https:\/\/doi.org\/10.2197\/ipsjjip.25.477","journal-title":"Journal of Information Processing"},{"issue":"052","key":"82_CR28","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1103\/PhysRevA.99.052331","volume":"99","author":"Z Zhao","year":"2019","unstructured":"Zhao Z, Fitzsimons JK, Fitzsimons JF (2019) Quantum-assisted gaussian process regression. Phys Rev A 99(052):331. https:\/\/doi.org\/10.1103\/PhysRevA.99.052331","journal-title":"Phys Rev A"},{"key":"82_CR29","doi-asserted-by":"publisher","first-page":"1460","DOI":"10.1126\/science.abe8770","volume":"370","author":"HS Zhong","year":"2020","unstructured":"Zhong HS, Wang H, Deng YH et al (2020) Quantum computational advantage using photons. Science 370:1460\u20131463. https:\/\/doi.org\/10.1126\/science.abe8770","journal-title":"Science"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-022-00082-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-022-00082-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-022-00082-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T19:11:02Z","timestamp":1727809862000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-022-00082-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,15]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["82"],"URL":"https:\/\/doi.org\/10.1007\/s42484-022-00082-0","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"type":"print","value":"2524-4906"},{"type":"electronic","value":"2524-4914"}],"subject":[],"published":{"date-parts":[[2022,8,15]]},"assertion":[{"value":"1 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"22"}}