Mahalanobis distance is a distance measure that takes into account the relationship between features. In this paper, we proposed a quantum KNN classification algorithm based on the Mahalanobis distance, which combines the classical KNN algorithm with quantum computing to solve supervised classification problem in machine learning. Firstly, a quantum sub-algorithm for searching the minimum of disordered data set is utilized to find out K nearest neighbors of the testing sample. Finally, its category can be obtained by counting the categories of K nearest neighbors. Moreover, it is shown that the proposed quantum algorithm has the effect of squared acceleration compared with the classical counterpart.
Mahalanobis distance is a distance measure that takes into account the relationship between features. In this paper, we proposed a quantum KNN classification algorithm based on the Mahalanobis distance, which combines the classical KNN algorithm with quantum computing to solve supervised classification problem in machine learning. Firstly, a quantum sub-algorithm for searching the minimum of disordered data set is utilized to find out K nearest neighbors of the testing sample. Finally, its category can be obtained by counting the categories of K nearest neighbors. Moreover, it is shown that the proposed quantum algorithm has the effect of squared acceleration compared with the classical counterpart.
One of the simplest and most effective classical machine learning algorithms is the k-nearest neighbors algorithm (kNN) which classifies an unknown test state by finding the k nearest neighbors from a set of M train states. Here we present a quantum analog of classical kNN − quantum kNN (QkNN) − based on fidelity as the similarity measure. We show that QkNN algorithm can be reduced to an instance of the quantum k-maxima algorithm, hence the query complexity of QkNN is O(kM). The non-trivial task in this reduction is to encode the fidelity information between the test state and all the train states as amplitudes of a quantum state. Converting this amplitude encoded information to a digital format enables us to compare them efficiently, thus completing the reduction. Unlike classical kNN and existing quantum kNN algorithms, the proposed algorithm can be directly used on quantum data thereby bypassing expensive processes such as quantum state tomography. As an example, we show the applicability of this algorithm in entanglement classification and quantum state discrimination.
The KNN (K-nearest neighbors) algorithm is one of Top-10 data mining algorithms and is widely used in various fields of artificial intelligence. This leads to that quantum KNN algorithms have developed and achieved certain speed improvements, denoted as Q-KNN. However, these Q-KNN methods must face two key problems as follows. The first one is that they are mainly focused on neighbor selection without paying attention to the influence of K value on the algorithm. The second is that only the neighbor selection process is quantized, and the selection of K value is not quantized. To solve these problems, this paper designs a novel quantum circuit for KNN classification, so as to simultaneously quantumize the neighbor selection and K value selection process. Specifically, the least squares loss and sparse regularization term are first used to construct the objective function of the proposed quantum KNN, so that it can simultaneously obtain the optimal K value and K nearest neighbors of the testing data. And then, a new quantum circuit is proposed to quantumize the process through quantum phase estimation, controlled rotation, and inverse phase estimation techniques. Finally, experiments are conducted with qiskit and matlab to output the quantum and classical results of the algorithm, verifying that the proposed algorithm can output the optimal K value and K nearest neighbors for each testing data.
Although multi-label k-nearest neighbor (ML-kNN) is able to effectively solve multi-label learning (MLL) problem with local neighborhood similarity, its time complexity is nearly unacceptable with large-scale datasets. To solve this issue, we propose a novel ML-kNN algorithm with quantum computing techniques, which called quantum multi-label k-nearest neighbor (QML-kNN). In particular, we first accelerate the calculation of the prior probability by taking advantage of quantum phase estimation and Grover's amplitude amplification. Then, a controlled-SWAP test and a quantum k-maximal similarity search are used for efficiently identifying the neighbors. Subsequently, a quantum parallel counting circuit (QPCC) is designed to rapidly calculate the posterior probabilities. Experimental results demonstrate that QML-kNN is able to significantly reduce the time complexity of solving multi-label problems with performance improvement, achieving a substantial speedup over the classical MLL algorithm.
Abstract The K‐nearest neighbor algorithm is one of the most frequently applied supervised machine learning algorithms. Similarity computing is considered to be the most crucial and time‐consuming step among the classical K‐nearest neighbor algorithm. A quantum K‐nearest neighbor algorithm is proposed based on the divide‐and‐conquer strategy. A quantum circuit is designed to calculate the fidelity between the test sample and each feature vector of the training dataset. The quantum K‐nearest neighbor algorithm has higher classification efficiency in high‐dimensional data processing. The classification accuracy of the proposed algorithm is equivalent to that of the classical K‐nearest neighbor algorithm under the IRIS dataset. In addition, compared with the typical quantum K‐nearest neighbor algorithms, the proposed classification method possesses higher classification accuracy with less calculation time, which has wide applications in the industrial field.
Text classification is one of key problems in pattern recognition. The KNN algorithm is a widely used text classification algorithm, because it is simple, valid and non-parameters. The main idea of KNN algorithm is to calculate the similarity between the new sample with unknown class label and the training samples, and choosing the class label of the highest k nearest neighbors as the new sample's class label. However, the text contains hundreds and thousands of features. The similarity computing in large numbers of vector will cost many time. In fact that, many machine learning algorithms are unable to manipulate and compute large number of vectors in high-dimensional space. Quantum computing algorithms are good at computing high-dimensional vectors in large tensor product spaces. It can provide exponential speed-up over its classical counterparts. The N-dimensional quantum vectors represent 2N quantum superposition states. The similarity computing on the N-dimensional vectors is also on the 2N quantum superposition states simultaneously. Therefore, this paper introduces a KNN algorithms based on quantum computing, which uses fidelity to compute the similarity between two quantum states. The Control-Swap Test gate is very convenient as a fidelity estimator.
This paper presents a novel quantum K-nearest neighbors (QKNN) algorithm, which offers improved performance over the classical k-NN technique by incorporating quantum computing (QC) techniques to enhance classification accuracy, scalability, and robustness. The proposed modifications focus on optimizing quantum data encoding using Hadamard and rotation gates, ensuring more effective rendering of classical data in quantum states. In addition, the quantum feature extraction process is significantly enhanced by the use of entangled gates such as IsingXY and CNOT, which enables better feature interactions and class separability. A novel quantum distance metric, based on the swap test, is introduced to calculate similarity measures between various quantum states, offering superior accuracy and computational efficiency compared to traditional Euclidean distance metrics. We assess the achievement of the proposed QKNN algorithm on three benchmark datasets: Wisconsin Breast Cancer, Iris, and Bank Note Authentication, and have noted its superior performance relative to both classical k-NN (CKNN) and Quantum Neural Network (QNN). The proposed QKNN algorithm is found to achieve prediction accuracies of 98.25%, 100%, and 99.27% ,respectively, for the three datasets, while the customized QNN shows prediction accuracies of only 97.17%, 83.33%, and 86.18%, respectively. Furthermore, we address the challenges of quantum noise by incorporating a repetition encoding-based error mitigation strategy, which ensures the stability and resilience of the algorithm in noisy quantum environments. The results highlight the potential of the proposed QKNN as a scalable, efficient and robust quantum-enhanced machine learning algorithm, especially in high-dimensional and complex datasets, when traditional approaches frequently fail.