If quantum computation is reversible, what is the point of Grover's search algorithm?

Question

Wikipedia et al say the following about Grover's algorithm:

Although the purpose of Grover's algorithm is usually described as “searching a database”, it may be more accurate to describe it as “inverting a function”. Roughly speaking, if we have a function $y=f(x)$ that can be evaluated on a quantum computer, Grover's algorithm allows us to calculate $x$ when given $y$.

However, since all quantum computation is reversible, can't one simply run the inverse of each step in $f$ in reverse in order to obtain $x$ from $y$?

Answer 1

Not really. Quantum computations are reversible in a very specific sense, which is not amenable to what you are thinking of. Suppose you want to compute a function $f$ of some bitstring $x$. Then you encode the bitstring into the state $\newcommand{\ket}[1]{|#1\rangle}\ket{x}$ of your registry and append a "blank" qubit to get $\ket{x}\ket{0}$. Applying $f$ in quantum computation means applying the unitary $U_f$ which performs the transformation $$ \ket{x}\ket{0}\mapsto U_f\ket{x}\ket{0}=\ket{x}\ket{f(x)} $$ for all computational-basis states $\ket{x}$.

Since $U_f$ is unitary, you can invert the computation, which will take states of the form $\ket{x}\ket{f(x)}$ into the original $\ket{x}\ket{0}=U_f^{-1}\ket{x}\ket{f(x)}$. The reason this doesn't fly, of course, is that you need to know $x$ for this to work! If you try to apply $U_f^{-1}$ to some arbitrary state such as $\ket{000\cdots0}\ket{1}$, then unless $f(000\cdots 0)=1$ you will get some rather complicated superposition as a result, and you can't fish inside this superposition without (of course!) performing, essentially, Grover's algorithm.

Answer 2

No, you cannot run it in reverse if you are going to get an answer using a quantum computer. Even though the intermediate step with quantum gates are reversible. It can be easily understood by the following general quantum algorithm:

1. Preparing an initial state $\left|\psi\right\rangle$
2. Get the final state $\left|\phi\right\rangle = U\left|\psi\right\rangle$ with a big unitary operator $U$
3. Measure the state $\left|\phi\right\rangle$

The physical measurement in step 3 is obviously not reversible since the final state is now collapsed to a particular value. This value cannot be used to reconstruct the state $\left|\phi\right\rangle$ and so the whole computation is not reversible.

If there is an algorithm such that both states $\left|\psi\right\rangle$ and its answer $\left|\phi\right\rangle$ are not in superposition state, we can certainly construct the state and run the reverse of $y=f(x)$. However, in this case you dont need a quantum computer, you just need a classical computer with all quantum gates replaced by classical gates.

Note that the step 2 can be reversed $\left|\psi\right\rangle = U^{-1}\left|\phi\right\rangle$, but it is not useful. In most algorithm, the initial state $\left|\psi\right\rangle$ is some kind of uniform superposition of all possible state to gain the power of "parallel processing". You definitely dont want to run it in reverse, because you already know the initial state.

Actually, most function are not trivial invertible. You should not only look for those algebraical function and continuous function, which only form a tiny subset of all possible function. In computer science, they are usually considering the function $f:\{0,1\}^n \to \{0,1\}$ which has total number of $2^{2^n}$ functions. For a simple example, lets consider the following permutation map $g:\{1,2,3,4\}\to\{1,2,3,4\}$ $$f(1)=3, f(2)=1, f(3)=4, f(4)=2$$ In this example, you should see that it is not possible to figure out the inverse mapping until you go through all 4 possible values.

Answer 3

Yes you can invert it in principle. But here is the issue, Wikipedia says it is possible, but what it does not tell you is how hard it is to do it in practice. If $f$ is very simple then you need not a search algorithm. But when it is complicated it might not be easy to see how one can construct a new physical system that will invert the function.

Grover's algorithm is a practical implementation of the inverse that is general in the sense that you can just stick in a function and trust it will work and takes less physical time to perform than the best classical general implementation of the same. That's why you use the algorithm.

As an aside, notice that the same is true for much of classical physics. If you have a physical system calculating $f$ then in principle the evolution of that system is invertible. But if somebody told you "OK, then invert it" you would probably be stumped as to how to proceed (after all you can't just say let's run time backwards). So you construct an algorithm that effectively arrives at the same answer (although not necessarily in the physically inverted sense).

Answer 4

In fact, unless you're considering input strings of one bit in length, the function $f$ has no inverse. For either $f(x) = 0$ or $f(x) = 1$, there will be more than one input value of $x \in \{0,1\}^n$ which satisfies it; this is exactly what it means for $f$ not to be invertible.

Of course, if $n = 1$, then $f$ could be invertible, but then it only takes two queries both to find out if it is, and to find its inverse function. (If you only want to know whether it is invertible, you can do this in one query — this is exactly the same as Deutsch's problem.)

More generally, if you have a value of $y$, Grover's algorithm will allow you to obtain one of the values $x$ such that $y = f(x)$, uniformly at random. This is true even of non-invertible functions — which unitary quantum circuits can compute, despite the fact that those circuits are reversible. This is because to remain reversible, it suffices not to overwrite any information. There are classic proofs that quantum computers can compute any function (including irreversible ones) which a normal Turing machine or boolean circuit can compute, using the Toffoli gate (a reversible gate which is universal for classical computation).