Towards understanding the power of quantum kernels in the NISQ era

Xinbiao Wang1,2, Yuxuan Du2, Yong Luo1, and Dacheng Tao2

1Institute of Artificial Intelligence, School of Computer Science, Wuhan University
2JD Explore Academy

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


A key problem in the field of quantum computing is understanding whether quantum machine learning (QML) models implemented on noisy intermediate-scale quantum (NISQ) machines can achieve quantum advantages. Recently, Huang et al. [Nat Commun 12, 2631] partially answered this question by the lens of quantum kernel learning. Namely, they exhibited that quantum kernels can learn specific datasets with lower generalization error over the optimal classical kernel methods. However, most of their results are established on the ideal setting and ignore the caveats of near-term quantum machines. To this end, a crucial open question is: does the power of quantum kernels still hold under the NISQ setting? In this study, we fill this knowledge gap by exploiting the power of quantum kernels when the quantum system noise and sample error are considered. Concretely, we first prove that the advantage of quantum kernels is vanished for large size of datasets, few number of measurements, and large system noise. With the aim of preserving the superiority of quantum kernels in the NISQ era, we further devise an effective method via indefinite kernel learning. Numerical simulations accord with our theoretical results. Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.

► BibTeX data

► References

[1] Shun-ichi Amari and Si Wu. Improving support vector machine classifiers by modifying kernel functions. Neural Networks, 12 (6): 783–789, 1999. https:/​/​​10.1016/​s0893-6080(99)00032-5.

[2] Sarabjot S Anand, Bryan W Scotney, Mee G Tan, Sally I McClean, David A Bell, John G Hughes, and Ian C Magill. Designing a kernel for data mining. IEEE Expert, 12 (2): 65–74, 1997. https:/​/​​10.1109/​64.585106.

[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 (7779): 505–510, 2019. https:/​/​​10.1038/​s41586-019-1666-5.

[4] Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning. arXiv preprint arXiv:1703.06476, 2017.

[5] Karol Bartkiewicz, Clemens Gneiting, Antonín Černoch, Kateřina Jiráková, Karel Lemr, and Franco Nori. Experimental kernel-based quantum machine learning in finite feature space. Scientific Reports, 10 (1): 1–9, 2020. https:/​/​​10.1038/​s41598-020-68911-5.

[6] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Science and Technology, 4 (4): 043001, 2019. https:/​/​​10.1088/​2058-9565/​ab4eb5.

[7] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549 (7671): 195, 2017. https:/​/​​10.1038/​nature23474. URL https:/​/​​articles/​nature23474.

[8] Christopher M Bishop. Pattern recognition and machine learning. springer, 2006. https:/​/​​10.1117/​1.2819119.

[9] 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–152, 1992. https:/​/​​10.1145/​130385.130401.

[10] 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, pages 1–20, 2021. https:/​/​​10.1038/​s42254-021-00348-9.

[11] Yihua Chen, Eric K Garcia, Maya R Gupta, Ali Rahimi, and Luca Cazzanti. Similarity-based classification: Concepts and algorithms. Journal of Machine Learning Research, 10 (3), 2009.

[12] Piotr Czarnik, Andrew Arrasmith, Patrick J Coles, and Lukasz Cincio. Error mitigation with clifford quantum-circuit data. arXiv preprint arXiv:2005.10189, 2020.

[13] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao. Expressive power of parametrized quantum circuits. Phys. Rev. Research, 2: 033125, Jul 2020a. 10.1103/​PhysRevResearch.2.033125. URL https:/​/​​doi/​10.1103/​PhysRevResearch.2.033125.

[14] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao. On the learnability of quantum neural networks. arXiv preprint arXiv:2007.12369, 2020b.

[15] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao. Quantum differentially private sparse regression learning. arXiv preprint arXiv:2007.11921, 2020c.

[16] Yuxuan Du, Tao Huang, Shan You, Min-Hsiu Hsieh, and Dacheng Tao. Quantum circuit architecture search: error mitigation and trainability enhancement for variational quantum solvers. arXiv preprint arXiv:2010.10217, 2020d.

[17] Suguru Endo, Simon C Benjamin, and Ying Li. Practical quantum error mitigation for near-future applications. Physical Review X, 8 (3): 031027, 2018. https:/​/​​10.1103/​PhysRevX.8.031027.

[18] Marc G Genton. Classes of kernels for machine learning: a statistics perspective. Journal of machine learning research, 2 (Dec): 299–312, 2001.

[19] Thore Graepel, Ralf Herbrich, Peter Bollmann-Sdorra, and Klaus Obermayer. Classification on pairwise proximity data. Advances in neural information processing systems, pages 438–444, 1999.

[20] 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 (7747): 209, 2019. https:/​/​​10.1038/​s41586-019-0980-2.

[21] Nicholas J Higham. Computing a nearest symmetric positive semidefinite matrix. Linear algebra and its applications, 103: 103–118, 1988. https:/​/​​10.1016/​0024-3795(88)90223-6.

[22] Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola. Kernel methods in machine learning. The annals of statistics, pages 1171–1220, 2008. https:/​/​​10.1214/​009053607000000677.

[23] He-Liang Huang, Yuxuan Du, Ming Gong, Youwei Zhao, Yulin Wu, Chaoyue Wang, Shaowei Li, Futian Liang, Jin Lin, Yu Xu, et al. Experimental quantum generative adversarial networks for image generation. arXiv preprint arXiv:2010.06201, 2020.

[24] 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 (1): 1–9, 2021. https:/​/​​10.1038/​s41467-021-22539-9.

[25] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: convergence and generalization in neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 8580–8589, 2018.

[26] Ian T Jolliffe. Principal components in regression analysis. In Principal component analysis, pages 129–155. Springer, 1986. https:/​/​​10.1007/​978-1-4757-1904-8_8.

[27] Ashish Kapoor, Nathan Wiebe, and Krysta Svore. Quantum perceptron models. In Advances in Neural Information Processing Systems, pages 3999–4007, 2016. URL http:/​/​​paper/​6401-quantum-perceptron-models.

[28] Reshma Khemchandani, Suresh Chandra, et al. Twin support vector machines for pattern classification. IEEE Transactions on pattern analysis and machine intelligence, 29 (5): 905–910, 2007. https:/​/​​10.1109/​tpami.2007.1068.

[29] Takeru Kusumoto, Kosuke Mitarai, Keisuke Fujii, Masahiro Kitagawa, and Makoto Negoro. Experimental quantum kernel machine learning with nuclear spins in a solid. arXiv preprint arXiv:1911.12021, 2019.

[30] Julian Laub and Klaus-Robert Müller. Feature discovery in non-metric pairwise data. The Journal of Machine Learning Research, 5: 801–818, 2004.

[31] Julian Laub, Volker Roth, Joachim M Buhmann, and Klaus-Robert Müller. On the information and representation of non-euclidean pairwise data. Pattern Recognition, 39 (10): 1815–1826, 2006. https:/​/​​10.1016/​j.patcog.2006.04.016.

[32] Junde Li, Rasit Topaloglu, and Swaroop Ghosh. Quantum generative models for small molecule drug discovery. arXiv preprint arXiv:2101.03438, 2021.

[33] Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear quantum algorithms for training linear and kernel-based classifiers. In International Conference on Machine Learning, pages 3815–3824, 2019.

[34] Ying Li and Simon C Benjamin. Efficient variational quantum simulator incorporating active error minimization. Physical Review X, 7 (2): 021050, 2017. https:/​/​​10.1103/​PhysRevX.7.021050.

[35] Ronny Luss and Alexandre d’Aspremont. Support vector machine classification with indefinite kernels. Mathematical Programming Computation, 1 (2): 97–118, 2009. https:/​/​​10.1007/​s12532-009-0005-5.

[36] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.

[37] Cheng Soon Ong, Xavier Mary, Stéphane Canu, and Alexander J Smola. Learning with non-positive kernels. In Proceedings of the twenty-first international conference on Machine learning, page 81, 2004. https:/​/​​10.1145/​1015330.1015443.

[38] Elzbieta Pekalska, Pavel Paclik, and Robert PW Duin. A generalized kernel approach to dissimilarity-based classification. Journal of machine learning research, 2 (Dec): 175–211, 2001.

[39] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2: 79, 2018. https:/​/​​10.22331/​q-2018-08-06-79.

[40] Volker Roth, Julian Laub, Motoaki Kawanabe, and Joachim M Buhmann. Optimal cluster preserving embedding of nonmetric proximity data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25 (12): 1540–1551, 2003. https:/​/​​10.1109/​TPAMI.2003.1251147.

[41] Manuel S Rudolph, Ntwali Toussaint Bashige, Amara Katabarwa, Sonika Johr, Borja Peropadre, and Alejandro Perdomo-Ortiz. Generation of high resolution handwritten digits with an ion-trap quantum computer. arXiv preprint arXiv:2012.03924, 2020.

[42] Maria Schuld. Quantum machine learning models are kernel methods. arXiv preprint arXiv:2101.11020, 2021.

[43] Maria Schuld and Nathan Killoran. Quantum machine learning in feature hilbert spaces. Physical review letters, 122 (4): 040504, 2019. https:/​/​​10.1103/​PhysRevLett.122.040504.

[44] Thomas Arthur Leck Sewell, Magnus O Myreen, and Gerwin Klein. Translation validation for a verified os kernel. In Proceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation, pages 471–482, 2013. https:/​/​​10.1145/​2499370.2462183.

[45] John Shawe-Taylor, Nello Cristianini, et al. Kernel methods for pattern analysis. Cambridge university press, 2004. https:/​/​​10.1017/​CBO9780511809682.

[46] Armands Strikis, Dayue Qin, Yanzhu Chen, Simon C Benjamin, and Ying Li. Learning-based quantum error mitigation. arXiv preprint arXiv:2005.07601, 2020.

[47] Hiroyuki Takeda, Sina Farsiu, and Peyman Milanfar. Kernel regression for image processing and reconstruction. IEEE Transactions on image processing, 16 (2): 349–366, 2007. https:/​/​​10.1109/​TIP.2006.888330.

[48] Kristan Temme, Sergey Bravyi, and Jay M Gambetta. Error mitigation for short-depth quantum circuits. Physical review letters, 119 (18): 180509, 2017. https:/​/​​10.1103/​PhysRevLett.119.180509.

[49] Vladimir Vapnik. Principles of risk minimization for learning theory. In Advances in neural information processing systems, pages 831–838, 1992.

[50] Peter Wittek. Quantum machine learning: what quantum computing means to data mining. Academic Press, 2014. https:/​/​​10.1016/​C2013-0-19170-2.

[51] Gang Wu, Edward Y Chang, and Zhihua Zhang. An analysis of transformation on non-positive semidefinite similarity matrix for kernel machines. In Proceedings of the 22nd International Conference on Machine Learning, volume 8. Citeseer, 2005.

[52] Dan-Bo Zhang, Shi-Liang Zhu, and Z. D. Wang. Protocol for implementing quantum nonparametric learning with trapped ions. Phys. Rev. Lett., 124: 010506, Jan 2020. 10.1103/​PhysRevLett.124.010506. URL https:/​/​​doi/​10.1103/​PhysRevLett.124.010506.

Cited by

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

[2] Thomas Hubregtsen, David Wierichs, Elies Gil-Fuster, Peter-Jan H. S. Derks, Paul K. Faehrmann, and Johannes Jakob Meyer, "Training Quantum Embedding Kernels on Near-Term Quantum Computers", arXiv:2105.02276.

[3] Yang Qian, Xinbiao Wang, Yuxuan Du, Xingyao Wu, and Dacheng Tao, "The dilemma of quantum neural networks", arXiv:2106.04975.

[4] Yuxuan Du and Dacheng Tao, "On exploring practical potentials of quantum auto-encoder with advantages", arXiv:2106.15432.

[5] Teresa Sancho-Lorente, Juan Román-Roche, and David Zueco, "Quantum kernels to learn the phases of quantum matter", arXiv:2109.02686.

[6] 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", arXiv:2111.05292.

[7] Beng Yee Gan, Daniel Leykam, and Dimitris G. Angelakis, "Fock State-enhanced Expressivity of Quantum Machine Learning Models", arXiv:2107.05224.

[8] Yuxuan Du, Yang Qian, and Dacheng Tao, "Accelerating variational quantum algorithms with multiple quantum processors", arXiv:2106.12819.

[9] Yusen Wu, Bujiao Wu, Jingbo Wang, and Xiao Yuan, "Provable Advantage in Quantum Phase Learning via Quantum Kernel Alphatron", arXiv:2111.07553.

[10] Benjamin A. Cordier, Nicolas P. D. Sawaya, Gian G. Guerreschi, and Shannon K. McWeeney, "Biology and medicine in the landscape of quantum advantages", arXiv:2112.00760.

[11] Marco Pistoia, Syed Farhan Ahmad, Akshay Ajagekar, Alexander Buts, Shouvanik Chakrabarti, Dylan Herman, Shaohan Hu, Andrew Jena, Pierre Minssen, Pradeep Niroula, Arthur Rattew, Yue Sun, and Romina Yalovetzky, "Quantum Machine Learning for Finance", arXiv:2109.04298.

The above citations are from Crossref's cited-by service (last updated successfully 2021-12-08 19:17:58) and SAO/NASA ADS (last updated successfully 2021-12-08 19:17:59). The list may be incomplete as not all publishers provide suitable and complete citation data.