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?
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 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:
In our example, we will use 3 qubits, i.e.
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.
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 value 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.
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, match with our prediction exactly.
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.
We have studied two quantum algorithms. Next, we will get into Simon’s algorithm before finishing our series with a real problem.