Quantum computers can search arbitrarily large databases by a single query

被引:343
作者
Grover, LK
机构
[1] 3C-404A Bell Labs, Murray Hill, NJ, 07974
关键词
D O I
10.1103/PhysRevLett.79.4709
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database can search a database for a unique item satisfying a given condition, in a single query [a query is defined as any question to the database to which the database has to return a (YES/NO answer]. A classical algorithm will be Limited to the information theoretic bound of at least log(2) N queries, which it would achieve by using a binary search.
引用
收藏
页码:4709 / 4712
页数:4
相关论文
共 8 条
  • [1] TIME-SPACE TRADE-OFFS FOR REVERSIBLE COMPUTATION
    BENNETT, CH
    [J]. SIAM JOURNAL ON COMPUTING, 1989, 18 (04) : 766 - 776
  • [2] Strengths and weaknesses of quantum computing
    Bennett, CH
    Bernstein, E
    Brassard, G
    Vazirani, U
    [J]. SIAM JOURNAL ON COMPUTING, 1997, 26 (05) : 1510 - 1523
  • [3] BOYER M, IN PRESS FORTSCHR PH
  • [4] Feller W., 1991, An Introduction to Probability Theory and Its Applications, V1 and 2
  • [5] FELLER W., 1971, INTRO PROBABILITY TH, V1
  • [6] GROVER LK, 1997, PHYS REV LETT, V78, P325
  • [7] KNUTH D, 1973, FUNDAMENTALS ALGORIT, V1
  • [8] TERHAL BM, QUANTPH9705041