New approach of KNN Algorithm in quantum computing based on new design of quantum circuits
DOI:
https://doi.org/10.31449/inf.v46i5.3608Abstract
Quantum computing has risen as the new type of computer that theoretically reduces the time complexity of classical methods exponentially because of the nature of superposition. It is promising to reduce runtimes on large data sets in machine learning (ML). Meanwhile, k-nearest neighbor (kNN) is a simple ML algorithm that can be translated to a quantum version (QkNN) to perform classification tasks efficiently. Here, we show a new version of QkNN which has a speed up in time complexity by using a new design of quantum circuits called integrated swap test. This quantum circuit can load two N-dimensional states and calculate the fidelity between them. Results show that QkNN allows us to take a different approach to the ML field.References
H¨affner et al., Quantum computing with trapped ions, Physics reports 469.4 (2008) 155-203.
Kok, Pieter et al., Linear optical quantum computing with photonic qubits, Reviews of modern physics 79.1 (2007) 135.
LeCun, Yann, Yoshua Bengio, and Geoffrey Hinton, Deep learning, nature 521.7553(2015) 436-444.
Lu, Sirui et al., Physical Review A 98.1 (2018) 012315.
Lloyd, Seth, Masoud Mohseni, and Patrick Rebentrost, Quantum algorithms for supervised and unsupervised machine learning arXiv preprint arXiv:1307.0411 (2013).
Rebentrost, Patrick, Masoud Mohseni, and Seth Lloyd, Quantum support vector machine for big data classification, Physical review letters 113.13 (2014) 130503.
Lloyd, Seth, Masoud Mohseni, and Patrick Rebentrost, Quantum principal component analysis, Nature Physics 10.9 (2014) 631-633.
Ruan, Yue et al., Quantum algorithm for k-nearest neighbors classification based on the metric of hamming distance, International Journal of Theoretical Physics 56.11 (2017) 3496-3507.
Basheer, Afrad, and Sandeep K. Goyal, Quantum k-nearest neighbor machine learning algorithm, arXiv preprint arXiv:2003.09187 (2020).
Fastovets, D. V. et al., Machine learning methods in quantum computing theory, International Conference on Micro-and Nano-Electronics 2018. Vol. 11022. International Society for Optics and Photonics (2019).
Wiebe, Nathan, Ashish Kapoor, and Krysta M. Svore, Quantum deep learning, arXiv preprint arXiv:1412.3489 (2014).
Kok, D. J., S. Caron, and A. Acun, Building a quantum kNN classifier with Qiskit: theoretical gains put to practice (2021).
Araujo, Israel et al., A divide-and-conquer algorithm for quantum state preparation, Scientific Reports 11.1 (2021) 1-12.
Cunningham, Padraig, and Sarah Jane Delany, k-Nearest Neighbour Classifiers–,arXiv preprint arXiv:2004.04523 (2015).
Jozsa, Richard, Fidelity for mixed quantum states, Journal of modern optics 41.12(1994) 2315-2323.
Zhang, Shichao et al., Learning k for knn classification, ACM Transactions on Intelligent Systems and Technology (TIST) 8.3 (2017) 1-19.
Barenco, Adriano et al., Stabilization of quantum computations by symmetrization, SIAM Journal on Computing 26.5 (1997) 1541-1557.
Resch, K. J., J. S. Lundeen, and A. M. Steinberg, Quantum state preparation and conditional coherence, Physical review letters 88.11 (2002) 113601.
Park, Daniel K. et al., Parallel quantum trajectories via forking for sampling without redundancy, New Journal of Physics 21.8 (2019) 083024.
Cormen, Thomas H. et al., Introduction to algorithms., MIT press (2009).
Wiebe, Nathan, Ashish Kapoor, and Krysta Svore, Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning, arXiv preprint arXiv:1401.2142 (2014).
Blake, Catherine,”UCI repository of machine learning databases, http://www. ics.uci. edu/ mlearn/MLRepository. html (1998).
Mitarai, Kosuke, Masahiro Kitagawa, and Keisuke Fujii, Quantum analog-digital conversion, Physical Review A 99.1 (2019) 012301
Downloads
Published
How to Cite
Issue
Section
License
I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.
I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.
In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.
I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal. The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.
Copyright © Slovenian Society Informatika
