电子学报 ›› 2016, Vol. 44 ›› Issue (12): 2975-2980.DOI: 10.3969/j.issn.0372-2112.2016.12.023

• 学术论文 • 上一篇    下一篇

迭代次数自适应的Grover算法

朱皖宁1,2, 陈汉武2,3   

  1. 1. 金陵科技学院软件工程学院, 江苏南京 211199;
    2. 东南大学计算机科学与工程学院, 江苏南京 210096;
    3. 东南大学计算机网络和信息集成教育部重点实验室, 江苏南京 210096
  • 收稿日期:2015-03-10 修回日期:2016-05-10 出版日期:2016-12-25
    • 作者简介:
    • 朱皖宁,男,1983年生,安徽淮南人,博士,主要研究领域为量子计算与量子可逆逻辑综合.E-mail:granny025@163.com;陈汉武,男,1955年生,江苏南京人,博士,教授,主要研究领域为量子信息与量子计算技术.E-mail:hanwu_chen@163.com
    • 基金资助:
    • 国家自然科学基金 (No.61170321,No.61502101); 高等学校博士学科点专项科研基金 (No.20110092110024); 江苏省自然科学基金 (No.BK20140651); 金陵科技学院高层次人才科研启动基金 (No.jit-b-201624)

Grover Auto-Control Searching Algorithm

ZHU Wan-ning1,2, CHEN Han-wu2,3   

  1. 1. Department of Software Engineering, Jinling Institute of Technology, Nanjing, Jiangsu 211199, China;
    2. Department of Computer Science and Engineering, Southeast University, Nanjing, Jiangsu 210096, China;
    3. Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing, Jiangsu 210096, China
  • Received:2015-03-10 Revised:2016-05-10 Online:2016-12-25 Published:2016-12-25
    • Supported by:
    • National Natural Science Foundation of China (No.61170321, No.61502101); Research Fund for the Doctoral Program of Higher Education of China (No.20110092110024); Natural Science Foundation of Jiangsu Province,  China (No.BK20140651); Research Fund for High-level Talent of Jinling Institute of Technology (No.jit-b-201624)

摘要:

本文提出了利用相位门自动控制Grover搜索算法迭代次数的算法.Grover搜索算法最终得到目标分量的概率非常依赖于酉算子迭代的次数.迭代次数的计算依赖于目标分量的数量.因此当目标分量数未知时,该方法无法以高概率测量到目标分量.在以往的解决方案中需要较高的Oracle查询复杂度才能以一定概率得到目标分量的数量.本文提出了一种通过判断叠加态相位正负性,可自动控制Grover搜索算法迭代次数的方法.只需要添加一个判断相位的门电路,仅增加一次Oracle查询次数就可以精确的在最优迭代次数时停止Grover搜索算法,在搜索空间较小时可比原算法有更大的概率得到目标分量.

关键词: Grover搜索算法, 相位正负性, 自动控制

Abstract:

This paper presents an improved Grover searching algorithm which can automatically control the iterative processing when the number of target states is unknown.The probability of success of Grover searching algorithm depends on the number of iteration times and the number of the time of iterations relies on the number of target states.Therefore,it is hard to get the target state with high probability when the number of target states is unknown.To this question,the time complexity of conventional solution is high and the answer is non-deterministic.This paper shows an improved Grover searching algorithm,which is based on the sign for the phases of superposition state.Compared to existing research results,this algorithm can always stop the Grover iterations when the number of iteration times is optimal by the cost where just one more gate,and one more time Oracle call are needed to judge the sign of phase.

Key words: Grover searching algorithm, sign of phase, auto-control

中图分类号: