A fast quantum mechanical algorithm for database search
Author:
- Lov K. GroverLGLov K. Grover
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Strengths and Weaknesses of Quantum ComputingSIAM Journal on Computing, 1997
- Quantum Seeing in the DarkScientific American, 1996
- Efficient networks for quantum factoringPhysical Review A, 1996
- Oracle Quantum ComputingJournal of Modern Optics, 1994
- Quantum mechanical interaction-free measurementsFoundations of Physics, 1993
- Rapid solution of problems by quantum computationProceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 1992
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- Quantum theory, the Church–Turing principle and the universal quantum computerProceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1985
- The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machinesJournal of Statistical Physics, 1980