New approach of KNN Algorithm in quantum computing based on new design of quantum circuits

Vu Tuan Hai, Phan Hoang Chuong, Pham The Bao


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.

Full Text:



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


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.