A quantum k-nearest neighbors algorithm based on the Euclidean distance estimation

Abstract

The k-nearest neighbors (k-NN) is a basic machine learning (ML) algorithm, and several quantum versions of it, employing different distance metrics, have been presented in the last few years. Although the Euclidean distance is one of the most widely used distance metrics in ML, it has not received much consideration in the development of these quantum variants. In this article, a novel quantum k-NN algorithm based on the Euclidean distance is introduced. Specifically, the algorithm is characterised by a quantum encoding requiring a low number of qubits and a simple quantum circuit not involving oracles, aspects that favor its realization. In addition to the mathematical formulation and some complexity observations, a detailed empirical evaluation with simulations is presented. In particular, the results have shown the correctness of the formulation, a drop in the performance of the algorithm when the number of measurements is limited, the competitiveness with respect to some classical baseline methods in the ideal case, and the possibility of improving the performance by increasing the number of measurements.

arXiv comment35 pages, 12 figures, 15 tables

References in corpus (17)

• Quantum Machine Learning
• Quantum support vector machine for big data classification
• Quantum Amplitude Amplification and Estimation
• Quantum Algorithms Revisited
• Quantum fingerprinting
• Quantum random access memory
• Quantum algorithms for supervised and unsupervised machine learning
• Implementing a distance-based classifier with a quantum interference circuit
• Quantum singular value decomposition of non-sparse low-rank matrices
• Quantum Analog-Digital Conversion
• Quantum K-nearest neighbor classification algorithm based on Hamming distance
• Reversible addition circuit using one ancillary bit with application to quantum computing
• Quantum version of the k-NN classifier based on a quantum sorting algorithm
• Quantum Unsupervised and Supervised Learning on Superconducting Processors
• A Quantum Algorithm for Finding $k$-Minima
• Implementation and Empirical Evaluation of a Quantum Machine Learning Pipeline for Local Classification
• Quantum K-medians Algorithm Using Parallel Euclidean Distance Estimator

Cited by in corpus (4)

• Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
• Comparative Analysis of Quantum and Classical Support Vector Classifiers for Software Bug Prediction: An Exploratory Study
• Fast Quantum Amplitude Encoding of Typical Classical Data
• Quantum Minimal Learning Machine: A Fidelity-Based Approach to Error Mitigation