In this tutorial, we will get a fundamental knowledge of the infamous Grover's Search Algorithm. We will understand the steps of the algorithm with an easy example using 2 qubits and finally implement the circuit initialized using 2 qubits in a simulator and real quantum device.
Grover's algorithm is a speed-searching algorithm that demonstrates Quantum superiority over classical algorithms.
Many of us must have heard about the linear search algorithm: you are given a sorted set of data and you are to keep looking for the desired data-point until you find it. And so, the time complexity is directly related to the size of the data-set. However, Grover's search algorithm can speed up the search process quadratically. Let us consider a simple a scenario to get the intuition.
Suppose, you are given a list of N number of boxes and based on a unique property, you want to find a specific box. Classically, you need to make boolean query for N/2 (average) times and in worst case for N times. But Grover's algorithm will help us find the box with roughly sqrt(N) steps based on amplitude amplification technique. Each box in the list is mapped as a possible state of qubits (e.g 8 (2^N) boxes need 3 qubits to be represented) and hence has a 1/sqrt(N) probability of being the one we are looking for. Amplitude of the desired state is amplified which results in amplitude shrinkage of others so that each of the probabilities add up to unity.
Now that we have amplified the amplitude, we apply the reflection oracle which basically adds negative phase to the solution state.
For |X>, oracle is defined as:
So graphically, the solution state has been reflected as follows:
As we iterate the steps (amplitude amplification and reflect oracle) the probability of solution state after measurement reaches ideally close to 1 (number of iteration doesn't affect time complexity). Now, let us try to implement our understanding using simple Qiskit codes:
In order to implement the algorithm we first need all of the qubits (2 in this example) in an uniform superposition state which can be achieved using the Hadamard gate on each qubit.
Let's try to find the position of desired state (in this case) |11>:
Here we try to understand how can we make an oracle for the required state:
The oracle for state |11> acts as follows:
and in the matrix form it corresponds to
Looking more closely we will be able to recognize that using the controlled Z gate on the state equally superposition state of |00> we can achieve this state.
For completing the circuit, we need to use additional reflection and mainly the diffuser works to amplify the required states probability amplitude where else shrinks the that of other items.
Constructing the complete circuit:
Adding measurement basis:
Our whole circuit has been completed; now let us implement this circuit first in a simulator and finally on a real device.
Here, we can see that the probability of our desired state (|11$\rang$) is significantly higher than rest other states and thus easily distinguishable.