量子搜索算法
作者:
基金项目:

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
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [35]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    结合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.

    参考文献
    [1]Landauer R. Information is physical. Physics Today, 1991,44(5):23~29.
    [2]Feynman R. Simulating physics with computers. International Journal of Theoretical Physics, 1982,21:467~488.
    [3]Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London (series A), 1985,400:97~117.
    [4]Deutsch D. Quantum computational networks. Proceedings of the Royal Society of London (series A), 1989,425:73~90.
    [5]Yao A. Quantum circuit complexity. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 1993. 352~361.
    [6]Bernstein E, Vazirani U. Quantum complexity theory. In: Proceedings of the 25th ACM Symposium on Theory of Computating. 1993. 11~20.
    [7]Simon DR. On the power of quantum computation. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 1994. 116~123.
    [8]Shor PW. Algorithms for quantum omputation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science. Santa Fe: IEEE Computer Society Press, 1994. 124~134.
    [9]Shor PW. Polynomial-Time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal of Computing, 1997,26(5):1484~1509.
    [10]Jozsa R. Quantum algorithms and the Fourier transform. Proceedings of the Royal Society of London (series A), 1998,454:323~338.
    [11]Hogg T. Quantum computing and phase transitions in combinatorial search. Journal of Artificial Intelligence Research, 1996, 4:91~128.
    [12]Hogg T. A framework for structured quantum search. Physica D, 1998,120:102~116.
    [13]Hogg T. Highly structured searches with quantum computers. Physical Review Letters, 1998,80:2473~2476.
    [14]Hogg T. Solving highly constrained search problems with quantum computers. Journal of Artificial Intelligence Research, 1999,10: 39~66.
    [15]Hogg T, Yanik M. Local search methods for quantum computers. Technical Report, 1998.
    [16]Grover LK. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. 1996. 212~219.
    [17]Grover LK. A fast quantum mechanical algorithm for estimating the median. Technical Report, quant-ph/9607024, 1996.
    [18]Grover LK. Quantum Telecomputation. Technical Report, quant-ph/9704012, 1997.
    [19]Shor PW. Scheme for reducing decoherence in quantum computer memory. Physical Review A, 1995,52(4):R2493.
    [20]Shor PW. Fault-Tolerant quantum computation. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 1996. 56~65.
    [21]Brassard G, Hoyer P, Tapp A. Quantum counting. In: Proceedings of the 25th ICALP. Lecture Notes in Computer Science, Vol 1443, Berlin: Springer-Verlag, 1998. 820~831.
    [22]Zhang ZJ, Zhang ZL. Prime factorization in quantum computation. Physics, 2000,29(9):560~564 (in Chinese with English Abstract).
    [23]Boyer M, Brassard G, Hoyer P, Tapp A. Tight bounds on quantum searching. In: Proceedings of the Workshop on Physics of Computation: PhysComp'96. IEEE Computer Society Press, 1996.
    [24]Nielson MA, Chuang IL. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000.
    [25]Grover LK. A framework for fast quantum mechanical algorithms. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing. 1998. 53~62.
    [26]Bennett CH, Bernstein E, Brassard G, Vazirani U. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 1997,26(5):1510~1523.
    [27]Zalka. Grover's quantum searching algorithm is optimal. Physical Review A, 1999,60:2746~2751.
    [28]Jones JA, Mosca M, Hansen RH. Implementation of a quantum search algorithm on a quantum computer. Nature, 1998, 393:344~346.
    [29]Chuang IL, Gershenfeld N, Kubinec M. Experimental implementation of fast quantum searching. Physical Review Letter, 1998,80(15):3408~3411.
    [30]Grover LK. Quantum computers can search rapidly by using almost any transformation. Physical Review Letters, 1998,80(19): 4329~4332.
    [31]Long GL, Zhang WL, Li YS, Niu Li. Arbitrary phase rotation of the marked state can not be used for Grover's quantum search algorithm. Commun.Theor.Phys., 1999,32:335~338.
    [32]Ahn J, Weinacht TC, Bucksbaum PH. Information storage and retrieval through quantum phase. Science, 2000,287(5452):463~465.
    [33]Knight P. Hanced: quantum information processing without entanglement. Science, 2000,287(5452):441~442.
    [34]Peng XH, Zhu XW, Fang XM, Feng M, Liu ML, Gao KL. Experimental implementation of Hogg's algorithm on a three-quantum-bit NMR quantum computer. Technical Report, quant-ph/0108068, 2001.
    [35]张镇九,张昭理.量子计算中的因子分解.物理,2000,29(9):560~564.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

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

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

京公网安备 11040202500063号