• Article
  • | |
  • Metrics
  • |
  • Reference [35]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    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.

    Reference
    [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.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:4301
  • PDF: 6877
  • HTML: 0
  • Cited by: 0
History
  • Received:January 28,2002
  • Revised:January 28,2002
You are the first2034825Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063