Abstract Anomaly detection of sequences is a hot topic in data mining. Anomaly detection using piecewise aggregate approximation in the amplitude domain (called ADPAAD) is one of the widely used methods in anomaly detection of sequences. The core step in the classical algorithm for performing ADPAAD is to construct an approximate representation of the subsequence, where the elements of each subsequence are divided into several subsections according to the amplitude domain, and then the average of the subsections is computed. It is computationally expensive when processing large‐scale sequences. In this paper, a quantum algorithm for ADPAAD is proposed, which can divide the subsequence elements and compute the average in parallel. The quantum algorithm can achieve polynomial speedups on the number of subsequences and the length of subsequences over its classical counterpart.
Abstract Anomaly detection of sequences is a hot topic in data mining. Anomaly detection using piecewise aggregate approximation in the amplitude domain (called ADPAAD) is one of the widely used methods in anomaly detection of sequences. The core step in the classical algorithm for performing ADPAAD is to construct an approximate representation of the subsequence, where the elements of each subsequence are divided into several subsections according to the amplitude domain, and then the average of the subsections is computed. It is computationally expensive when processing large‐scale sequences. In this paper, a quantum algorithm for ADPAAD is proposed, which can divide the subsequence elements and compute the average in parallel. The quantum algorithm can achieve polynomial speedups on the number of subsequences and the length of subsequences over its classical counterpart.
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.
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 with multivariate Gaussian distribution, which we refer to as Gassian anomaly detection (GAD), is a prominent task in data mining and machine learning. The core task of GAD is to obtain the mean value vector and the covariance matrix that characterize the probability density function of an unknown multivariate Gaussian distribution used to detect anomalies, which could be time-consuming when addressing a large dataset. Recently, several quantum algorithms have been proposed for GAD with substantial speedup over the classical GAD. However, they all require quantum phase estimation as key subroutines so that their quantum ciruits have long depth and are unfavorable in the noisy intermediate-scale and early fault-tolerant quantum eras. In this paper, we propose a quantum algorithm for GAD biult on arithmetic-free black-box quantum state preparation (AFQSP), which significantly shortens the quantum circuit depth and reduces the burden of quantum hardware. Specifically, we take advantage of AFQSP to estimate the magnitude of every mean value and that of every covariance matrix element in the classical form, and develop a technique referred to as Hadamard sign test to further reveal their signs, so that anomaly detection of any data point can be done immediately on a classical computer at little cost. It is shown that our quantum algorithm for GAD achieves exponential speedup over the classical GAD when handling low-dimensional datasets with well-conditioned data matrices, and is also time competitive compared to the prior quantum algorithms for GAD. Moreover, our algorithm releases the requirements of input data being quantum, mean centered, or feature correlated in the prior quantum algorithms for GAD, meaning that our algorithm is more practical on input data. Our work highlights the role of AFQSP in bringing quantum machine learning closer to reality.
Abstract Anomaly detection is an important problem with applications in various domains such as fraud detection, pattern recognition, or medical diagnosis. Several algorithms have been introduced using classical computing approaches. However, using quantum computing for solving anomaly detection problems in time series data is a widely unexplored research field. This paper explores the application of quantum autoencoders to time series anomaly detection. We investigate two primary techniques for classifying anomalies: (1) Analyzing the reconstruction error generated by the quantum autoencoder and (2) latent representation analysis. Our simulated experimental results, conducted across various ansaetze, demonstrate that quantum autoencoders consistently outperform classical deep learning-based autoencoders across multiple datasets. Specifically, quantum autoencoders achieve superior anomaly detection performance while utilizing 60–230 times fewer parameters and requiring five times fewer training iterations. In addition, we implement our quantum encoder on real quantum hardware. Our experimental results demonstrate that quantum autoencoders achieve anomaly detection performance on par with their simulated counterparts.
We present a quantum algorithm for estimating the amplitude content of user-specified sequency bands in quantum-encoded signals. The method employs a sequency-ordered Quantum Walsh-Hadamard Transform (QWHT), a comparator-based oracle that coherently marks basis states within an arbitrary sequency range, and Quantum Amplitude Estimation (QAE) to estimate the total probability mass in the selected band. This enables the detection of structured signal components, including both high- and low-sequency features, as well as the identification of rapid sign-change behavior associated with noise or anomalies. The proposed method can be embedded as a module within a larger quantum algorithm; in this setting, both the input and output remain fully quantum, enabling seamless integration with upstream and downstream quantum operations. We show that the sequency-ordered QWHT can be implemented with circuit depth O(log2N) (equivalently O(n) for N=2n) when acting on an amplitude-encoded quantum state, whereas computing the full Walsh-Hadamard spectrum of an explicit length-N classical signal requires O(Nlog2N) operations via the fast Walsh-Hadamard transform. This results in an exponential quantum advantage when the QWHT is used as a modular block within a larger quantum algorithm, relative to classical fast Walsh-Hadamard transform-based approaches operating on explicit data. From an application perspective, the proposed sequency band-energy estimation may be interpreted as a structure-based anomaly indicator, enabling the detection of unexpected high-sequency components relative to a nominal low-sequency signal class. The algorithm is applicable to quantum-enhanced signal processing tasks such as zero-crossing analysis, band-limited noise estimation, and feature extraction in the Walsh basis.
Anomaly detection is an important problem with applications in various domains such as fraud detection, pattern recognition or medical diagnosis. Several algorithms have been introduced using classical computing approaches. However, using quantum computing for solving anomaly detection problems in time series data is a widely unexplored research field. This paper explores the application of quantum autoencoders to time series anomaly detection. We investigate two primary techniques for classifying anomalies: (1) Analyzing the reconstruction error generated by the quantum autoencoder and (2) latent representation analysis. Our simulated experimental results, conducted across various ansaetze, demonstrate that quantum autoencoders consistently outperform classical deep learning-based autoencoders across multiple datasets. Specifically, quantum autoencoders achieve superior anomaly detection performance while utilizing 60-230 times fewer parameters and requiring five times fewer training iterations. In addition, we implement our quantum encoder on real quantum hardware. Our experimental results demonstrate that quantum autoencoders achieve anomaly detection performance on par with their simulated counterparts.