4
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ $\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}$. $\endgroup$ Mar 27, 2019 at 21:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.