Abstract
K-nearest neighbor classification algorithm is one of the most basic algorithms in machine learning, which determines the sample’s category by the similarity between samples. In this paper, we propose a quantum K-nearest neighbor classification algorithm with the Hamming distance. In this algorithm, quantum computation is utilized to obtain the Hamming distance in parallel at first. Then, a core sub-algorithm for searching the minimum of unordered integer sequence is presented to find out the minimum distance. Based on these two sub-algorithms, the whole quantum frame of K-nearest neighbor classification algorithm is presented. At last, it is shown that the proposed algorithm can achieve a significant speedup by analyzing its time complexity briefly.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., Lloyd, S.: Quantum machine learning. Nature 549, 195 (2017)
Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009)
Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum principal component analysis. Nat. Phys. 10(9), 108 (2014)
Yu, C.H., Gao, F., Lin, S., Wang, J.B.: Quantum data compression by principal component analysis. Quantum Inf. Process. 18, 249 (2019)
Duan, B.J., Yuan, J.B., Li, D.: Quantum algorithm and quantum circuit for A-optimal projection: dimensionality reduction. Phys. Rev. A 99, 032311 (2019)
Wang, G.: Quantum algorithm for linear regression. Phys. Rev. A 96, 012335 (2017)
Yu, C.H., Gao, F., Wen, Q.Y.: Quantum algorithm for ridge regression, ar**v:1707.09524 (2017)
Yu, C.H., Gao, F., Wang, Q.L., Wen, Q.Y.: Quantum algorithm for association rules mining. Phys. Rev. A 94, 042311 (2016)
Lu, S., Braunstein, S.L.: Quantum decision tree classifier. Quantum Inf. Process. 13, 757 (2014)
Rebentrost, P., Mohseni, M., Lloyd, S.: Quantum support vector machine for big data classification. Phys. Rev. Lett. 113, 130503 (2014)
Duan, B., Yuan, J., Liu, Y., Li, D.: Quantum algorithm for support matrix machines. Phys. Rev. A 96, 032301 (2017)
Li, Z., Liu, X., Xu, N., Du, J.: Experimental realization of a quantum support vector machine. Phys. Rev. Lett. 114, 140504 (2015)
Santucci, E., Sergioli, G.: Classification problem in a quantum framework. In: Khrennikov, A., Toni, B. (eds.) Quantum Foundations Probability and Information, pp. 215–228. Springer, Berlin (2018)
Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum algorithms for supervised and unsupervised machine learning (2013). ar**v:1307.0411
Wiebe, N., Kapoor, A., Svore, K.: Quantum nearest neighbor algorithms for machine learning, (2014). ar**v:1401.2142
Ruan, Y., Xue, X.L., Liu, H., Tan, J., Li, X.: Quantum algorithm for K-nearest neighbors classification based on the metric of Hamming distance. Int. J. Theor. Phys. 56, 3496 (2017)
Dang, Y.J., Jiang, N., Hu, H., Ji, Z.X., Zhang, W.Y.: Image classification based on quantum K-Nearest-Neighbor algorithm. Quantum Inf. Process. 17, 239 (2018)
Cai, X.D., Wu, D., Su, Z.E., Chen, M.C., Wang, X.L., Li, L., Liu, N.L., Lu, C.Y., Pan, J.W.: Entanglement-based quantum machine learning. Phys. Rev. Lett. 114, 110504 (2015)
Guo, G.D., Wang, H., Bell, D., Greer, K.: Using kNN model for automatic text categorization. Soft. Comput. 10(5), 423 (2006)
Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett. 87, 167902 (2001)
Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325 (1997)
Dürr, C., Høyer, P.: A quantum algorithm for finding the minimum, (1996). ar**v:quant-ph/9607014
Cover, T., Hart, P.: Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13(1), 21–27 (1967)
Alfeilat, H.A.A., Hassanat, A.B.A., Lasassmeh, O., Tarawneh, A.S., Alhasanat, M.B., Salman, H.S., Prasath, V.B.S.: Effects of distance measure choice on K-nearest neighbor classifier performance: a review. Big Data 7(4), 221–248 (2019)
Giovannetti, V., Lloyd, S., Maccone, L.: Quantum random access memory. Phys. Rev. Lett. 100, 160501 (2008)
Kerenidis, I., Prakash, A.: Quantum recommendation systems, (2016). ar**v:1603.08675
Giovannetti, V., Lloyd, S., Maccone, L.: Architectures for a quantum random access memory. Phys. Rev. A 78, 052310 (2008)
Anupam, P.: Quantum algorithms for linear algebra and machine learning. University of California, Berkeley, EECS Department (2014). Ph.D. thesis
Wang, D., Liu, Z.H., Zhu, W.N., Li, S.Z.: Design of quantum comparator based on extended general Toffoli gates with multiple targets. Comput. Sci. 39(9), 302–306 (2012)
Kaye, P.: Reversible addition circuit using one ancillary bit with application to quantum computing, (2004). ar**v:quant-ph/0408173
Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation, In Contemporary Mathematics Series Millenium, vol. 305, p. 53. AMS, New York (2002)
Acknowledgements
This work was supported by National Natural Science Foundation of China (Grants Nos. 61976053, 61772134, and 62171131), Fujian Province Natural Science Foundation (Grant No. 2018J01776), and Program for New Century Excellent Talents in Fujian Province University.
Author information
Authors and Affiliations
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Li, J., Lin, S., Yu, K. et al. Quantum K-nearest neighbor classification algorithm based on Hamming distance. Quantum Inf Process 21, 18 (2022). https://doi.org/10.1007/s11128-021-03361-0
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11128-021-03361-0