Menu
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:
# Importing standard Qiskit libraries:
import numpy as np
from qiskit import QuantumCircuit, transpile, Aer, IBMQ, execute, assemble
from qiskit.providers.ibmq import least_busy
from qiskit.tools.jupyter import *
from qiskit.visualization import *
from ibm_quantum_widgets import *
# Loading your IBM Quantum account(s):
provider = IBMQ.load_account()
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.
# Creating function for Equal Superposition states of two qubits:
def initialize(qc):
qc.h(0) # Applying H gates to both qubits
qc.h(1)
qc.barrier()
grover_circuit = QuantumCircuit(2) # Initializing grover circuit
initialize(grover_circuit)
grover_circuit.draw('mpl')
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.
def oracle_11(qc):
qc.cz(0,1) # Apply a controlled Z gate
qc.barrier()
oracle_11(grover_circuit)
grover_circuit.draw('mpl')
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:
# Creating Grover's Diffusion operator:
def u_g(qc):
qc.h(0)
qc.h(1)
qc.x(0)
qc.x(1)
qc.h(1)
qc.cx(0,1)
qc.x(0)
qc.h(1)
qc.h(0)
qc.x(1)
qc.h(1)
qc.barrier()
u_g(grover_circuit) # temporary circuit just to see what U_s looks like
grover_circuit.draw('mpl')
Adding measurement basis:
# Finally we measure the circuit:
grover_circuit.measure_all()
grover_circuit.draw('mpl')
Our whole circuit has been completed; now let us implement this circuit first in a simulator and finally on a real device.
# Simulating the Circuit:
backend = Aer.get_backend('qasm_simulator')
job = execute(grover_circuit, backend, shots = 1024)
result = job.result()
counts = result.get_counts()
plot_histogram(counts)
# Experimenting with real device:
IBMQ.load_account()
# Getting the least busy backend:
provider = IBMQ.get_provider(hub='ibm-q')
backend = least_busy(provider.backends(filters=lambda x: x.configuration().n_qubits >= 2
and not x.configuration().simulator
and x.status().operational==True))
print("least busy backend: ", backend)
# Running the circuit on the least busy backend. Monitor the execution of the job in the queue:
from qiskit.tools.monitor import job_monitor
transpiled_grover_circuit = transpile(grover_circuit, backend, optimization_level=3)
qobj = assemble(transpiled_grover_circuit)
job = backend.run(qobj)
job_monitor(job, interval=2)
# Getting the results from the computation:
results = job.result()
answer = results.get_counts(grover_circuit)
plot_histogram(answer)
Here, we can see that the probability of our desired state (|11$\rang$) is significantly higher than rest other states and thus easily distinguishable.
About
Support
Every week, our team curates the most important news, events, and opportunities in the quantum space. Our subscribers gain early access to opportunities and exclusive interviews with prominent individuals. You don't want to miss out.