| 星图上的散射量子行走搜索算法 |
| |
| 引用本文： | 刘艳梅,陈汉武,刘志昊,薛希玲,朱皖宁.星图上的散射量子行走搜索算法[J].物理学报,2015,64(1):10301-010301. |
| |
| 作者姓名： | 刘艳梅 陈汉武 刘志昊 薛希玲 朱皖宁 |
| |
| 作者单位： | 1. 东南大学计算机科学与工程学院, 南京 210096;2. 东南大学计算机网路和信息集成教育部重点实验室, 南京 210096 |
| |
| 基金项目： | 国家自然科学基金，高等学校博士学科点专项科研基金，东南大学计算机网络和信息集成教育部重点实验室开放基金(批准号:K93-9-2010-18)资助的课题.* Project supported by the National Natural Science Foundation of China，the China Specialized Research Fund for the Doctoral Program of Higher Education，the Key Laboratory of Computer Network and Information Integration of Ministry of Education of China |
| |
| 摘 要： | 量子行走是一种典型的量子计算模型, 近年来开始受到量子计算理论研究者们的广泛关注. 本文首先证明了在星图上硬币量子行走与散射量子行走的酉等价关系, 之后提出了一个在星图上的散射量子行走搜索算法. 该算法的时间复杂度与Grover算法相同, 但是当搜索的目标数目多于总数的1/3时搜索成功概率大于Grover算法.
|
| 关 键 词： | 硬币量子行走 散射量子行走 Grover算法 |
| 收稿时间： | 2014-05-27 |
Scattering quantum walk search algorithm on star graph |
| |
| Liu Yan-Mei,Chen Han-Wu,Liu Zhi-Hao,Xue Xi-Ling,Zhu Wan-Ning.Scattering quantum walk search algorithm on star graph[J].Acta Physica Sinica,2015,64(1):10301-010301. |
| |
| Authors: | Liu Yan-Mei Chen Han-Wu Liu Zhi-Hao Xue Xi-Ling Zhu Wan-Ning |
| |
| Institution: | 1. School of Computer Science and Engineering, Southeast University, Nanjing 210096, China;2. Key Laboratory of Computer Network and Information Integration(Southeast University), Ministry of Education, Nanjing 210096, China |
| |
| Abstract: | Quantum walk is a typical quantum computing model which is receiving significant attention in recent years from theory researchers. In this paper, we prove that the two major formulations for discrete quantum walks, coined and scattering, are unitarily equivalent on star graph. We then propose a new quantum search algorithm on star graph based on the scattering quantum walk. It is shown that the temporal complexity of the algorithm is the same as that in Grover algorithm, but success probability is greater than that in Grover algorithm when the objects are more than one third of total items. |
| |
| Keywords: | coined quantum walk scattering quantum walk grover algorithm |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《物理学报》浏览原始摘要信息 |
| 点击此处可从《物理学报》下载免费的PDF全文 |
|
