Grover algorithm for more than one element

Question

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!

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$.