The density peak anomaly detection algorithm based on KNN, one of the most frequently utilized classical algorithms, is widely applied in communication fields, such as network fault detection, network traffic detection, user behavior detection, and network intrusion detection. In this algorithm, the local density value and KNN distance of all data points must be calculated, which faces enormous computational cost and computational delay challenges when the data set is processed as the network scale increases. To address this trouble, we introduce quantum computing into the algorithm and propose a quantum version of the density peak anomaly detection algorithm based on KNN. The proposed quantum algorithm first utilizes the inner product estimate algorithm and the quantum minimum search algorithm to accelerate the determination of the K nearest neighbor set of each data point and the calculation of KNN distance. Then, it performs amplitude estimation to concurrently obtain the local density of all data points. Our quantum algorithm is shown to be exponentially faster than its classical counterpart in the dimensionality of the data points and polynomially faster than the classical algorithm in the number of data points.
The density peak anomaly detection algorithm based on KNN, one of the most frequently utilized classical algorithms, is widely applied in communication fields, such as network fault detection, network traffic detection, user behavior detection, and network intrusion detection. In this algorithm, the local density value and KNN distance of all data points must be calculated, which faces enormous computational cost and computational delay challenges when the data set is processed as the network scale increases. To address this trouble, we introduce quantum computing into the algorithm and propose a quantum version of the density peak anomaly detection algorithm based on KNN. The proposed quantum algorithm first utilizes the inner product estimate algorithm and the quantum minimum search algorithm to accelerate the determination of the K nearest neighbor set of each data point and the calculation of KNN distance. Then, it performs amplitude estimation to concurrently obtain the local density of all data points. Our quantum algorithm is shown to be exponentially faster than its classical counterpart in the dimensionality of the data points and polynomially faster than the classical algorithm in the number of data points.
Anomaly detection is a prominent task in machine learning and data mining, which plays a key role in various domains such as financial fraud detection, network intrusion detection, and healthcare. Angle-based outlier detection (ABOD) algorithm stands out as one of the most common approaches for anomaly detection, the core step of which involves computing the angular variance among distance vectors from each point to others, and then marking those points with angular variance lower than a threshold as outliers. The time complexity of classical ABOD algorithm scales as mathcalOM³) with respect to the number of samples M, making it hard to efficiently handle large-scale datasets. To this end, a quantum ABOD algorithm is proposed, in which quantum amplitude estimation is harnessed to compute angular variance in quantum parallel, and quantum amplitude amplification is further applied to search out the outliers. Compared with its classical counterpart, our quantum ABOD algorithm has time complexity Ołeft[\sqrt{M}\log(M)\right] with respect to M, achieving a polynomial speedup with respect to M.
Anomaly detection plays a crucial role in identifying rare and critical events, anomalies, or outliers that are not part of the normal data distribution. With the large volume of modern data and the widespread use of sensors and IoT devices, datasets have evolved into high-dimensional structures, posing significant challenges to anomaly detection tasks. In this work, we investigate to employ a hybrid quantum-classical algorithm to help handle such challenges. It is mainly based on Local Outlier Factor (LOF) algorithm to detect anomalies. However, we enhance distance estimation and k-nearest neighbor search via quantum algorithms. The proof-of-principle numerical results demonstrate the performance of the proposed method is competitive to previous algorithm.
High time complexity is one of the biggest challenges faced by k-Nearest Neighbors (kNN). Although current classical and quantum kNN algorithms have made some improvements, they still have a speed bottleneck when facing large amounts of data. To address this issue, we propose an innovative algorithm called Granular-Ball based Quantum kNN(GB-QkNN). This approach achieves higher efficiency by first employing granular-balls, which reduces the data size needed to processed. The search process is then accelerated by adopting a Hierarchical Navigable Small World (HNSW) method. Moreover, we optimize the time-consuming steps, such as distance calculation, of the HNSW via quantization, further reducing the time complexity of the construct and search process. By combining the use of granular-balls and quantization of the HNSW method, our approach manages to take advantage of these treatments and significantly reduces the time complexity of the kNN-like algorithms, as revealed by a comprehensive complexity analysis.
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.
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.