I am currently working on the Grover algorithm again. In many lectures and documents, as well as books, I noticed that there is always talk of looking for a single element of $N$ elements. Now I read to Nielsen that Grovers algorithm can also be used for multiple searches. For example if you are looking for $M>1$ elements from $N$

Now comes the problem, in Nielsen is e.g. said that the process does not change fundamentally. I tried an example by looking for a single element, you can see the result here, I have successively applied the individual steps of the algorithm:

Searched item: $|01\rangle$

Input: $|00\rangle$

Hadamard on n-bits: $$ H|00\rangle=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$$ Apply $ U_f $ to bits: $$\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle+|11\rangle)$$ Hadamard on n-bits (again): $$\frac{1}{4}(|00\rangle+|01\rangle+|10\rangle+|11\rangle- |00\rangle+|01\rangle-|10\rangle+|11\rangle +|00\rangle+|01\rangle-|10\rangle-|11\rangle +|00\rangle-|01\rangle-|10\rangle+|11\rangle) =\frac{1}{2}(|00\rangle+|01\rangle-|10\rangle+|11\rangle)$$ Phase Shift: $$\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle)$$ Hadamard transform (again): $\frac{1}{4}(|00\rangle+|01\rangle+|10\rangle+|11\rangle -|00\rangle+|01\rangle-|10\rangle+|11\rangle +|00\rangle+|01\rangle-|10\rangle-|11\rangle -|00\rangle-|01\rangle-|10\rangle-|11\rangle) =\frac{1}{4}(4|01\rangle)$$

So you see directly that the searched (single) element ($|01\rangle$) comes out, the question is, what happens if I say we are looking for two elements e.g $|01\rangle, |10\rangle$?

This is understandable for me as far as possible, especially that even at the end exactly one single element is in the register, that one has searched.

Now my question comes: What happens if I search for several elements? Let's say, how do you stay with the example and are you looking for another element? How about the individual steps of the algorithm and, most importantly, what is in the register afterwards?

I am very much looking forward to your answers and hope that my question is clear and understandable. Thanks in advance!


1 Answer 1


Firstly, the general case:

When looking for a single element, you apply the inversion $U_f = I - 2\left|\psi\rangle\langle\psi\right|$, where $\left|\psi\right>$ is the searched-for element. When searching for $M$ elements, forming a subset $S$, this inversion becomes $$U_f = I - 2\sum_{x\in S}\left|x\rangle\langle x\right|,$$ which is now an inversion about $\left|S\right> = \frac{1}{\sqrt M}\sum_{x\in S}\left|x\right>$ for states in the subspace spanned by $\left|S\right>$ and $\left|+\right>$.

In the single element case, the angle $\gamma$ between $\left|+\right>$ and $\left|\psi\right>$ can be given by $\sin\gamma = \left<\psi|+\right> = \frac{1}{\sqrt N}$, with an initial angle between the starting state $\left|+\right>$ and $\left|\psi\right>$ of $\gamma_0 = \frac{1}{2}\pi - \gamma$. After $T$ iterations, the angle between the current state and the $\left|\psi\right>$ becomes $$\gamma_T = \frac{1}{2}\pi - \left(2T+1\right)\sin^{-1}\frac{1}{\sqrt N},$$ as after each iteration, the current state shifts by $2\gamma$. This gives a probability of obtaining $\left|\psi\right>$ of $$\sin^2\left(\left(2T+1\right)\sin^{-1}\frac{1}{\sqrt N}\right)$$ and so we take $$T = \left\lfloor\frac{\pi\sqrt N}{4}\right\rfloor.$$

In the multiple element case, this extends to $\sin\gamma = \left<S|+\right> = \sqrt{\frac{M}{N}}$, we get a probability of obtaining the state $\left|S\right>$ of $$\sin^2\left(\left(2T+1\right)\sin^{-1}\sqrt{\frac{M}{N}}\right)$$, giving $$T = \left\lfloor\frac{\pi}{4}\sqrt{\frac{N}{M}}\right\rfloor.$$

The given example

We're looking for the 2 elements $\left|01\right>$ and $\left|10\right>$, so $M=2,\, N = 4\implies T=1$. Following the algorithm:

\begin{align*}H^{\otimes 2}\left|00\right> &= \frac{1}{2}\left(\left|00\right\rangle+\left|01\right\rangle+\left|10\right\rangle+\left|11\right\rangle\right)\\ U_fH^{\otimes 2}\left|00\right> &= \frac{1}{2}\left(\left|00\right\rangle-\left|01\right\rangle-\left|10\right\rangle+\left|11\right\rangle\right) \\ H^{\otimes 2}U_fH^{\otimes 2}\left|00\right> &= \left|11\right\rangle \\ -U_0H^{\otimes 2}U_fH^{\otimes 2}\left|00\right> &= -\left|11\right\rangle \\ -H^{\otimes 2}U_0H^{\otimes 2}U_fH^{\otimes 2}\left|00\right> &= \frac{1}{2}\left(-\left|00\right\rangle+\left|01\right\rangle+\left|10\right\rangle-\left|11\right\rangle\right).\end{align*}

In this specific case, this is obviously no more help than picking at random. Going back to the probability of obtaining $\left|S\right>$, we have that $\sin^{-1}\frac{1}{\sqrt 2} = \frac{\pi}{4}$ and that $$\sin^2\left(\frac{\pi}{4}\left(2T+1\right)\right) = \frac{1}{2},$$ so the probability of obtaining the correct result is 1/2, as a result of $N=2M$.

  • $\begingroup$ is there a typo in the form of $T$ here? replacing it in the previous equation you would get inside the $\sin^2$ something like $\sqrt{N/M}\sin^{-1}\sqrt{M/N}$. But here $\sin^{-1}$ denotes $\arcsin$, not $1/\sin$, I presume (unless you are approximating $\sin(\sqrt{M/N})\simeq\sqrt{M/N}$) $\endgroup$
    – glS
    Commented Aug 9, 2020 at 6:17
  • $\begingroup$ @glS Yes, I'm using $\sin^{-1}$ to mean $\arcsin$, but I don't see how that makes the form of $T$ wrong?.. If you could somehow set $T$ to be the non-integer value $\pi/4 \times \sqrt{N/M}$ instead of the floored value, you get a success probability of $1$, which is what we want $\endgroup$
    – Mithrandir24601
    Commented Aug 12, 2020 at 11:17
  • $\begingroup$ ... under the assumption that $M/N$ is small enough and thus $\sin(\sqrt{M/N})\simeq\sqrt{M/N}$. Otherwise you just have $\frac{\pi}{2}\sqrt{N/M}\arcsin(\sqrt{M/N})$ $\endgroup$
    – glS
    Commented Aug 12, 2020 at 12:12
  • $\begingroup$ @glS Yes, sure, around $M/N \approx 1/2$, the approximation breaks down a bit, yes. But in that case, (classically) randomly sampling is good enough $\endgroup$
    – Mithrandir24601
    Commented Aug 25, 2020 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.