  Anomaly detection, an important branch of machine learning, plays a critical
role in fraud detection, health care, intrusion detection, military
surveillance, etc. As one of the most commonly used unsupervised anomaly
detection algorithms, the Local Outlier Factor algorithm (LOF algorithm) has
been extensively studied. This algorithm contains three steps, i.e.,
determining the k-distance neighborhood for each data point x, computing the
local reachability density of x, and calculating the local outlier factor of x
to judge whether x is abnormal. The LOF algorithm is computationally expensive
when processing big data sets. Here we present a quantum LOF algorithm
consisting of three parts corresponding to the classical algorithm.
Specifically, the k-distance neighborhood of x is determined by amplitude
estimation and minimum search; the local reachability density of each data
point is calculated in parallel based on the quantum multiply-adder; the local
outlier factor of each data point is obtained in parallel using amplitude
estimation. It is shown that our quantum algorithm achieves exponential speedup
on the dimension of the data points and polynomial speedup on the number of
data points compared to its classical counterpart. This work demonstrates the
advantage of quantum computing in unsupervised anomaly detection.
