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

Question

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.

Answer 1

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

Answer 2

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 \begin{equation} R\leq \frac{\pi}{4}\sqrt{\frac{N}{M}} \end{equation} where $N$ is the number of total elements while $M$ is the number of solution elements in the basis.