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)

    “If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
    —Thomas Jefferson (1743–1826)

    “What will happen once the authentic mass man takes over, we do not know yet, although it may be a fair guess that he will have more in common with the meticulous, calculated correctness of Himmler than with the hysterical fanaticism of Hitler, will more resemble the stubborn dullness of Molotov than the sensual vindictive cruelty of Stalin.”
    —Hannah Arendt (1906–1975)