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 .