迭代次数自适应的Grover算法

doi:10.3969/j.issn.0372-2112.2016.12.023

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

迭代次数自适应的Grover算法

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

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-ning^1,2, CHEN Han-wu^2,3

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)

摘要/Abstract

摘要：

本文提出了利用相位门自动控制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

中图分类号:

朱皖宁, 陈汉武. 迭代次数自适应的Grover算法[J]. 电子学报, 2016, 44(12): 2975-2980.

ZHU Wan-ning, CHEN Han-wu . Grover Auto-Control Searching Algorithm[J]. Acta Electronica Sinica, 2016, 44(12): 2975-2980.

参考文献

[1] Shor P W.Algorithms for quantum computation:discrete logarithms and factoring[A].Proceedings of the 35th Annual Symposium on foundations of Computer Science[C].Santa Fe,NM:IEEE,1994.124-134.
[2] GroverL K.A fast quantum mechanical algorithm for database search[A].Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing[C].Philadelphia,USA:ACM,1996.212-219.
[3] Grover L K.Quantum mechanics helps in searching for a needle in a haystack[J].Physical Review Letters,1997,79(2):325-328.
[4] Grover L K.Quantum computers can search rapidly by using almost any transformation[J].Physical Review Letters,1998,80(19):4329-4332.
[5] Long G L,Li Y S,Zhang W L,et al.Dominant gate imperfection in Grover's quantum search algorithm[J].Physical Review A,2000,61(4):042305.
[6] Biron D,Biham O,Biham E,et al.Generalized Grover search algorithm for arbitrary initial amplitude distribution[A].Quantum Computing and Quantum Communications[C].Palm Springs,CA:Springer Berlin Heidelberg,1999.140-147.
[7] Chuang I L,Gershenfeld N,Kubinec M.Experimental implementation of fast quantum searching[J].Physical Review Letters,1998,80(15):3408-3411.
[8] Boyer M,Brassard G,Høyer P,et al.Tight bounds on quantum searching[OL].arXiv Preprint Quant-ph/9605034,1996.
[9] Michael A Nielsen,Isaac L Chuang.Quantum Computation and Quantum Information[M].British:Cambridge University Press,2000.240-243.
[10] Daniel Reitzner,Daniel Nagaj,Vladimir Buzek.Quantum walks[J].Acta Physica Slovaca,2011,61(6):603-725.
[11] 金文梁,陈向东.相位不匹配的量子搜索算法[J].电子学报,2012,40(1):189-192. Jin Wenliang,Chen Xiangdong.Phase-unmatched quantum search algorithm[J].Acta Electronica Sinica,2012,40(1):189-192.(in Chinese)
[12] Zalka Christof.Using Grover's quantum algorithm for searching actual databases[J].Physical Review A,2000,62(5):052305-052301.
[13] Yamashita S.How to utilize a Grover search in general paogramming[J].Laser Physics,2006,16(4):730-734.
[14] 阮越,陈汉武,刘志昊,等.量子主成分分析算法[J].计算机学报,2014,37(3):666-676. Ruan Yue,Chen Hanwu,Liu Zhihao.Quantum principal component analysis algorithm[J].Chinese Journal of Computers,2014,37(3):666-676.(in Chinese)
[15] 彭宏,荆晶.无线自组织量子通信网络的Grover路由算法研究[J].浙江工业大学学报,2014,42(6):612-615. Peng Hong,Jing Jing.Research on routing algorithm of Grover for wireless ad hoc quantum communication network[J].Journal of Zhejiang University of Technology,2014,42(6):612-615.(in Chinese)
[16] 孙国栋,苏盛辉,徐茂智.求根问题的量子计算算法[J].北京工业大学学报,2015,41(3):366-371. Sun Guodong,Su Shenghui,Xu Maozhi.Quantum mechanical algorithms for solving root finding problem[J].Journal of Beijing University of Technology,2015,41(3):366-371.(in Chinese)
[17] Shenvi N,Kempe J,Whaley R B.A quantum random walk search algorithm[J].Physical Review A,2003,67(5):052307.
[18] Aaronson S,Ambainis A.Quantum search of spatial regions[A].Proceedings of 44th Annual IEEE Symposium on Foundations of Computer Science[C].MA,USA:IEEE,2003.200-209.
[19] Ambainis A,Kempe J,Rivosh A.Coins make quantum walks faster[A].Proceedings of 16th ACM-SIAM SODA[C].British Columbia,Canada:ACM,2005.1099-1108.
[20] Ambainis A.Quantum walk algorithm for element distinctness[A].Proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)[C].Rome,Italy:IEEE,2004.22-31.
[21] Childs A M,Eisenberg J M.Quantum algorithms for subset finding[J].Quantum Information and Computation,2005,5(7):593-604.
[22] Dorner U,Demkowicz-Dobrzanski R,Smith B J,et al.Optimal quantum phase estimation[J].Physical Review Letters,2009,102(4):040403.
[23] Hradil Z.Phase measurement in quantum optics[J].Quantum Optics:Journal of the European Optical Society Part B,1992,4(2):93-110.

迭代次数自适应的Grover算法

Grover Auto-Control Searching Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics