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.

Now, let’s say that an arbitrary state $|x\rangle$ is the state we’ll guess upon collapsing the superposition and prematurely measuring our qubit, hoping to find $|w\rangle$. Obviously, we want to maximize the likelihood of collapsing $|x\rangle$ to $|w\rangle$. So, we somehow want to increase $|x\rangle$'s bent towards it.

Just for clarity that $|w\rangle$ and $|E\rangle$ are not orthogonal, we add a vector $|x'\rangle$ that spans both and lies orthogonal to $|w\rangle$. The angle separating $|E\rangle$ and $|w\rangle$ from orthogonality is $\Delta$. Why we choose to introduce $|x'\rangle$ and $\Delta$ will become clear later.

Now, let’s try something with the vectors we have in front of us. Let’s reflect $|x\rangle$ on $|w\rangle$. That should bring us to the following situation, where $|x_1\rangle$ ...