Skip to main content
SpringerLink
Log in

Quantum Algorithm for K-Nearest Neighbors Classification Based on the Metric of Hamming Distance

  • Published:
International Journal of Theoretical Physics Aims and scope Submit manuscript

Abstract

K-nearest neighbors (KNN) algorithm is a common algorithm used for classification, and also a sub-routine in various complicated machine learning tasks. In this paper, we presented a quantum algorithm (QKNN) for implementing this algorithm based on the metric of Hamming distance. We put forward a quantum circuit for computing Hamming distance between testing sample and each feature vector in the training set. Taking advantage of this method, we realized a good analog for classical KNN algorithm by setting a distance threshold value t to select k − n e a r e s t neighbors. As a result, QKNN achieves O(n 3) performance which is only relevant to the dimension of feature vectors and high classification accuracy, outperforms Llyod’s algorithm (Lloyd et al. 2013) and Wiebe’s algorithm (Wiebe et al. 2014).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Armbrust, M., Fox, A., Griffith, R., et al.: A view of cloud computing. Commun. ACM. 53(4), 50–58 (2010)

    Article  Google Scholar 

  2. Schölkopf, B., Platt, J., Hofmann, T.: Map-Reduce for machine learning on multicore. In: Proceedings of the 2006 Conference Advances in Neural Information Processing Systems 19, pp. 281–288. MIT Press (2007)

  3. Low, Y., Bickson, D., Gonzalez, J., et al.: Distributed GraphLab: a framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment 5(8), 716–727 (2012)

    Article  Google Scholar 

  4. Liu, Q., Cai, W., Shen, J., et al.: A speculative approach to spatial-temporal efficiency with multi-objective optimization in a heterogeneous cloud environment. Security Commun. Netw. 9(17), 4002–4012 (2016)

    Article  Google Scholar 

  5. Xia, Z., Wang, X., Zhang, L., et al.: A privacy-preserving and copy-deterrence content-based image retrieval scheme in cloud computing. IEEE Trans. Inf. Forensics Secur. 11(11), 2594–2608 (2016)

    Article  Google Scholar 

  6. Fu, Z., Ren, K., Shu, J., et al.: Enabling personalized search over encrypted outsourced data with efficiency improvement. IEEE Trans. Parallel Distrib. Syst. 27 (9), 2546–2559 (2016)

    Article  Google Scholar 

  7. Fu, Z., Sun, X., Liu, Q., et al.: Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE Trans. Commun. E98-B(1), 190–200 (2015)

    Article  ADS  Google Scholar 

  8. Xia, Z., Wang, X., Sun, X., et al.: A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE Trans. Parallel Distrib. Syst. 27(2), 340–352 (2015)

    Article  Google Scholar 

  9. Nielsen, M.A., Chuang, I.L.: Quantum computation and quantum information [M]. Cambridge University Press, Cambridge (2000)

    MATH  Google Scholar 

  10. Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum principal component analysis. Nature Physics. 10(9), 631–633 (2014)

    Article  ADS  Google Scholar 

  11. Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411 (2013)

  12. Lloyd, S., Garnerone, S., Zanardi, P.: Quantum algorithms for topological and geometric analysis of data. Nat. Commun. 7, 10138 (2016)

    Article  ADS  Google Scholar 

  13. Wiebe, N., Kapoor, A., Svore, K.: Quantum nearestneighbor algorithms for machine learning. arXiv:1401.2142 (2014)

  14. Wiebe, N., Granade, C., Ferrie, C., et al.: Quantum Hamiltonian learning using imperfect quantum resources. Phys. Rev. A 89(4), 042314 (2014)

    Article  ADS  Google Scholar 

  15. Trugenberger, D.A.: Quantum pattern recognition. Quantum Inf. Process. 1(6), 471–493 (2002)

    Article  MathSciNet  Google Scholar 

  16. Aïmeur, E., Brassard, G., Gambs, S.: Machine learning in a quantum world. In: Advances in Artificial Intelligence Lecture Notes in Computer Science, vol. 4013, pp 431–442 (2006)

  17. Hentschel, A., Sanders, B.C.: Machine learning for precise quantum measurement. Phys. Rev. Lett. 104(6), 063603 (2010)

    Article  ADS  Google Scholar 

  18. Gammelmark, S., Mølmer, K.: Quantum learning by measurement and feedback. New J. Phys. 11, 033017 (2009)

    Article  ADS  Google Scholar 

  19. Bisio, A., Chiribella, G., D’Ariano, G.M., et al.: Optimal quantum learning of a unitary transformation. Phys. Rev. A 81(3), 032324 (2010)

    Article  ADS  Google Scholar 

  20. Lu, S., Braunstein, S.L.: Quantum decision tree classifier. Quantum Inf. Process. 13(3), 757–770 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  21. Rebentrost, P., Mohseni, M., Lloyd, S.: Quantum support vector machine for big data classification. Phys. Rev. Lett. 113(13), 130503 (2014)

    Article  ADS  Google Scholar 

  22. Schuld, M., Sinayskiy, I., Petruccione, F.: Quantum computing for pattern classification. In: Proceedings 13th Pacific Rim International Conference on Artificial Intelligence (PRICAI), pp 208–220 (2014)

  23. Buhrman, H., Cleve, R., Watrous, J., et al.: Quantum fingerprinting. Phys. Rev. Lett. 87(16), 167902 (2001)

    Article  ADS  Google Scholar 

  24. Brassard, G., Høyer, P., Mosca, M., et al.: Quantum amplitude amplification and estimation. arXiv:0005055 [quant-ph/] (2000)

  25. Dürr C., Høyer, P.: A quantum algorithm for finding the minimum. arXiv:9607014 [quant-ph/] (1996)

  26. Manevitz, L.M., Yousef, M.: One-class SVMs for document classification. J. Mach. Learn. Res. 2(12), 139–154 (2001)

    MATH  Google Scholar 

  27. Norouzi, M., Fleet, D.J., Salakhutdinov R.R.: Hamming distance metric learning [C]. In: Advances in Neural Information Processing Systems (NIPS). 061–1069 (2012)

  28. Rai, H., Yadav, A.: Iris recognition using combined support vector machine and Hamming distance approach. Expert Syst. Appl. 41(2), 588–593 (2014)

    Article  Google Scholar 

  29. Kaye, P.: Reversible addition circuit using one ancillary bit with application to quantum computing. arXiv:0408173v2 [quant-ph] (2004)

  30. Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325–328 (1997)

    Article  ADS  Google Scholar 

Download references

Acknowledgements

This work is supported by the National Natural Science Foundation of China (Grant No. 61170321,61502101), Natural Science Foundation of Jiangsu Province, China (Grant No. BK20140651), Natural Science Foundation of Anhui Province, China (Grant No. 1608085MF129, 1708085MF162), Foundation for Natural Science Major Program of Education Bureau of Anhui Province (Grant No. KJ2015ZD09) and the open fund of Key Laboratory of Computer Network and Information Integration in Southeast University, Ministry of Education, China (Grant No. K93-9-2015-10C).

Author information

Authors and Affiliations

  1. School of Computer Science and Technology, Anhui University of Technology, Maanshan, 243005, China

    Yue Ruan, Xiling Xue & Heng Liu

  2. Key Laboratory of Computer Network and Information Integration, Southeast University, Ministry of Education, Nanjing, 210096, China

    Yue Ruan

  3. School of Computer Science and Engineering, Southeast University, Nanjing, 210096, China

    Jianing Tan & Xi Li

Authors
  1. Yue Ruan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiling Xue
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Heng Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jianing Tan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Xi Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yue Ruan.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ruan, Y., Xue, X., Liu, H. et al. Quantum Algorithm for K-Nearest Neighbors Classification Based on the Metric of Hamming Distance. Int J Theor Phys 56, 3496–3507 (2017). https://doi.org/10.1007/s10773-017-3514-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10773-017-3514-4

Keywords

Search

Navigation