基于置换群的多粒子环上量子行走的反馈搜索算法

• 作者: 姜瑶瑶 张文彬 初鹏程 马鸿洋
• 来源期刊: 物理学报
• 关键词: 搜索算法 量子行走 置换群 同构映射
• 年，卷（期）: 2022,（3）
• 所属期刊栏目: 总论|GENERAL
• 页码范围: 1-11
• 页数: 11页
• 语种: 中文
• DOI: 10.7498/aps.71.20211000

摘要

在量子计算科学中,如何更好地构建量子搜索算法一直以来受到学者们的广泛关注,并且基于量子行走寻找新的搜索算法也仍吸引着学者们不断深入研究与探索.本文从减少搜索过程中的时间消耗、增加算法搜索的准确性和可控性等多方面进行考虑,提出了一种基于置换群的多粒子量子行走搜索算法.首先分析得到置换群在空间中可看成一个闭环,定义了置换集合,并且通过同构映射将数据点所在数据集映射到定义的置换集,使得置换集合中元素数据点形成一一对应的关系.其次,根据给定初始态和硬币算符,在数据点集与置换集合张成的搜索空间中利用多粒子的量子行走在环上进行目标数据搜索.最后,根据函数Φ(w)=1找到目标数据,并用量子态存储数值,用于形成搜索算法的反馈控制;同时通过控制硬币算符从而控制量子行走在环上的行走方向,增加搜索的可操作性与准确性.本文利用多粒子的量子行走进行搜索,分析得到粒子数量参数j与时间复杂度呈非线性负相关;提出的量子行走搜索算法符合零点条件与下确界条件,且不受变量数j的影响;通过数值分析得到量子行走搜索算法的时间复杂度等价于O(3(N)),相比于Grover搜索算法提高了搜索效率.