A fast quantum mechanical algorithm for database search
| dc.creator | Grover, Lov K. | |
| dc.date | 1996-05-29 | |
| dc.date | 1996-11-19 | |
| dc.date.accessioned | 2026-07-07T09:05:09Z | |
| dc.date.available | 2026-07-07T09:05:09Z | |
| dc.description | 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. | |
| dc.description | 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 | |
| dc.identifier | https://arxiv.org/abs/quant-ph/9605043 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/9605043 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/149624 | |
| dc.subject | Quantum Physics | |
| dc.title | A fast quantum mechanical algorithm for database search | |
| dc.type | text |