2
$\begingroup$

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.

Please help. Thank you.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ There you go: ocw.mit.edu/courses/mathematics/…. $\endgroup$
    – Yuval Filmus
    May 8, 2017 at 17:39
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    May 8, 2017 at 17:41

1 Answer 1

Reset to default
4
$\begingroup$

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.

So Grover's algorithm is very very widely applicable. But unfortunately it also only gives a quadratic advantage, so "applicable" often doesn't translate into "useful". For example, the space of (reasonably sized) possible Riemann-hypothesis proofs is so huge that it laughs at square roots.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you Craig! So now I get the point of the algorithm, but it gives rise to another query. How is this oracle actually implemented/modelled? $\endgroup$
    – Srajan Jain
    May 9, 2017 at 18:38
  • 1
    $\begingroup$ @SrajanJain You compile the function into a classical reversible circuit made of NOT/CNOT/CCNOT gates, apply that circuit using the search-bits as the input, hit the output bit with a Z gate, then un-apply the circuit. $\endgroup$
    – Craig Gidney
    May 9, 2017 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.