Quantum algorithms for anomaly detection using amplitude estimation

Abstract

Anomaly detection plays a critical role in fraud detection, health care, intrusion detection, military surveillance, etc. Anomaly detection algorithm based on density estimation (called ADDE algorithm) is one of widely used algorithms. Liang et al. proposed a quantum version of the ADDE algorithm [Phys. Rev. A 99, 052310 (2019)] and it is believed that the algorithm has exponential speedups on both the number and the dimension of training data point over the classical algorithm. In this paper, we find that Liang et al.'s algorithm doesn't actually execute. Then we propose a new quantum ADDE algorithm based on amplitude estimation. It is shown that our algorithm can achieves exponential speedup on the number $M$ of training data points compared with the classical counterpart. Besides, the idea of our algorithm can be applied to optimize the anomaly detection algorithm based on kernel principal component analysis (called ADKPCA algorithm). Different from the quantum ADKPCA proposed by Liu et al. [Phys. Rev. A 97, 042315 (2018)], compared with the classical counterpart, which offer exponential speedup on the dimension $d$ of data points, our algorithm achieves exponential speedup on $M$.

References in corpus (35)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum Amplitude Amplification and Estimation
• Quantum principal component analysis
• Quantum fingerprinting
• Quantum random access memory
• Quantum generative adversarial learning
• Quantum Data Fitting
• Quantum algorithms for supervised and unsupervised machine learning
• Prediction by linear regression on a quantum computer
• Amplitude estimation without phase estimation
• Quantum private queries
• Quantum Hopfield neural network
• Quantum arithmetic with the Quantum Fourier Transform
• Quantum generative adversarial network for generating discrete distribution
• Quantum Algorithm for Linear Regression
• Quantum machine learning for quantum anomaly detection
• Quantum Discriminant Analysis for Dimensionality Reduction and Classification
• Variational Quantum algorithm for Poisson equation
• Quantum data compression by principal component analysis
• Quantum Analog-Digital Conversion
• Quantum algorithm for association rules mining
• Quantum algorithm for association rules mining
• Quantum Fourier Transform in Computational Basis
• Quantum algorithm for visual tracking
• Asymptotic Quantum Algorithm for the Toeplitz Systems
• Quantum Anomaly Detection with Density Estimation and Multivariate Gaussian Distribution
• Variational quantum amplitude estimation
• Improved quantum algorithm for A-optimal projection
• Efficient quantum circuit for singular value thresholding
• A brief introduction to quantum algorithms
• Quantum speedup for twin support vector machines
• Clustering in Hilbert space of a quantum optimization problem

Cited by in corpus (5)

• Financial Fraud Detection: A Comparative Study of Quantum Machine Learning Models
• Quantum Dimensionality Reduction by Linear Discriminant Analysis
• Quantum Algorithm for Unsupervised Anomaly Detection
• Quantum density estimation with density matrices: Application to quantum anomaly detection
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications