# Quantum computers: Grover’s algorithm

We apply the composite transformation $$VU$$ to $$T$$ and specifically
look at what happens to the vector $$|\xi\rangle$$ which we defined
above as $$\frac{1}{\sqrt{N}}\sum_x|xC(x)\rangle$$.

Diagram showing how the composite map $$VU$$ is a rotation. What is the
operation $$VU$$? It's a composition of two reflections and hence it's a
rotation. To understand exactly what's rotating where, let's write
$$|\xi'\rangle$$ for the projection of $$|\xi\rangle$$ to the subspace
spanned by black vectors (normalising $$|\xi'\rangle$$ to have norm 1)
and restrict attention to the 2-dimensional subspace spanned by
$$|\xi'\rangle$$ and the vector $$|mW\rangle$$, corresponding to the
unique white vector in our dataset (remember I told you a long time
ago that $$m$$ is the identification number of the unique white object!).

Now $$|\xi\rangle$$ is a linear combination of $$|\xi'\rangle$$ and
$$|mW\rangle$$ by construction, say
$|\xi\rangle=\cos\phi|\xi'\rangle+\sin\phi|mW\rangle$ Moreover, we
know that the coefficient of $$|mW\rangle$$ in $$|\xi\rangle$$ is
$$1/\sqrt{N}$$, so $\sin(\phi)=1/\sqrt{N}.$ The two reflections $$U$$
and $$V$$ preserve the 2-dimensional subspace spanned by $$|\xi'\rangle$$
and the vector $$|mW\rangle$$. Indeed, reflecting using $$U$$ gives
$U|\xi\rangle=\cos\phi|\xi'\rangle-\sin\phi|mW\rangle$ and the using
$$V$$ (exercise, very clear when you draw the picture!) gives $VU|\xi\rangle=\cos(\phi+2\phi)|\xi'\rangle+\sin(\phi+2\phi)|mW\rangle$
In other words, $$VU$$ is a rotation by $$2\phi$$ towards $$|mW\rangle$$. If we
rotate $$R$$ times then the $$|mW\rangle$$-component of $$(VU)^R|\xi\rangle$$ is
$\sin((2R+1)\phi)$ and (remembering our discussion about
measurement) the square of this quantity $\sin^2((2R+1)\phi)$ has an
interpretation as the probability that we get the right identification
number for the white object when we measure the identification number
in this state (i.e. after rotation). When $$N$$ is large φ is very
small and we can pick $$R$$ to make $$\sin^2((2R+1)\phi)$$ very close
to 1. Indeed, when $$N$$ is enormous, so that
$$\phi\approx\sin\phi=1/\sqrt{N}$$ it's clear that we need
$$2R/\sqrt{N}\approx \pi$$, i.e. $R\approx \pi\sqrt{N}/2\mbox{ iterations}.$

Note: we don't want to do any more than this, or else we start
rotating away from $$|mW\rangle$$ ! Posted in: Uncategorized