物理学报Issue(24)：27-38,12.DOI:10.7498/aps.64.240301
基于相位匹配的量子行走搜索算法及电路实现∗
Quantum walk search algorithm based on phase matching and circuit cmplementation
摘要
Abstract
As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N ). Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.关键词
Grover算法/相位匹配/量子行走搜索算法Key words
Grover algorithm/phase matching/quantum walk search algorithm引用本文复制引用
陈汉武,李科,赵生妹..基于相位匹配的量子行走搜索算法及电路实现∗[J].物理学报,2015,(24):27-38,12.基金项目
国家自然科学基金(批准号:61170321,61271238,61475075)和高等学校博士学科点专项科研基金(批准号:20110092110024,20123223110003)资助的课题.* Project supported by the National Natural Science Foundation of China (Grant Nos.61170321,61271238,61475075) and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant Nos.20110092110024,20123223110003) （批准号:61170321,61271238,61475075）
