A question about performing quantum computations on uniform superpositions

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^*$).