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