论文标题
用于序列异常检测的量子算法
Quantum Algorithm for Anomaly Detection of Sequences
论文作者
论文摘要
序列的异常检测是数据挖掘的热门话题。使用振幅域中（称为ADPAAD）中的分段聚集物近似的异常检测是序列异常检测中广泛使用的方法之一。执行ADPAAD的经典算法中的核心步骤是构建子序列的近似表示，其中每个子序列的元素根据振幅域将几个小节分为几个小节，然后计算了小节的平均值。处理大规模序列时的计算昂贵。在本文中，我们提出了一种用于ADPAAD的量子算法，该算法可以分配子序列并平行计算平均值。我们的量子算法可以在其经典对应物上的子序列和子序列的长度上实现多项式加速。
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.
