完全图上结构异常的搜索算法——融入量子计算思维的经典算法探讨

• 作者: 刘志昊 李文骞 赵生妹 陈汉武
• 来源期刊: 东南大学学报（自然科学版）
• 学科: 工学
• 关键词: 散射量子行走 完全图 结构异常 不变子空间 微扰理论
• 年，卷（期）: 2017,（5）
• 页码范围: 866-872
• 页数: 7页
• 分类号: TP387
• 字数: 5249字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-0505.2017.05.005

摘要

采用量子计算思维探索新的图结构搜索方法,提出了一种基于散射量子行走的完全图上结构异常的搜索算法.在N个顶点的完全图上外接一个悬挂点,既破坏了完全图的对称性,也预示着图的拓扑结构将发生变化.首先给出完全图上散射量子行走酉算子U的解析刻画,将行走的Hilbert空间投影到低维不变子空间S,并给出酉算子U在空间S中的作用Us的形式;然后将完全图中所有状态的均匀叠加态选择为行走的初态,借用微扰理论求出酉算子Us的本征值和特征向量,通过数学解析计算出行走的终态(悬挂点);最后分析算法的时间复杂度和成功概率.算法分析及Matlab仿真结果表明,利用散射量子行走可以在O(√N)步内以接近于1的概率找到异常位置,而经典算法中使用邻接矩阵查找该异常点的时间复杂度为O(N),因此相对特定问题和特定的经典算法,使用散射量子行走搜索算法可以实现二次加速.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈汉武	东南大学计算机科学与工程学院	67	442	12.0	17.0
5	赵生妹	南京邮电大学通信与信息工程学院	99	581	13.0	17.0
6	刘志昊	东南大学计算机科学与工程学院	20	130	6.0	10.0
10	李文骞	东南大学计算机科学与工程学院	8	72	4.0	8.0