量子行走搜索算法中硬币算子作用分析  

Analysis on effects of coin operators in search algorithms based on quantum walk

作　　者：薛希玲 刘志昊[2] 阮越[1] 张艳霞[3] Xue Xiling;Liu Zhihao;Ruan Yue;Zhang Yanxia(School of Computer Science and Technology,Anhui University of Technology,Ma'anshan 243032;School of Computer Science and Engineering,Southeast University,Nanjing 211189;School of Microelectronics and Data Science,Anhui University of Technology,Ma'anshan 243032)

机构地区：[1]安徽工业大学计算机科学与工程学院,马鞍山243032 [2]东南大学计算机科学与工程学院,南京211189 [3]安徽工业大学微电子与数据科学学院,马鞍山243032

出　　处：《东南大学学报（自然科学版）》2023年第5期947-954,共8页Journal of Southeast University：Natural Science Edition

基　　金：国家自然科学基金资助项目(61802002,62071240);安徽省自然科学基金资助项目(2008085QF305);安徽省高校重点科研资助项目(KJ2020A0233);安徽省科研编制计划资助项目(2022AH050290)。

摘　　要：为研究基于不同标记硬币算子的搜索算法的性能,分别使用负的恒等算子I、Grover扩散算子D和量子Fourier变换算子F作为标记算子构造基于算子-I、-D和-F的搜索算法(SAI、SAD和SAF),采用数值仿真研究其在对称图和随机图上搜索多个目标时的性能,分析SAI和SAD在一步量子行走中的作用,并使用不重复量子行走研究Cayley树根节点上的状态转移情况.结果表明,SAI的成功概率曲线近似为正弦函数平方曲线,并且在稠密图上成功概率大于0.5;SAD在搜索多个不相邻目标时等价于SAI,而在搜索Johnson图和随机图上的混合顶点时成功概率曲线出现双峰;SAF搜索相邻顶点时的性能取决于目标顶点硬币空间的基中各向量的顺序.在迭代数为g的4-Cayley树上实现了根节点状态在2g步的周期性转移.To study the performance of search algorithms based on different marking coins,the negative identity operator I,Grover diffusion operator D and quantum Fourier transform operator F are used as marking coin operators to construct search algorithms based on operators-I,-D and-F(SAI,SAD and SAF).Numerical simulations are used to explore the performance of these algorithms when searching for multiple target vertices on symmetric and random graphs.The effects of SAI and SAD in one-step quantum walk are analyzed,and state transition on the root of a Cayley tree is investigated using the nonrepeating quantum walk.The results show that the success probability curves of SAI are close to the square of sinusoidal curve,and the success probabilities are greater than 0.5 on dense graphs.SAD is equivalent to SAI when searching for non-adjacent multiple targets,while the success probability curves have double peaks when searching for hybrid vertices on Johnson graph and some random graphs.The performance of SAF when searching for adjacent targets depends on the order of each vector in the basis states of coin space of the target vertices.Finally,periodic state transfer is realized using nonrepeating coin on the root of 4-Cayley tree with generation g using 2 g steps.

关 键 词：量子行走 空间搜索 多目标 硬币算子 状态转移 

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