Quantum algorithm for angle-based anomaly detection
Abstract
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.
