A fast quantum mechanical algorithm for database search

Lov K. Grover · 1996 · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (STOC ‘96)

| 编号 QAPP001 | 主题 应用 | 链接 arXiv:quant-ph/9605043 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

Imagine a phone directory containing N names arranged in completely random order. In order to find someone’s phone number with a 50% probability, any classical algorithm (whether deterministic or probabilistic) will need to look at a minimum of N/2 names. 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(sqrt(N)) steps. The algorithm is within a small constant factor of the fastest possible quantum mechanical algorithm. 8 pages, single postscript file. This is an updated version of a paper that was originally presented at STOC 1996. The algorithm is the same; however, the proof has been simplified by using a new interpretation termed “inversion about average.” Also a few recently discovered insights have been added. Journal Ref.: Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC), May 1996, pages 212-219

本站词条在引用该文献时，会以 wikilink（sources/QAPP001）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。