第1期 李盼池，等：一种Grover量子搜索算法的改进策略 ·39· ③正确结果的概率 [7]BIHAM E,KENIGSBERG D.Grover's quantum search 5 2 algorithm for an arbitrary initial mixed state [J].Physi- P=19 32 =0.2319. cal Review A,2002,66(6):2301.2304. [8]BIHAM O,SHAPIRA D,SHIMONI Y.Analysis of 4 结束语 Grover's quantum search algorithm as a dynamical system 针对目前Grover算法随着目标数增多，搜索概 [U].Physical Review A,2003,68(2):2326-2333. [9]VENTURA D,MARTIN EZ T.Quantum associative 率迅速下降直至算法失效的问题，文中提出了一种 memory [J ]Information Sciences,2000(124):273- 新的相位匹配策略，不同于文献[5]的结论，该策略 296. 使算法中2次相移大小相等方向相反.该策略较好 [10]EZHOV A,NIFANOVA A,VENTURA D.Quantum 地解决了目前Grover算法中存在的上述问题.算例 associative memory with distributed queries [J ]Infor- 证明，该策略是有效的.在搜索目标较多时如何进一 mation Sciences,2000(128):271-293. 步提高成功搜索的概率，以及如何将Grover量子搜 [11]李士勇，李盼池.基于实数编码和目标函数梯度的量子 索算法与梯度量子遗传算法川融合是下一步要解 遗传算法[U],哈尔滨工业大学学报，2006,38(8)： 决的问题 1216-1218 LI Shiyong,LI Panchi.A quantum genetic algorithm 参考文献： based on real encoding and gradient information of ob- [1]GROVER L K.A fast quantum mechanical algorithm for ject function [J].Journal of Harbin Institute of Tech- nology,2006,38(8):1216-1218 database search [A ]Proceedings of the 28th Annual 作者简介： ACM Symposium on the Theory of Computing [C]. 李盼池，男，1969年生，副教授，博 Pennsylvania,1996. 士研究生，主要研究方向为量子计算、 [2]SHOR P W.Algorithms for quantum computation:dis 智能优化算法及其在智能控制、智能信 crete logarithms and factoring [A].Proceedings of the 息处理、模式识别等方面的应用.发表 35th Annual Symposium on the Foundation of Computer 学术论文多篇。 Science [C].Los Alamitos,1994. [3]NIEL SEN M A,CHUANG IL.Quantum computation Email:lipanchi @vip.sina.com. and quantum information [M].London:Cambridge Uni- versity Press,2000. 李士勇，男，1943年生，教授，博士 [4]GROVER L K.Quantum computers can search rapidly 生导师，主要研究方向为模糊控制、神经 by using almost any transformation [J].Physical Review 控制、智能控制、智能优化算法，非线性 Letters,1998,80(29):4329-4332. 科学与复杂性科学等.中国自动化学会 5]LONG GL,LI Y S,ZHANG WL,et al.Phase matc- hing in quantum searching[J].Physics Letters A,1999, 智能自动化专业委员会委员，《计算机测 量与控制》编委.编著教材与专著共5 26(10):27-34. [6]BIHAM E,BIHAM O,BIRON D,et al.Grover's quam 部，在国内外发表学术论文120余篇。 E mail:Isy @hit.edu.cn tum search algorithm for an arbitrary initial amplitude distribution [J].Physical Review A,1999,60(4):2742 .2745. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net③正确结果的概率 P = 19 5 32 2 2 = 01231 9. 4 结束语 针对目前 Grover 算法随着目标数增多 ,搜索概 率迅速下降直至算法失效的问题 ,文中提出了一种 新的相位匹配策略 ,不同于文献[ 5 ]的结论 ,该策略 使算法中 2 次相移大小相等方向相反. 该策略较好 地解决了目前 Grover 算法中存在的上述问题. 算例 证明 ,该策略是有效的. 在搜索目标较多时如何进一 步提高成功搜索的概率 ,以及如何将 Grover 量子搜 索算法与梯度量子遗传算法[ 11 ] 融合是下一步要解 决的问题. 参考文献 : [ 1 ] GROV ER L K. A fast quantum mechanical algorithm for database search [ A ]. Proceedings of the 28th Annual ACM Symposium on the Theory of Computing [ C ]. Pennsylvania , 1996. [2 ]SHOR P W. Algorithms for quantum computation : dis2 crete logarithms and factoring [ A ]. Proceedings of the 35th Annual Symposium on the Foundation of Computer Science [C]. Los Alamitos , 1994. [3 ]NIELSEN M A , CHUAN G I L. Quantum computation and quantum information [ M]. London : Cambridge Uni2 versity Press , 2000. [4 ] GROV ER L K. Quantum computers can search rapidly by using almost any transformation [J ]. Physical Review Letters ,1998 , 80 (29) : 4329 - 4332. [5 ]LON G G L , L I Y S , ZHAN G W L , et al. Phase matc2 hing in quantum searching [J ]. Physics Letters A ,1999 , 26 (10) :27 - 34. [6 ]BIHAM E , BIHAM O , BIRON D , et al. Grover’s quan2 tum 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 arbitrary initial mixed state [J ]. Physi2 cal Review A ,2002 ,66 (6) : 2301 - 2304. [8 ] BIHAM O , SHAPIRA D , SHIMONI Y. Analysis of Grover’s quantum search algorithm as a dynamical system [J ]. Physical Review A ,2003 , 68 (2) : 2326 - 2333. [ 9 ] V EN TURA D , MARTIN EZ T. Quantum associative memory [J ]. Information Sciences , 2000 ( 124) : 273 - 296. [10 ] EZHOV A , NIFANOVA A , V EN TURA D. Quantum associative memory with distributed queries [J ]. Infor2 mation Sciences ,2000 (128) : 271 - 293. [ 11 ]李士勇 , 李盼池. 基于实数编码和目标函数梯度的量子 遗传算法 [J ]. 哈尔滨工业大学学报 , 2006 , 38 ( 8) : 1216 - 1218. L I Shiyong , L I Panchi. A quantum genetic algorithm based on real encoding and gradient information of ob2 ject function [J ]. Journal of Harbin Institute of Tech2 nology ,2006 , 38 (8) : 1216 - 1218. 作者简介 : 李盼池 ,男 ,1969 年生 ,副教授 ,博 士研究生 ,主要研究方向为量子计算、 智能优化算法及其在智能控制、智能信 息处理、模式识别等方面的应用. 发表 学术论文多篇. E2mail : lipanchi @vip. sina. com. 李士勇 ,男 ,1943 年生 ,教授 ,博士 生导师 ,主要研究方向为模糊控制、神经 控制、智能控制、智能优化算法、非线性 科学与复杂性科学等. 中国自动化学会 智能自动化专业委员会委员《, 计算机测 量与控制》编委. 编著教材与专著共 5 部 ,在国内外发表学术论文 120 余篇. E2mail : lsy @hit. edu. cn 第 1 期 李盼池 ,等 :一种 Grover 量子搜索算法的改进策略 ·39 ·