Erdal Arikan
Published 2002-10-10, updated 2002-10-11Version 2
Grover discovered a quantum algorithm for identifying a target element in an unstructured search universe of N items in approximately square-root of N queries to a quantum oracle, thus achieving a square-root speed-up over classical algorithms. We present an information-theoretic analysis of Grover's algorithm and show that the square-root speed-up is the best attainable result using Grover's oracle.
Comments: 8 pages, 1 figure, minor corrections
Grover's algorithm on a Feynman computer
Asymptotically Improved Grover's Algorithm in any Dimensional Quantum System with Novel Decomposed $n$-qudit Toffoli Gate
Experimental requirements for Grover's algorithm in optical quantum computation
