Quantum mechanics helps in searching for a needle in a haystack

被引:3174
作者
Grover, LK
机构
[1] Bell Labs, Murray Hill, NJ, 07974, 3C-404A
关键词
D O I
10.1103/PhysRevLett.79.325
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
Quantum mechanics can speed up a range of search applications over unsorted data. For example, imagine a phone directory containing N names arranged in completely random order. To find someone's phone number with a probability of 50%, any classical algorithm (whether deterministic or probabilistic) will need to access the database a minimum of 0.5N times. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. As a result, the desired phone number can be obtained in only O(root N) accesses to the database.
引用
收藏
页码:325 / 328
页数:4
相关论文
共 9 条
  • [1] [Anonymous], P ROYAL SOC LONDON A
  • [2] Efficient networks for quantum factoring
    Beckman, D
    Chari, AN
    Devabhaktuni, S
    Preskill, J
    [J]. PHYSICAL REVIEW A, 1996, 54 (02): : 1034 - 1063
  • [3] BOYER M, QUANTPH9605034
  • [4] Quantum computing - Searching a quantum phone book
    Brassard, G
    [J]. SCIENCE, 1997, 275 (5300) : 627 - 628
  • [5] DURR C, QUANTPH9602016
  • [6] QUANTUM-MECHANICAL INTERACTION-FREE MEASUREMENTS
    ELITZUR, AC
    VAIDMAN, L
    [J]. FOUNDATIONS OF PHYSICS, 1993, 23 (07) : 987 - 997
  • [7] Grover L K., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. STOC'96, P212, DOI [DOI 10.1145/237814.237866, 10.1145/237814.237866]
  • [8] GROVER LK, QUANTPH9607024
  • [9] SHOR PW, 1994, AN S FDN CO, P124