QC — Grover’s algorithm

Image for post
Image for post
Photo by Steven Welch

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 which is always equal 0 except a single value u. How are we going to find u?

Image for post
Image for post

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

Image for post
Image for post

But that assumes Gover’s algorithm has access to an oracle function which can compute f(x) simultaneously. (For a classical computer, such 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 function f, quantum computing will unlikely have any competitive edge. But for some specific domain, 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 more superior even 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:

Image for post
Image for post

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

Image for post
Image for post
Amplitudes for each computational basis

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

Image for post
Image for post
Modified from source

First, in ①, we apply the Oracle function.

Image for post
Image for post
Modified from source

where the oracle function is defined as

Image for post
Image for post

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

Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

Now we apply the Grover operator G.

Image for post
Image for post
Image for post
Image for post
Modified from source

What does the Grover operator do?

Image for post
Image for post

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

Image for post
Image for post

So after applying the Grover operator, the superposition becomes

Image for post
Image for post

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

Image for post
Image for post

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.

Image for post
Image for post

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

Image for post
Image for post
Image for post
Image for post

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

Image for post
Image for post

With the original|ψ⟩ equals

Image for post
Image for post

The state after the Grover operation becomes

Image for post
Image for post

Substituting the inner product:

Image for post
Image for post

and replacing |ψ⟩, the superposition becomes:

Image for post
Image for post

And that is the result after the first iteration.

Image for post
Image for post

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.

Image for post
Image for post
Modified from source

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

Image for post
Image for post

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

Image for post
Image for post

The physical implementation has about 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.

Image for post
Image for post
Source

Next

We have studied two quantum algorithms. Next, we will get into Simon’s algorithm before finishing our series with a real problem.

Reference

Quantum Algorithms

IBM Q

Written by

Deep Learning

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store