基于角度的量子异常检测算法  

Quantum algorithm for angle-based anomaly detection

作　　者：饶洪淼 吁超华 吴英培 刘德喜[1,2] 刘喜平[1,2] RAO HongMiao;YU ChaoHua;WU YingPei;LIU DeXi;LIU XiPing(School of Computing and Artificial Intelligence,Jiangxi University of Finance and Economics,Nanchang 330032,China;Jiangxi Provincial Key Laboratory of Multimedia Intelligent Processing,Jiangxi University of Finance and Economics,Nanchang 330032,China)

机构地区：[1]江西财经大学计算机与人工智能学院,南昌330032 [2]江西财经大学多媒体智能处理江西省重点实验室,南昌330032

出　　处：《中国科学:物理学、力学、天文学》2025年第4期63-72,共10页Scientia Sinica Physica,Mechanica & Astronomica

摘　　要：异常检测是机器学习和数据挖掘的一项重要任务,在金融欺诈检测、网络入侵检测和医疗保健等领域发挥着关键作用.基于角度的异常检测(Angle-Based Outlier Detection,ABOD)算法是目前最常用的异常检测方法之一,其核心步骤是计算每个样本点与其他点的距离向量之间的角度方差,并将角度方差低于某个阈值的点标记为异常点.经典ABOD算法的时间复杂度关于样本数量M的规模为O(M3),这使得该算法难以高效处理大规模数据集.为此,本文提出一个量子ABOD算法,该算法利用量子幅度估计技术,以量子并行方式计算所有点的角度方差,并进一步利用量子幅度放大技术搜索出异常点.所提量子ABOD算法的时间复杂度关于M的规模为O[√M log(M)],与经典ABOD算法相比实现了M的多项式级加速.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 O(M3)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[√M log(M)]with respect to M,achieving a polynomial speedup with respect to M.

关 键 词：基于角度的异常检测 量子算法 多项式级加速 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]