Quantum algorithm that "searches" for a particular state in a bigger state vector?

Question

Does there exist an oracle that inputs a quantum state, say for example

$$ \frac{1}{2^N} \sum_{n=0}^{2^N - 1} \left | n \right > \left | f(n) \right > $$

and allows us to find $n$ such that $f(n) = A$ for some given $A$? Or easier, $f(n) = 0^{\otimes N}$.

This state can be represented, in vector form, like this

$$ \begin{pmatrix} \left | f(000) \right > \\ \left | f(001) \right > \\ \left | f(010) \right > \\ \left | f(011) \right > \\ \vdots \end{pmatrix} $$

This question is very similar to Grover's algorithm, which instead asks:

find x such that $f(x) = 1$

$$ \frac{1}{\sqrt{2^N}} \sum_{n=0}^{2^N -1} (-1)^{f(n)} \left | n \right > $$

Of course Grover's algorithm has a solution that runs in $O(\sqrt{2^N})$ time. Does the problem I pose have a solution, and is it efficient?

Answer 1

I think that if you encode the state just as you indicated - the left part is the binary encoding of $n$ and the right part is the binary encoding of $f(n)$ - using Grover and just marking the element $A$ will let you find the state that has $A$ on its right side and hence the index on the left side.

I would have to try this out but intuitively I don't see why this wouldn't work. Of course, the number of qubit increases by 2x, as you have to encode $n$ and $f(n)$.

Answer 2

As stated by rhundt, using Grover's algorithm would work here. Actually, we can do even better and show that these two problems are equivalent. Since Grover's algorithm is optimal for this problem, it shows that we cannot solve this problem faster than $O\left(\sqrt{2^n}\right)$.

Let us denote $U_f$ the unitary that acts as the following on the basis states: $$U_f|x, y\rangle=|x,y\oplus f(x)\rangle$$ Now, suppose we initialize our state in the uniform superposition on the first register, and in the $|0\rangle$ state for the second register and another register: $$\sum_{n=0}^{2^n-1}|n\rangle|0\rangle|0\rangle$$ We can apply $U_f$ to the first and second register: $$\sum_{n=0}^{2^n-1}|n\rangle|f(n)\rangle|0\rangle$$ Now, we apply an $X$ gate on the third register controlled on the second one being in state $A$: $$\sum_{n=0}^{2^n-1}|n\rangle|f(n)\rangle|f(n)=A\rangle$$ Finally, we apply $U_f$ once again to uncompute the second register: $$\sum_{n=0}^{2^n-1}|n\rangle|f(n)=A\rangle$$ By doing so, we've successfully created an oracle that returns $1$ on $n$ if $f(n)$ is equal to $1$, which is exactly Grover's problem. This proves that Grover's algorithm can be used to solve your problem.

On the other hand, we easily see that Grover's problem is a special case of your problem: simply replace $A$ by $1$ and you're left with Grover's problem. Thus, these two problems are equivalent, and as such Grover's algorithm is the optimal method to solve it.