Grover's Algorithm - Algebraic Proof of Correctness

Algebraic Proof of Correctness

To complete the algebraic analysis we need to find out what happens when we repeatedly apply . 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 and . We can write the action of and in the space spanned by as:

U_s : a |\omega \rang + b |s \rang \mapsto (|\omega \rang \, | s \rang) \begin{pmatrix} -1 & 0 \\ 2/\sqrt{N} & 1 \end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}.
U_\omega : a |\omega \rang + b |s \rang \mapsto (|\omega \rang \, | s \rang) \begin{pmatrix} -1 & -2/\sqrt{N} \\ 0 & 1 \end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}.

So in the basis (which is neither orthogonal nor a basis of the whole space) the action of applying followed by is given by the matrix

U_sU_\omega = \begin{pmatrix} -1 & 0 \\ 2/\sqrt{N} & 1 \end{pmatrix} \begin{pmatrix} -1 & -2/\sqrt{N} \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2/\sqrt{N} \\ -2/\sqrt{N} & 1-4/N \end{pmatrix}.

This matrix happens to have a very convenient Jordan form. If we define, it is

where

It follows that rth power of the matrix (corresponding to r iterations) is

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

.

Alternatively, one might reasonably imagine that a near-optimal time to distinguish would be when the angles 2rt and -2rt are as far apart as possible, which corresponds to or . Then the system is in state

A short calculation now shows that the observation yields the correct answer ω with error O(1/N).

Read more about this topic:  Grover's Algorithm

Famous quotes containing the words algebraic, proof and/or correctness:

    “I have no scheme about it,—no designs on men at all; and, if I had, my mode would be to tempt them with the fruit, and not with the manure. To what end do I lead a simple life at all, pray? That I may teach others to simplify their lives?—and so all our lives be simplified merely, like an algebraic formula? Or not, rather, that I may make use of the ground I have cleared, to live more worthily and profitably?”
    —Henry David Thoreau (1817–1862)

    “From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
    —Johan Huizinga (1872–1945)

    “Rather would I have the love songs of romantic ages, rather Don Juan and Madame Venus, rather an elopement by ladder and rope on a moonlight night, followed by the father’s curse, mother’s moans, and the moral comments of neighbors, than correctness and propriety measured by yardsticks.”
    —Emma Goldman (1869–1940)