# How is Grover's Algorithm useful?

I am at a loss when it comes to understanding how Grover's Algorithm gives any useful information. Suppose we have a 4-qubit states (|0⟩ to |15⟩), and we are searching for the state |3⟩. The oracle would thus be O=I−2|3⟩⟨3|

And then, at the end, after all the amplitude amplification steps, we would get the state |3⟩ with a high probability, but does this give any new information, since we already used |3⟩ inside the oracle?

I know I am missing out something crucial, but I absolutely cannot put my finger on it.

• There you go: ocw.mit.edu/courses/mathematics/…. – Yuval Filmus May 8 '17 at 17:39
• Wikipedia is also very helpful here: "Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just $O(\sqrt{N})$ evaluations of the function, where $N$ is the size of the function's domain." What you're missing is the black box. – Yuval Filmus May 8 '17 at 17:41

The thing you're missing is that you aren't search for $|3\rangle$, you're searching for "the input that makes $f$ return true" where $f$ is some function.
For example, maybe $f$ is a discrete logarithm checker like $x \rightarrow 2^x \equiv^? 432821 \pmod{7438927891}$. Or $f$ could interpret its input as a claimed proof of the Riemann hypothesis, and check if that proof is correct. Anything you can imagine checking, $f$ could be that.