Quantum Algorithm for Unsupervised Anomaly Detection

• URL: http://arxiv.org/abs/2304.08710v1
• Date: Tue, 18 Apr 2023 03:20:11 GMT
• Title: Quantum Algorithm for Unsupervised Anomaly Detection
• Authors: MingChao Guo, ShiJie Pan, WenMin Li, Fei Gao, SuJuan Qin, XiaoLing Yu, XuanWen Zhang, QiaoYan Wen
• Abstract summary: Anomaly detection plays a critical role in fraud detection, health care intrusion detection, military surveillance, etc. The Local Outlier Factor algorithm (LOF algorithm) has been extensively studied. Here we present a quantum LOF algorithm consisting of three parts corresponding to the classical algorithm.
• Score: 5.4335077019052145
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Unsupervised anomaly detection algorithms on real-world data: how many do we need? [1.4610038284393165]
  This study is the largest comparison of unsupervised anomaly detection algorithms to date. On the local datasets the $k$NN ($k$-nearest neighbor) algorithm comes out on top. On the global datasets the EIF (extended isolation forest) algorithm performs the best.
  arXiv  Detail & Related papers  (2023-05-01T09:27:42Z)
• Encoding of data sets and algorithms [0.0]
  In many high-impact applications, it is important to ensure the quality of output of a machine learning algorithm. We have initiated a mathematically rigorous theory to decide which models are close to each other in terms of certain metrics. A given threshold metric acting on this grid will express the nearness (or statistical distance) from each algorithm and data set of interest to any given application.
  arXiv  Detail & Related papers  (2023-03-02T05:29:27Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• NISQ-friendly measurement-based quantum clustering algorithms [0.7373617024876725]
  Two novel measurement-based, quantum clustering algorithms are proposed. The first algorithm follows a divisive approach, the second is based on unsharp measurements. Both algorithms are simplistic in nature, easy to implement, and well suited for noisy intermediate scale quantum computers.
  arXiv  Detail & Related papers  (2023-02-01T16:38:27Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum clustering and jet reconstruction at the LHC [0.0]
  Jet clustering at the CERN's Large Hadron Collider is computationally expensive. We consider two novel quantum algorithms which may speed up the classical jet clustering algorithms.
  arXiv  Detail & Related papers  (2022-04-13T16:27:04Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Quantum algorithms for anomaly detection using amplitude estimation [5.20363732303968]
  Anomaly detection algorithm based on density estimation (called ADDE algorithm) is one of widely used algorithms. In this paper, we propose a new quantum ADDE algorithm based on amplitude estimation.
  arXiv  Detail & Related papers  (2021-09-28T15:47:56Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  We study the widely adopted ancestral sampling algorithms for auto-regressive language models. We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
  arXiv  Detail & Related papers  (2020-09-15T17:28:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.