量子搜索算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

Supported by National Natural Science Foundation of China under Grant Nos.60073039, 60273080 (国家自然科学基金); the Science and Technology Development Program of Jilin Provience of China under Grant No.20020306 (吉林省科技发展计划); the Foundation of Innovation of Jilin University of China(吉林大学创新基金)


A Quantum Search Algorithm
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    结合Grover和Tad Hogg的算法框架,叙述了量子算法中非结构化和结构化的两类搜索算法的设计思想.在Grover算法中,结合复杂性、临界点、非单调性、完备性和鲁棒性分析总结了一些性质,分析了Grover算法的优缺点.在Tad Hogg算法中对独立于问题的映射和相位调整分别作了介绍.重点分析了一种相位调整策略,解释该策略有效的原因和适用的场合,讨论了影响算法效率的因素.在上述论述的基础上对量子搜索算法与传统搜索算法进行了比较和分析,总结了隐藏在不同量子搜索算法背后的深刻思想.

    Abstract:

    In this paper, an important idea of devising a quantum algorithm is introduced, based on the description and analysis of two classes of quantum search algorithms, i.e. the unstructured search algorithms and structured search algorithms. Some qualities of Grover’s search algorithm, which is the representation of the unstructured search algorithms are introduced and summarized, by analyzing its peculiar complexity, completeness, sensitivity to the errors in the mappings, and its advantages and disadvantages. On introducing structure-based search algorithm, the Tad Hogg’s series of search algorithms are referred to. They can be summarized into one universal algorithm framework, which can be separated into two parts, i.e., the problem-independent mapping and phase rotation matrix. This paper places emphasis on analyzing one of the phase adaptation strategies, and interprets how it works and what can make it more efficient. Some other factors affect the algorithm are also discussed more generally. Finally, based on the comparison and analysis of classical search algorithm and the quantum one, the thoughts behind various quantum search algorithms are illustrated.

    参考文献
    相似文献
    引证文献
引用本文

孙吉贵,何雨果.量子搜索算法.软件学报,2003,14(3):334-344

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2002-01-28
  • 最后修改日期:2002-01-28
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号