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

grover1.png

\[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\) !

grover2.png