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) ?

  • $\begingroup$ 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. $\endgroup$
    – Mark S
    May 16 '19 at 11:52
  • $\begingroup$ Don't see why. The diffusion is applied to the input $n$ bits (just like in the database search). $\endgroup$ May 16 '19 at 12:37
  • $\begingroup$ 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$? $\endgroup$
    – Mark S
    May 16 '19 at 13:48
  • $\begingroup$ Yes, conditioned on $F(x)=1$. Also, keep in mind that $|x\rangle|f(x)\rangle$ is entangled. $\endgroup$ May 16 '19 at 13:54
  • $\begingroup$ 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? $\endgroup$
    – 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.

  • $\begingroup$ Thanks. Can you please provide reference for "you can't simply diffuse over the mixed state". $\endgroup$ May 28 '19 at 0:35

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.