Grover’s Algorithm (My Lab)

Cahyati Supriyati Sangaji (My Note)

You will implement Grover’s algorithm in Qiskit. You might find this chapter of the Qiskit Textbook useful:

• https://qiskit.org/textbook/ch-algorithms/grover.html

Remember, to run a cell in Jupyter notebooks, you press Shift + Return/Enter on your keyboard.

Installing necessary packages

Before we begin, you will need to install some prerequisites into your environment. Run the cell below to complete these installations. At the end, the cell outputs will be cleared.

!pip install -U seaborn==0.10
!pip install -U qiskit==0.19
!pip install -U ipywidgets==7.5.1
from IPython.display import clear_output
clear_output()

Review of Grover’s Algorithm

Grover’s algorithm has three main components.

Graded Exercise 1: Implementing Grover’s Algorithm

It is not hard to implement Grover’s algorithm using Qiskit. The goal of this lab is to implement Grover's algorithm by creating a quantum circuit that has the marked elements 000001 and 101010. You will see that the algorithm outputs one of these two marked elements with probability greater than 99%.

Let us build each block step by step.

1) Phase Oracle

We start with the phase oracle. You might find it helpful to have a look at the corresponding chapter in the Qiskit textbook: https://qiskit.org/textbook/ch-algorithms/grover.html. However, note that the implementation in the textbook is done on 2 and 3 qubits only, while here we need to apply it to 6 qubits.

Once you complete these steps, apply the unitary operator to the quantum circuit.

from qiskit.quantum_info import Operator
from qiskit import QuantumCircuit
import numpy as np
def phase_oracle(n, indices_to_mark, name = 'Oracle'):
    # create a quantum circuit on n qubits
    qc = QuantumCircuit(n, name=name)
### WRITE YOUR CODE BETWEEN THESE LINES - START
    oracle_matrix = np.identity(2**n)
    for index_to_mark in indices_to_mark:
        oracle_matrix[index_to_mark, index_to_mark] = -1
### WRITE YOUR CODE BETWEEN THESE LINES - END
# convert your matrix (called oracle_matrix) into an operator, and 
# add it to the quantum circuit
    qc.unitary(Operator(oracle_matrix), range(n))
    
    return qc

2.) Diffusion Operator 𝑉

def diffuser(n):
    
    # create a quantum circuit on n qubits
    qc = QuantumCircuit(n, name='Diffuser')
    
    ### WRITE YOUR CODE BETWEEN THESE LINES - START
    qc.h(range(n))
    qc.append(phase_oracle(n,[0]),range(n))
    qc.h(range(n))
    ### WRITE YOUR CODE BETWEEN THESE LINES - END
    
    return qc

3.) Putting it all together

Finally, we combine the functions to construct Grover’s algorithm. We need to determine the optimal number of rounds 𝑟. This was given by

We have also seen a lower bound on the success probability when using 𝑛 qubits. In this exercise, the success probability should be higher than 99%.

Let’s construct a quantum program that finds the marked elements 000001 and 101010 using Grover's algorithm. To do this, we will need to do the following:

1. We start with a Hadamard gate on all qubits.
2. Next, we apply 𝑟r rounds of Grover’s algorithm, where each round consists of the application of the phase oracle with the marked elements and the diffuser. The indices for the two marked elements 000001 and 101010 are 1 and 42.
3. Finally, we need to measure all qubits.

The next lines of code put everything together.

def Grover(n, indices_of_marked_elements):
    
    # Create a quantum circuit on n qubits
    qc = QuantumCircuit(n, n)
    
    # Determine r
    r=int(np.floor(np.pi/4*np.sqrt(2**n/len
          (indices_of_marked_elements))))
    print(f'{n} qubits, basis states {indices_of_marked_elements} 
          marked, {r} rounds')
    
    # step 1: apply Hadamard gates on all qubits
    qc.h(range(n))
    
    # step 2: apply r rounds of the phase oracle and the diffuser
    for _ in range(r):
        qc.append(phase_oracle(n, indices_of_marked_elements), 
                  range(n))
        qc.append(diffuser(n), range(n))
        
    # step 3: measure all qubits
    qc.measure(range(n), range(n))
  
    return qc
mycircuit = Grover(6, [1, 42])
mycircuit.draw(output='text')

That’s it! You might find it useful to run your quantum circuit and see the measurement outcomes, as well as visualize the statevector at the end.

In order to run your quantum circuit and get the measurement outcomes, you simply need to run Qiskit's execute function as follows.

from qiskit import Aer, execute
simulator = Aer.get_backend('qasm_simulator')
counts = execute(mycircuit, backend=simulator, shots=1000).result().get_counts(mycircuit)
from qiskit.visualization import plot_histogram
plot_histogram(counts)

Additional reading

• In the exercise above, we implemented the phase oracle and diffuser as matrices without decomposing them into single- and two-qubit gates. To run on real hardware, one will also need to consider how to build these oracles using gates. You can find examples of how the oracles can be built in the Grover’s algorithm section of the Qiskit Textbook here: https://qiskit.org/textbook/ch-algorithms/grover.html

References:

Qiskit (Global Summer School), Introduction to Quantum Computing and Quantum Hardware — Lab 2.