[1]李盼池,李士勇.一种Grover量子搜索算法的改进策略[J].智能系统学报,2007,2(1):35-39.
LI Pan-chi,LI Shi-yong.An improved measure in Grover quantum searching algorithm[J].CAAI Transactions on Intelligent Systems,2007,2(1):35-39.
点击复制
LI Pan-chi,LI Shi-yong.An improved measure in Grover quantum searching algorithm[J].CAAI Transactions on Intelligent Systems,2007,2(1):35-39.
一种Grover量子搜索算法的改进策略
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
2
期数:
2007年第1期
页码:
35-39
栏目:
学术论文—人工智能基础
出版日期:
2007-02-25
- Title:
- An improved measure in Grover quantum searching algorithm
- 文章编号:
- 1673-4785(2007)01-0035-05
- Keywords:
- Grover algorithm; phase matching; quantum searching; quantum computing
- 分类号:
- TP18
- 文献标志码:
- A
- 摘要:
- 在使用Grover量子搜索算法对给定规模的数据库搜索时，随着搜索目标数的增加，获得正确结果的概率大幅度下降．分析了出现这种现象的原因，提出了一种基于新的相位匹配条件的改进策略．在新的相位匹配条件中，使2次相位旋转的大小相等方向相反．当要搜索的目标数目多于记录总数的1/3时，应用改进后的算法只需一步搜索，能以至少25/27的概率得到全部搜索目标．实验证明这种策略是有效的．
- Abstract:
- When the current Grover algorithm is applied to search some objects in an unsorted quantum database, the probability of correct objects usually falls with the increase of the searched objects. The reason for this problem is analyz ed in this paper, and an improved measure based on the new phase matching condit ion is proposed. In the new phase matching condition, the amplitudes of two phas e rotations are the same and the directions of two phase rotations are contrary . Whe n the objects are more than one third of the total items, with the new phase mat ching condition, all objects can be found by at least 25/27 of the probability a nd by the only one Grover iteration. The validity of the improved measure is pr oved by experiment.
- 参考文献/References:
-
［1］ GROVER L K. A fast quantum mechanical algorithm for database search ［A］.Proce edings of the 28th Annual ACM Symposium on the Theory of Computing ［C］. Pennsylvania, 1996.
［2］SHOR P W. Algorithms for quantum computation: discrete logarithms and fact oring［A］. Proceedings of the 35th Annual Symposium on the Foundation of Compu ter Science ［C］. Los Alamitos, 1994.
［3］NIELSEN M A, CHUANG I L. Quantum computation and quantum information ［M］ . London: Cambridge University Press, 2000.
［4］GROVER L K. Quantum computers can search rapidly by using almost any trans formation ［J］. Physical Review Letters,1998, 80(29): 4329-4332.
［5］LONG G L, LI Y S, ZHANG W L, et al. Phase matching in quantum searching［J ］.Physics Letters A，1999, 26(10):27-34.
［6］BIHAM E, BIHAM O, BIRON D, et al. Grover’s quantum search algorithm for an arbitrary initial amplitude distribution ［J］. Physical Review A，1999, 60(4): 2742-2745.
［7］BIHAM E, KENIGSBERG D. Grover’s quantum search algorithm for an arbit rary initial mixed state ［J］. Physical Review A，2002，66(6): 2301-2304.
［8］BIHAM O, SHAPIRA D, SHIMONI Y. Analysis of Grover’s quantum search al gorit hm as a dynamical system ［J］. Physical Review A，2003, 68(2): 2326 -2333.
［9］VENTURA D, MARTINEZ T. Quantum associative memory ［J］. Information Scien ces，2000(124): 273-296.
［10］EZHOV A, NIFANOVA A, VENTURA D. Quantum associative memory with distribut ed queries ［J］. Information Sciences，2000(128): 271-293
［11］李士勇, 李盼池. 基于实数编码和目标函数梯度的量子遗传算法［J］. 哈尔滨工业大学学报，2006, 38(8): 1216-1218.
?LI Shiyong, LI Panchi. A quantum genetic algorithm based on real encoding and gr adient information of object function ［J］. Journal of Harbin Institute of Tech nology，2006, 38(8): 1216-1218
备注/Memo
收稿日期：2006-05-18.
基金项目：国家自然科学基金资助项目（50138010）
作者简介：
李盼池，男，1969年生，副教授，博士研究生，主要研究方向为量子计算、智能优化算法及其在智能控制、智能信息处理、模式识别等方面的应用．发表学术论文多篇．
?E-mail: lipanchi@vip.sina.com.
李士勇，男，1943年生，教授，博士生导师，主要研究方向为模糊控制、神经控制、智能控制、智能优化算法、非线性科学与复杂性科学等．中国自动化学会智能自动化专业委员会委员，《计算机测量与控制》编委．编著教材与专著共5部，在国内外发表学术论文120余篇．
E-mail: lsy@hit.edu.cn
更新日期/Last Update:
2009-05-05