What is the point of Grover's algorithm, really?

Question

This is a question desguised as a rant. There is a similar question here, What's the point of Grover's algorithm if we have to search the list of elements to build the oracle?, but the answers have not helped me much.

I have seen a few explanations of Grover's algorithm. I do not understand it, and the problem is not the mathematics. The story told by the sources is: given states $|x\rangle$ and $|\psi\rangle$, there is an operator $U$ such that you apply it so many times to $|\psi\rangle$ and the result is $|x\rangle$.

Surely the point of the algorithm is not to turn $|\psi\rangle$ into $|x\rangle$, is it?

If it is, then it should be called Grover's transformation, not Grover's search. And for that I have a much simpler algorithm: just apply the operator $\frac{|x\rangle\langle x|}{\langle x|\psi\rangle}$ (it requires a single run and works with 100% efficiency). Why is this not acceptable?

I have seen an analogy with phones. Suppose you want to find out who owns a particular phone number. Classically you must search the entire phone book (this analogy is getting out of touch with reality, but never mind that for the moment). Fine. So in the quantum setting I suppose you might have the state $|\psi\rangle$ which is your phone book, written in terms of energy eigenstates as $|\psi\rangle=\frac{1}{\sqrt{N}}\sum_i|\phi_i\rangle$, and you might ask "who is the state in there with energy $E_i$?", and the answer should be $\phi_i$.

But if I must know $|\phi_i\rangle$ in order to build the Grover operator $U$, then I see no point. Can I create $U$ without knowing $|\phi_i\rangle$ beforehand?

Answer 1

The point is indeed to "turn $|\psi\rangle$ into $|x\rangle$". More precisely, the point is to transform a given $|\psi\rangle$ into some (unknown) state $|x\rangle$ which is defined as satisfying some properties (i.e. it is "marked" by some oracle). Even more precisely, the point is to transform $|\psi\rangle$ into some state which, when measured, gives you a string that with good probability is the $x$ which solves whatever problem you are facing.

You can call it "Grover's transformation" if you wish. It is indeed a "transformation"; but then again, any algorithm is a transformation in the same sense. It makes sense to call it a "search algorithm" when you think about the result it gives you. If you use it to, say, find the solution to some SAT problem, it gives you as answer some string that satisfies specific properties. You can think of these questions as more complex versions of something like "find the 3-bit string such that the sum of the first two bits is 0". This looks very much like a "search" to me.

Note that the solution to the "search" is obtained when you measure the final state, and thus obtain a classical string out of it. In other words, the "state transformation" part of the algorithm is such that the state it gives you, when measured, encodes the solution to the search problem.

Why not just apply the operator $|x\rangle\!\langle x|$?

That would be useless. "Applying the operator $|x\rangle\!\langle x|$" means to measure the state $|\psi\rangle$ in some measurement basis containing $|x\rangle$. This amounts to asking the question "what is the probability that the initial state $|\psi\rangle$ is found in the state $|x\rangle$ (assuming some suitable choice of measurement basis)?". That's not what you want. The goal is to find an $|x\rangle$ such that $f(x)=1$ for some given function $f$ (called the "oracle" in this context). You do not know what this $x$ is, otherwise you'd already know the solution to the problem.

But if I must know $|ϕ_i⟩$ in order to build the Grover operator $U$, then I see no point. Can I create $U$ without knowing $|ϕ_i⟩$ beforehand?

Yes, that's the point. The oracle encodes the constraints that you want the solution to satisfy, not the solution itself.

If I tell you to find the needle in the haystack, do you know beforehand where the needle is? No, you know that you need to search through many locations until you find the location containing the needle. It's the same thing: in this analogy, each $|x\rangle$ is a position potentially containing the needle, and the oracle is the function that checks whether a given position contains the needle.

This has been discussed multiple times in the site, see e.g. Does the oracle in Grover's algorithm need to contain information about the entirety of the database?.

Answer 2

Can I create $U$ without knowing $|\phi_i\rangle$ beforehand?

Yes. For example, you could write down a sudoko grid with a few random hints, define $|\phi_i\rangle$ to be any solution (if one exists), and $U$ could check if a given filling of the grid is a solution matching the hints.

Answer 3

Grover's algorithm is a CIRCUIT-SAT solver. Given a circuit with $n$ boolean inputs, it finds a satisfying input in $O(2^{n/2})$ evaluations of the circuit in the worst case, which is interesting because no classical algorithm is known that does better than $O(2^n)$, and it's conjectured that none exists.

Lov Grover decided to call it a database search algorithm in his original paper, and there's a tendency for arbitrary terminological choices made in pioneering papers to become standards whether they make sense or not. So I suppose it will forever be taught as a database search algorithm, and students will forever be confused by it as they quite reasonably wonder how this "database" is encoded in the circuit and why you wouldn't just index it for $O(n)$ lookup while you're at it.

Don't try to understand the "database". Just forget about it. Grover's algorithm is a CIRCUIT-SAT solver.