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)

    “He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
    —Herman Melville (1819–1891)

    “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)