If quantum computation is reversible, what is the point of Grover's search algorithm?
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.
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:
- Preparing an initial state $\left|\psi\right\rangle$
- Get the final state $\left|\phi\right\rangle = U\left|\psi\right\rangle$ with a big unitary operator $U$
- 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.
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).