A fast quantum mechanical algorithm for database search
Lov K. Grover · ACM Symposium on Theory of Computing (STOC) · 1996
An unsorted database contains N records, of which just one satisfies a particular property.The problem is to identify that one record.Any classical algorithm, deterministic or probabilistic, will clearly take O (N) steps since on the average it will have to examine a large fraction of the N records.Quantum mechanical systems can do several operations simultaneously due to their wave like properties.This paper gives an O ( JN) step quantum mechanical algorithm for identifying that record.It is within a constant factor of the fastest possible quantum mechanical algorithm.
Cited by 8,636 works. doi:10.1145/237814.237866 Open-access PDF
Authors
References
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Algorithms for quantum computation: discrete logarithms and factoring
- Scheme for reducing decoherence in quantum computer memory
- Rapid solution of problems by quantum computation
- Quantum complexity theory
- Strengths and Weaknesses of Quantum Computing
- Tight Bounds on Quantum Searching
- The Emperor's New Mind
- On the power of quantum computation
- The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines