New approach of KNN Algorithm in quantum computing based on new design of quantum circuits
Abstract
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
DOI:
https://doi.org/10.31449/inf.v46i5.3608Downloads
Published
How to Cite
Issue
Section
License
Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.
All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.
Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.
