Amplitude Amplification for searching $|0\rangle$ in an unknown state

Question

For one known (invertible) function that does: $$f:H^{\otimes 2n}\times H^{\otimes 2n}:|x⟩|0⟩\mapsto|x⟩|y⟩$$ I want to find a similar (invertible) function that does: $$g:H^{\otimes 2n}\times H^{\otimes2n}:|0⟩|y⟩\mapsto|x⟩|0⟩$$ so that $f \ast g$ maps $|0⟩|y⟩$ to $|x⟩|y⟩$.

To do so, I prepare a state $|0, y_x⟩$ and do the following operations: $$|0, y_x⟩ \mapsto \frac{1}{\sqrt{2^{n}}}(\sum^{2^n-1}_{k\,=\,0}|k⟩)|y_x⟩ = \frac{1}{\sqrt{2^{n}}}\sum^{2^n-1}_{k\,=\,0}|k⟩|y_x⟩ $$ Now apply $f^{-1}$ to $|k⟩|y_x⟩$, which gives: $$\frac{1}{\sqrt{2^{n}}}\sum^{2^n-1}_{k\,=\,0}f^{-1}(|k⟩|y_x⟩)=...+\frac{1}{\sqrt{2^{n}}}|x⟩|0⟩$$ I verfied that only when $k=x$, the second register of $f^{-1}(|k⟩|y_x⟩)$ contains $|0⟩$. Denote $|\varphi⟩$ as the state of second register. The only information I know, is that $|\varphi⟩$ contains $|0⟩$ with amplitude $\frac{1}{\sqrt{2^{n}}}$. Is that possible that I can use amplitude amplification to significantly increase the amplitude of $|0⟩$?

Answer 1

Yes this should be possible. We need to show that the final state you've prepared consists of two orthogonal components, and that one of these components contains all of the "good" solutions that can be recovered by measuring the second register - meaning that $0$ occurs in the second register only if $x$ occurs in the first register$^1$.

I'm going to use a different notation than you have for the sake of unitarity: Suppose we have an invertible $f: \{0,1\}^n \rightarrow \{0,1\}^n$ that we can query in superposition via $U_f$: \begin{equation}\tag{1} U_f |x\rangle |b\rangle \rightarrow |x\rangle |b\oplus f(x)\rangle \end{equation} for some $b\in \{0,1\}^n$, and since $f$ is invertible we query $f^{-1}$ via the unitary \begin{equation}\tag{2} U_f^\dagger |x\rangle |b\oplus f(x)\rangle \rightarrow |x\rangle |b\rangle \end{equation}

Starting with $|0\rangle |f(x)\rangle$ and applying $H^{\otimes n}$ (or more generally the QFT over $\mathbb{Z}_N$ if we don't restrict ourselves to qubits) followed by $U^\dagger$ we reach the state you mentioned \begin{align}\tag{3} |\psi\rangle &= \frac{1}{\sqrt{2^n}}|x\rangle |0\rangle + \frac{1}{\sqrt{2^n}}\sum_{z\neq x} U^\dagger |z\rangle|f(x)\rangle \\&= |\psi_a\rangle + |\psi_b\rangle \end{align}

Using (1) with $b=0$ we can easily verify that these two components are orthogonal \begin{align} \left(\langle x| \langle 0 | U^\dagger\right) |z\rangle|f(x)\rangle &= \left( \langle x | \langle f(x) | \right) |z\rangle|f(x)\rangle \\&= \delta_x^z \end{align} and since the sum in (3) omits $z=x$ then $\langle \psi_a | \psi_b \rangle = 0$. Now we want to check that $|x\rangle |0\rangle$ is the only component of $|\psi\rangle$ with $|0\rangle$ in the second register, so we check that $|\psi_b\rangle$ has zero amplitude to be in $|z'\rangle |0\rangle$ for $z' \in \{0,1\}^n$: \begin{align} \left(\langle z'| \langle 0 | U^\dagger\right) |z\rangle|f(x)\rangle &= \langle z' | z\rangle \langle f(z') | f(x) \rangle \\&= \delta_{z'}^z \delta_{z'}^x \end{align}

where the second line follows by the invertibility of $f$. This then tells us $\langle \psi_b | (|z'\rangle |0\rangle) = 0$ for all $z'$, and so $|\psi_b\rangle$ contains no "good" solutions.

Now that we've verified that $|\psi_b\rangle$ contains no good solutions and $\langle \psi_a | \psi_b \rangle = 0$, then you can apply any standard amplitude amplification algorithm that will allow you prepare $|x\rangle |0\rangle$ with high probability (or certainty) using $O(\sqrt{2^n})$ uses of $U_f$ and $U_f^\dagger$. See (Brassard, 1998) for example.

---

$^1$ Technically its fine if some bitstring $\neq 0$ occurs in the second register when $x$ appears in the first register - this just makes the amplitude amplification algorithm less efficient. In your case this is irrelevant since only one item is relevant to the search.