Editing Grover's algorithm (section)

== Algebraic proof of correctness ==
To complete the algebraic analysis, we need to find out what happens when we repeatedly apply <math>U_s U_\omega</math>. A natural way to do this is by eigenvalue analysis of a matrix. Notice that during the entire computation, the state of the algorithm is a linear combination of <math>s</math> and <math>\omega</math>. We can write the action of <math>U_s</math> and <math>U_\omega</math> in the space spanned by <math>\{|s\rang, |\omega\rang\}</math> as:

<math>\begin{align}
U_s : a |\omega \rang + b |s \rang &\mapsto [|\omega \rang \, | s \rang] \begin{bmatrix}
-1 & 0 \\
2/\sqrt{N} & 1 \end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}. \\

U_\omega : a |\omega \rang + b |s \rang &\mapsto [|\omega \rang \, | s \rang] \begin{bmatrix}
-1 & -2/\sqrt{N} \\
0 & 1 \end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}.
\end{align}</math>

So in the basis <math>\{ |\omega\rang, |s\rang \}</math> (which is neither orthogonal nor a basis of the whole space) the action <math>U_sU_\omega</math> of applying <math>U_\omega</math> followed by <math>U_s</math> is given by the matrix

<math display="block"> U_sU_\omega = \begin{bmatrix} -1 & 0 \\ 2/\sqrt{N} & 1 \end{bmatrix}
\begin{bmatrix}
-1 & -2/\sqrt{N} \\
0 & 1 \end{bmatrix}
 = 
\begin{bmatrix}
1 & 2/\sqrt{N} \\
-2/\sqrt{N} & 1-4/N \end{bmatrix}.</math>

This matrix happens to have a very convenient [[Jordan form]]. If we define <math>t = \arcsin(1/\sqrt{N})</math>, it is

<math display="block"> U_sU_\omega = M \begin{bmatrix} e^{2it} & 0 \\ 0 & e^{-2it}\end{bmatrix} M^{-1}</math>

where <math>M = \begin{bmatrix}-i & i \\ e^{it} & e^{-it} \end{bmatrix}.</math>

It follows that ''r''-th power of the matrix (corresponding to ''r'' iterations) is 

<math display="block"> (U_sU_\omega)^r = M \begin{bmatrix} e^{2rit} & 0 \\ 0 & e^{-2rit}\end{bmatrix} M^{-1}.</math>

Using this form, we can use trigonometric identities to compute the probability of observing ''&omega;'' after ''r'' iterations mentioned in the previous section, 

<math display="block">\left|\begin{bmatrix}\lang\omega|\omega\rang & \lang\omega|s\rang\end{bmatrix}(U_sU_\omega)^r \begin{bmatrix}0 \\ 1\end{bmatrix} \right|^2 = \sin^2\left( (2r+1)t\right).</math>

Alternatively, one might reasonably imagine that a near-optimal time to distinguish would be when the angles 2''rt'' and −2''rt'' are as far apart as possible, which corresponds to <math>2rt \approx \pi/2</math>, or <math>r = \pi/4t = \pi/4\arcsin(1/\sqrt{N}) \approx \pi\sqrt{N}/4</math>. Then the system is in state

<math display="block"> [|\omega \rang \, | s \rang] (U_sU_\omega)^r \begin{bmatrix}0\\1\end{bmatrix} \approx [|\omega \rang \, | s \rang] M \begin{bmatrix} i & 0 \\ 0 & -i\end{bmatrix} M^{-1} \begin{bmatrix}0\\1\end{bmatrix} = | \omega \rang \frac{1}{\cos(t)} - |s \rang \frac{\sin(t)}{\cos(t)}.</math>

A short calculation now shows that the observation yields the correct answer ''&omega;'' with error <math>O\left (\frac{1}{N} \right)</math>.