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)

    “A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
    —Samuel Johnson (1709–1784)

    “With impressive proof on all sides of magnificent progress, no one can rightly deny the fundamental correctness of our economic system.”
    —Herbert Hoover (1874–1964)