Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (18): 54-55.DOI: 10.3778/j.issn.1002-8331.2009.18.017

• 研究、探讨 • Previous Articles     Next Articles

Improved quantum multi-object search algorithm

ZHONG Pu-cha,BAO Wan-su,WEI Yun   

  1. Institute of Electronic Technology,the PLA Information Engineering University,Zhengzhou 450004,China
  • Received:2008-04-15 Revised:2008-07-04 Online:2009-06-21 Published:2009-06-21
  • Contact: ZHONG Pu-cha

改进的多目标元素量子搜索算法

钟普查,鲍皖苏,隗 云   

  1. 解放军信息工程大学 电子技术学院,郑州 450004
  • 通讯作者: 钟普查

Abstract: Grover’s quantum mechanical search algorithm solves the unsorted database search with quadratic speed-up over the classical algorithms.But Grover’s algorithm will be inefficient when the number of matching is close to 2n/2.This paper presents a quantum algorithm which can get a target item with certainty by a single query when the number of the target items is more than a quarter.

Key words: quantum computing, quantum algorithm, Grover algorithm, arbitrary phase

摘要: Grover量子搜索算法解决了未加排序的数据库搜索问题,在2n个元素中搜索M个目标元素,其计算复杂度为O((2n/M-2),相对于经典算法实现了二次加速,但是,当目标元素个数接近2n/2时该算法成功率只达到50%。从任意相位的Grover变换从发,给出一种改进的多目标元素量子搜索算法,该算法在目标元素个数M≥2n/4时,只用一次Grover变换就能以概率1完成搜索。

关键词: 量子计算, 量子算法, Grover算法, 任意相位