# A question about performing quantum computations on uniform superpositions

Let us consider the following situation. Let $$U_f$$ be a gate computing $$f$$ mapping $$\{0,1\}^n$$ to $$\{0,1\}^n$$. That is, $$U_f\left\vert x,0^n\right\rangle=\left\vert x,f(x)\right\rangle$$. Let $$\left\vert\phi\right\rangle$$ be the uniform superposition on $$\{0,1\}^n$$. By performing $$U_f$$ on $$\left\vert\phi\right\rangle\left\vert0^n\right\rangle$$, we have $$\left\vert\phi'\right\rangle=\sum_{x\in\{0,1\}^n}\frac1{2^{n/2}}\left\vert x,f(x)\right\rangle$$. Let $$x^\ast$$ be some specific state $$x^\ast\in\{0,1\}^n$$.

My question is: is it possible to obtain $$f(x^\ast)$$ from performing some gates or projections on $$\left\vert\phi'\right\rangle$$ (without running $$U_f$$ again) with overwhelming probability? Or, particularly, is it possible to obtain $$f(0^n)$$ from $$\left\vert\phi'\right\rangle$$? Does Hadamard gate work in this situation?

I guess no, but I wonder there is something I have missed.

You could run Grover's algorithm on the top $$n$$ bits of the register for $$2^{n/2}$$ steps, but this is probably less efficient than you were hoping for.
Anything better than Grover is unlikely to work (I'm not sure how far Zalka's no-go result in "Grover's quantum searching algorithm is optimal" extends into the following). Such an algorithm would be enough to invert an arbitrary permutation on $$\mathbb F_2^n$$ (and hence any permutation as a corollary). To see this suppose we are endowed with a circuit $$U_\pi$$ to evaluate our mystery permutation $$\pi(x)$$. We create the state $$|\phi\rangle|0^n\rangle$$ and apply $$U_\pi$$ to obtain $$|\psi\rangle:=\sum 2^{-n/2}|x\rangle|\pi(x)\rangle$$. Note that the final $$n$$ bits are in state $$|\phi\rangle$$ because $$\pi$$ is a permutation. If swap the first and second half of the registers we then have $$\sum 2^{-n/2}|x\rangle|\pi^{-1}(x)\rangle$$ and running our putative algorithm for your problem will allow us to compute $$\pi^{-1}(x^*)$$ for any $$x^*$$. Restricting to the case $$0^n$$ does to reduce the power of such an algorithm by considering the function (resp. permutation) $$f(x\oplus x^*)$$ (resp. $$\pi(x)\oplus x^*$$).