Grover's Algorithm - The First Iteration

The First Iteration

A preliminary observation, in parallel with our definition

,

is that Uω can be expressed in an alternate way:

.

To prove this it suffices to check how Uω acts on basis states:

.
for all .

The following computations show what happens in the first iteration:

.
.
.
.

After application of the two operators ( and ), the amplitude of the searched-for element has increased from to .

Read more about this topic:  Grover's Algorithm

Famous quotes containing the words the first:

    The aphorism, the apothegm, in which I am the first among the Germans to be a master, are the forms of “eternity”; it is my ambition to say in ten sentences what everyone else says in a book—what everyone else does not say in a book.
    Friedrich Nietzsche (1844–1900)