Amplitude Amplification

Here’s what we did in the previous lesson:

• Created an equal superposition state $|E\rangle$ to obtain equal probabilities for all states and input them simultaneously to our algorithm.
• Applied our quantum search oracle $U_f$ and added a negative phase to the elements we do not want, essentially marking the one with a positive phase that we do want.

We now want to increase our chances/probability of finding the chosen state. This is where amplitude amplification comes in.

We’ll go through a geometric representation of this algorithm. That way, we will be able to see the effect before going over the mathematics behind it. Let’s start.

Rotations

States are vectors in the 2-D complex plane. We can picture these vectors as follows: $|E\rangle$ lies nearly orthogonal to $|w\rangle$, which is the state or element we want to seek in our collection. We say nearly orthogonal since, at the end of the day, if the element exists, we should reach it from the state $|E\rangle$. So, if the element did not exist in the collection, the two states would be orthogonal.