# In what sense do repeated applications of Grover's operator rotate the state closer to the target?

I'm studying the quantum search algorithm on this book:

M.A. Nielsen, I.L. Chuang, "Quantum Computation and Quantum Information", Cambridge Univ. Press (2000) [~p. 252].

To sum up we have a state:

$$|\psi \rangle = \cos( \frac{\theta}{2}) |\alpha \rangle + \sin( \frac{\theta}{2})|\beta\rangle$$ with $$\theta \in [0, \pi]$$

Now we apply an operator called G that performs a rotation:

$$G |\psi \rangle = \cos( \frac{3\theta}{2}) |\alpha \rangle + \sin( \frac{3\theta}{2})|\beta\rangle$$

Continued application of $$G$$ takes the state to:

$$G^k |\psi \rangle = \cos( \frac{(2k+1)\theta}{2}) |\alpha \rangle + \sin( \frac{(2k+1)\theta}{2})|\beta\rangle$$

Now the book says: " Repeated application of the Grover iteration rotates the state vector close to $$| \beta \rangle$$

Why? Probably it is a silly doubt but I can't figure out.

As was also pointed out in another answer, repeated applications of the Grover operator rotate the state closer to the target $$\lvert\beta\rangle$$ in the sense that the probability of finding the state in $$\lvert\beta\rangle$$ increases up to a certain point (or equivalently, the fidelity between the state and $$\lvert\beta\rangle$$ gets closer to one).

More precisely, you can see that this probability is, after $$k$$ iterations, $$p^{(k)}_\beta\equiv \lvert\langle \beta\rvert G^k\lvert\psi\rangle\rvert^2=\sin^2\left(\frac{(2k+1)\theta}{2}\right).$$ Now, you start with the probability $$p^{(0)}_\beta=\sin^2(\theta/2)$$. This tells you how close the initial state is to the target. In most basic introductions to Grover's algorithm, you have $$\sin(\theta/2)=2^{-n/2}=1/\sqrt N$$ with $$n$$ number of qubits or $$N$$ total dimension of the state space, so that $$p_\beta^{(0)}=2^{-n}=1/N$$. This is not really important for the discussion though so let us consider the general case with arbitrary $$\theta$$.

By definition, you know that $$\sin(\theta/2)\le1$$ (because the overlap of a state with another state can never exceed $$1$$), so that $$\theta\le\pi$$. The question thus becomes: what is the smallest integer $$k\ge0$$ such that $$(2k+1)\theta\sim\pi$$?. More precisely, we are looking for the $$k_0\in\mathbb N$$ that minimises the difference between $$(2k+1)\theta$$ and $$\pi$$: $$k_0=\operatorname{argmin}_k\{(2k+1)\theta-\pi\}.$$ In other words, you are looking for the odd number $$(2k+1)$$ that is closer to $$\pi/\theta$$, which is the same as saying that you are looking for the non-negative integer $$k_0$$ that is closer to $$\pi/2\theta-1/2$$. This number is $$k_0=\left\lfloor\frac{\pi}{2\theta}\right\rfloor,$$ that is, the integer part of $$\pi/2\theta$$ $${}^\dagger$$.

In summary, $$p_\beta^{(k)}$$ will keep increasing with $$k$$ for all $$k\le k_0$$, after which it reaches its maximum and will start decreasing again (note that you might have $$k_0=0$$, in which case Grover's algorithm is useless). You might notice that the smaller the initial $$\theta$$ is, the more Grover's algorithm brings you closer to the target, but also the more steps will be needed to do that.

$${}^\dagger$$ To see this, write $$\frac{\pi}{2\theta}=\left\lfloor\frac{\pi}{2\theta}\right\rfloor+r$$, where $$0\le r\le1$$ is the decimal part of $$\pi/2\theta$$.

If $$0\le r\le 1/2$$, then $$\frac{\pi}{2\theta}-\frac{1}{2}=\left\lfloor\frac{\pi}{2\theta}\right\rfloor-r'$$ where $$0\le r'\le 1/2$$, and thus $$\left\lfloor\frac{\pi}{2\theta}\right\rfloor$$ is the closer integer.

If on the other hand $$1/2\le r\le1$$, then $$\frac{\pi}{2\theta}-\frac{1}{2}=\left\lfloor\frac{\pi}{2\theta}\right\rfloor+r''$$ for some $$0\le r''\le1/2$$. It follows that, again, the integer closest to $$\pi/2\theta-1/2$$ is $$\left\lfloor\frac{\pi}{2\theta}\right\rfloor$$.

In the space of $$\{|\alpha \rangle ,|\beta\rangle\}$$ (where $$|\beta \rangle$$ is the solution vector) vectors, which are orthogonal, there is an initial angle of $$\pi/2$$. As you can see from the result that $$\sin \frac{(2k+1)\theta}{2}$$ increases when $$k$$ increases for the respective anglular range $$\{0,\pi/2 \}$$ while $$\cos \frac{(2k+1)\theta}{2}$$ decreases. So the probability of getting state $$|\beta\rangle$$ which is $$|\sin \frac{(2k+1)\theta}{2}|^2$$ increases, before it overshoots with repeated iterations the vector $$|\beta\rangle$$ at some iteration. The required value of approximate number of iterations can be caculated beforehands for a given problem. This is approximately equal to $$$$R\leq \frac{\pi}{4}\sqrt{\frac{N}{M}}$$$$ where $$N$$ is the number of total elements while $$M$$ is the number of solution elements in the basis.

• $\sin\frac{(2k+1)\theta}{2}$ doesn't increase when $k$ increases. $\sin\frac{(2*1+1)\theta}{2} > \sin\frac{(2*40+1)\theta}{2}$ for $\theta = \frac{\pi}{4}$. Mar 27 '19 at 21:43