搜索空间自适应量子搜索算法  

Search Space Self-adaptive Quantum Search Algorithm

作　　者：谢旭明 段隆振[1] 邱桃荣[1] 康小丽[2] XIE Xu-ming;DUAN Long-zhen;QIU Tao-rong;KANG Xiao-li(School of Information Technology,Nanchang University,Nanchang 330031,China;Library,Nanchang University,Nanchang 330031,China)

机构地区：[1]南昌大学信息工程学院,南昌330031 [2]南昌大学图书馆,南昌330031

出　　处：《小型微型计算机系统》2021年第4期732-735,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61070139,81460769,61762045)资助。

摘　　要：量子搜索算法,相较于经典计算有着平方根的加速,在许多机器学习算法中都有广泛应用,如量子KNN算法、量子特征提取、量子主成分分析等.在目标分量占比较小的时候,量子搜索算法总能以较高的概率得到目标分量;然而,当目标分量占比较大时,量子搜索算法的成功概率急剧下降.为解决这个问题,本文拟提出一种搜索空间自适应的量子搜索算法.新算法依据目标分量占比的不同采用不同的策略:当目标分量占比为λ≥1/2,将搜索空间扩大为8N;当目标分量占比1/4≤λ<1/2时,将搜索空间扩大为4N;当目标分量占比1/8≤λ<1/4时,将搜索空间扩大为2N;当目标分量占比λ<1/8时,保持搜索空间不变.通过理论分析,改进算法整体效率得到显著的改进,能够保持93%以上的成功概率.The quantum search algorithm,having quadratic speedup over its classical counterpart,is widely studied in the field of machine learning,such as quantum KNN,quantum feature selection and quantum principal component analysis.The quantum search algorithm has a very high success rate when there is a low target proportion;however,when the target proportion is high,the performance is not so efficient.To solve the aforementioned problem,a new strategy,adjusting the search space according to different target proportions,is proposed in this study.Whenλ≥1/2,the search space was changed to 8N;when 1/4≤λ<1/2,the search space was changed to 4N;when(3-√5)/8≤λ<1/4,the search space was changed to 2N;whenλ<(3-√5)/8,the search space was unaltered.Through theoretical analysis,the adapted algorithm keeps a consistent higher-than-93%success rate.

关 键 词：搜索空间 自适应 量子搜索 GROVER算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]