QC — Grover’s algorithm

6 min readDec 10, 2018

In Part 8, we introduce the first quantum algorithm. Here, we will introduce another famous one called Grover’s algorithm to demonstrate the power of quantum parallelism, in specific, making queries in parallel. Quantum algorithms involve a lot of maths. But for Grover’s algorithm, we will demonstrate how it works graphically.

Consider a function that is always equal to 0 except for a single value u. How are we going to find u?

A classical algorithm requires N queries to find u in the worst case. But Grover’s algorithm can complete the task in root N.

But that assumes Grover’s algorithm has access to an oracle function that can compute f(x) simultaneously. (For a classical computer, such a function may require an N core computer. So the complexity remains O(N).) Immediately, you may want to know how the Oracle function is implemented. In practice, if you want an Oracle that handles all possible functions f, quantum computing will unlikely have any competitive edge. But for some specific domains, if you can identify some specific pattern to load the desired superposition in polynomial time, you can win.

But in reality, it is one of the milestones in quantum computing. We demonstrate something that quantum computing may be superior even if we do not demonstrate a practical Oracle function. As quantum algorithms are advancing, we may put different techniques together for commercial applications. So let’s treat this Oracle function as a black box and study Grover’s algorithm.

As always, we prepare a superposition as:

In our example, we will use 3 qubits, i.e.

After the state preparation, Grover’s algorithm turns into an iterative process which composes of multiple iterations of the Oracle function and the Grover operator.

First, in ①, we apply the Oracle function.

where the oracle function is defined as

Let’s substitute the state we prepare and check out its output for different values of f(x)

So for any |x⟩ with f(x) = 0, its amplitude does not change. Otherwise, the amplitude is changed to negative. In our example, f(011) =1 and after applying the Oracle function, the superposition state turns into:

The average of the amplitudes (the dotted line) will drop because of the negative amplitude of |011⟩.

Now we apply the Grover operator G.

What does the Grover operator do?

It flips every amplitude around the average, the horizontal dotted line below.

So after applying the Grover operator, the superposition becomes

So if we make any measurement, the measured state equals the correct answer is increased. In the Dirac notation:

If we measure the qubits now, we still have a reasonable chance of selecting the wrong answer. So we repeat this process square root times (√N) to amplify the amplitude of the right answer.

For example, if we repeat the Oracle and the Grover operator once more, the amplitude of the correct answer will stand out more.

So let’s go through the math in detail again. After applying the Oracle function in the first iteration, the superposition is:

With the original|ψ⟩ equals

The state after the Grover operation becomes

Substituting the inner product:

and replacing |ψ⟩, the superposition becomes:

And that is the result after the first iteration.

Implementation

While our earlier demonstration has 3 qubits, we will implement a simpler problem with 2 qubits. If we go through the process again, we will find this to be a very special case. In the first flip, for the incorrect answer, we flip its amplitude of ½ around 1/4 which turns to 0. Therefore, the right answer has a 100% chance of measurement in one iteration.

Here is an implementation of Grover’s search algorithm for u=11.

This is our measurement (reporting from Q4 to Q0 — in reverse direction and Q0 being the auxiliary qubit):

If we run it in a simulator, we see the result is 11 which matches with our prediction exactly.

The physical implementation has about a 54% chance of getting the right result. The lower value is a reflection of the gate errors (the deeper we go, the higher the error) as well as the approximation error in implementing the logical quantum gates with the physical universal quantum gates.

Here is another implementation for different values of x=u.