# Grover search with single query to $f(x)$ and multiple queries to $f(x) = a$

Assume $$f(x)$$ is an $$n$$ bits to $$m$$ bits function and we want to use Grover's search algorithm to find $$x$$ such that $$f(x) = a$$, where $$a$$ is some $$m$$-bit predetermined value.

When using the algorithm, can we separate the calls to $$f(x)$$ and $$f(x)=a$$? That is, instead of querying $$F(x) \equiv (f(x) = a)$$ around $$2^{n/2}$$ times (interleaved with amplification), is it possible to query $$f(x)$$ once at the begining and then repeat $$2^{n/2}$$ times $$f(x)=a$$ (interleaved with amplification) ?

• It feels like you'd be applying the diffusion operator to an $(n+m)$-qubit input rather than merely an $n$-qubit input? You might need $2^{(n+m)/2}$ such repetitions? I'm not sure. – Mark S May 16 '19 at 11:52
• Don't see why. The diffusion is applied to the input $n$ bits (just like in the database search). – mike_dole_z3 May 16 '19 at 12:37
• It seems like you want to create a composite function, first $f(x)$ and then $F(x)$. Initially you'll create a superposition $\vert x\rangle\vert 000\cdots\rangle\vert 0\rangle$, then $\vert x\rangle\vert f(x)\rangle\vert 0\rangle$, and then $\vert x \rangle\vert f(x)\rangle\vert F(x)\rangle$. How would you rotate? Conditioned on $F(x)=1$? – Mark S May 16 '19 at 13:48
• Yes, conditioned on $F(x)=1$. Also, keep in mind that $|x\rangle|f(x)\rangle$ is entangled. – mike_dole_z3 May 16 '19 at 13:54
• But if you diffuse just on $\vert x\rangle$, $\vert f(x)\rangle$ gets in the way to stop the interference from the diffusion operator? – Mark S May 16 '19 at 22:40

It sounds like you want a state given to you as $$\vert x\rangle\vert f(x)\rangle$$, and you wish to only conditionally rotate when $$f(x)=a$$, diffuse over $$x$$, conditionally rotate when $$f(x)=a$$, diffuse over $$x$$, ... conditionally rotate when $$f(x)=a$$, diffuse over $$x$$, and measure.
If I understand your question, then I think the issue is in the "diffuse over $$x$$."
Because you can't simply diffuse over the mixed state $$\vert x\rangle$$, but you must diffuse over the pure state $$\vert x\rangle\vert f(x)\rangle$$.
If $$\vert f(x)\rangle$$ has not been uncomputed back to $$\vert 0\rangle$$, then the diffusion will not lead to constructive/destructive interference in the first register. Even if you are diffusing only over the first register $$\vert x\rangle$$, the second register $$\vert f(x)\rangle$$ gets in the way.