Quantum Algorithms Part 1/2: Grover's Algorithm

Let us begin, this is part 1 of our explorations into quantum algorithms. The second part shall consist of Shor's algorithm. I hope you enjoy this. It might be worth re-reading my error correction notes to familiarise yourself with some of the concepts I'll be mentioning here.

Grover's Algorithm: The problem, the philosophy and the implementation 

I shall first state the problem, then move on to the kinds of steps that are required to solve it and then finally onto how it is carried out in a quantum circuit. The problem and the philosophy are illustrated in Figure 1 while the implementation is laid out in Figure 2. 

The problem

To begin, we must first state the problem itself. We are given some function f which maps some numbers which are entries in a database onto one of two possible values: 0 or 1. 

Formally speaking, f:{0,1,...,N-1} -> {0,1} and there exist some unique value x for which f(x)=1 

The function uniquely maps onto 1 for that particular value of x only - every other value, is mapped onto 0. It is worth mentioning, that the number of elements is 2^n. Now we somehow want to find this unique element. So what can we do? Classically, we could search through all N elements, which would (in the wort case scenario) require N steps. In comp sci, you say that as forth: O(N)

Using Grovers algorithm, we can get find the element in O(sqrt[N]) steps. How do we do that? Well Grover algorithm has two steps. I'll explain those steps and then get onto the implementation.  

The philosophy

 

The algorithm requires two steps - phase inversion and inversion about the mean 

Step 1: Phase inversion 

So first of, every element in the database gets assigned an equal amplitude of 1/sqrt(N). Then, our special element x* gets assigned an amplitude of - 1/sqrt(N). 

Step 2: Inversion about the mean 

Secondly, every amplitude about the mean is inverted. The - 1/sqrt(N) gets converted to approximately 3/sqrt(N) The approximate conversion is because when we inverted the phase in step 1, we lowered the initial mean from 1/sqrt(N) slightly. 

If we continue this process of step 1 and step 2, what we end up with in sqrt(N) steps is that our element x* has an amplitude of 1/sqrt(2) so the prob of measuring it is (1/sqrt(2))^2 = 1/2

See Figure 1 for the entire working. 

Figure 1: Problem and the philosophy

The implementation 

So I'll just lay it out. For phase inversion, we apply a classical XOR gate or addition mod 2 if you're a mathematician. It is worth noting that we put our special element in the state |-> in order to get a phase change. For inversion about the mean, we apply this rather Jazzy gate. I've laid out all of this in figure 2 so just check that for the details on this section. 

Finally, we have our quantum circuit for Grover algorithm in Fig 3. 

Figure 2: Implementation mechanism

Figure 3: (figure 2 continuation) and final circuit 

Concluding remarks

This quadratic speedup over classical database searching is quite remarkable. The speedup offered by Shor's however, is far more surprising. If you want more details, check Nielson and Chuang's book. I shall release part 2 of this post sometime later today or tomorrow. Wait just a little bit longer!