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 Grovers algorithm and show that the square-root speed-up is the best attainable result using Grovers oracle.
Download