4
$\begingroup$

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.

$\endgroup$
1
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.