Quantum Algorithm for Anomaly Detection of Sequences

• URL: http://arxiv.org/abs/2209.08594v1
• Date: Sun, 18 Sep 2022 16:14:16 GMT
• Title: Quantum Algorithm for Anomaly Detection of Sequences
• Authors: Ming-Chao Guo, Hai-Ling Liu, Shi-Jie Pan, Wen-Min Li, Su-Juan Qin, Xin-Yi Huang, Fei Gao and Qiao-Yan Wen
• Abstract summary: We propose a quantum algorithm for anomaly detection using Piecewise Aggregate in the Amplitude Domain (called ADPAAD) Our quantum algorithm can achieve speedups on the number of subsequences and the length of subsequences over its classical counterpart.
• Score: 13.087762988229068
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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, we propose a quantum algorithm for ADPAAD, which can divide the subsequence elements and compute the average in parallel. Our quantum algorithm can achieve polynomial speedups on the number of subsequences and the length of subsequences over its classical counterpart.

Related papers

• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Quantum algorithm for position weight matrix matching [0.9404723842159504]
  We propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching. The two proposed algorithms, the naive method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence.
  arXiv  Detail & Related papers  (2023-03-07T00:34:16Z)
• Exploring the role of parameters in variational quantum algorithms [59.20947681019466]
  We introduce a quantum-control-inspired method for the characterization of variational quantum circuits using the rank of the dynamical Lie algebra. A promising connection is found between the Lie rank, the accuracy of calculated energies, and the requisite depth to attain target states via a given circuit architecture.
  arXiv  Detail & Related papers  (2022-09-28T20:24:53Z)
• Efficient Approximate Kernel Based Spike Sequence Classification [56.2938724367661]
  Machine learning models, such as SVM, require a definition of distance/similarity between pairs of sequences. Exact methods yield better classification performance, but they pose high computational costs. We propose a series of ways to improve the performance of the approximate kernel in order to enhance its predictive performance.
  arXiv  Detail & Related papers  (2022-09-11T22:44:19Z)
• Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
  We propose an adaptive algorithm for interval estimation of amplitudes. The proposed algorithm uses a similar number of quantum queries to achieve the same level of precision. We rigorously prove that the number of oracle queries achieves $O(1/epsilon)$, i.e., a quadratic speedup over classical Monte Carlo sampling.
  arXiv  Detail & Related papers  (2022-06-16T21:11:15Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• 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)
• Nonparametric Extrema Analysis in Time Series for Envelope Extraction, Peak Detection and Clustering [0.0]
  We propose a nonparametric approach that can be used in envelope extraction, peak-burst detection and clustering in time series. Our problem formalization results in a naturally defined splitting/forking of the time series.
  arXiv  Detail & Related papers  (2021-09-05T14:21:24Z)
• Quantum K-nearest neighbor classification algorithm based on Hamming distance [3.4501155479285326]
  We propose a quantum K-nearest neighbor classification algorithm with Hamming distance. It is shown that the proposed algorithm can achieve a quadratical speedup by analyzing its time complexity briefly.
  arXiv  Detail & Related papers  (2021-03-07T04:08:21Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)

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.