Implementing Grover’s Search Algorithm and Comparing to Classical Search Algorithms

1 (5 pts.). Using the code we developed in class, create a graph which shows the expected computational runtime for searching for a specific binary string of length 2, 4, 8, 16, 32, and 64. Add to the plot the expected and worst case scenarios for a classical search. Do the same to find 2 specific strings of the given lengths above. Hint: for a binary string of a given length, how many possible strings are there to search through?

import numpy as np
import matplotlib.pyplot as plt

binary_string_length = [2, 4, 8, 16, 32, 64]
search_space = [2**i for i in binary_string_length]

grovers = [i**(1/2) for i in search_space]
linear_avg = [i/2 for i in search_space]
linear_worst = search_space

plt.plot(binary_string_length, grovers, color="darkred", label="Grover's")
plt.plot(binary_string_length, linear_avg, color="darkblue", linestyle="--", label="Linear (Average)")
plt.plot(binary_string_length, linear_worst, color="darkgreen", linestyle=":", label="Linear (Worst Case)")

plt.yscale("log")

plt.xlabel("Length of Binary String")
plt.ylabel("Expected Computational Time (Log-Scale)")
plt.legend()

2 (20 pts.). From scratch (so no Qiskit Grover functions and not using the function we created in class for the general case) create four Grover’s oracle circuits with two qubits each. The first should pick out the state \(|11\rangle\), the second the state \(|10\rangle\), the third the state \(|01\rangle\), and the final circuit should pick out the state \(|00\rangle\). Print the statevectors for each circuit and discuss your results (how can you tell you picked out the correct state). Apply the general amplification circuit and simulate running each circuit. Comment on if the results are correct. Hint: You may want to complete conceptual homework question 1 first.

from qiskit import QuantumRegister, QuantumCircuit, ClassicalRegister
from qiskit.quantum_info import Statevector
from qiskit.circuit.library import GroverOperator, MCMT, ZGate, XGate
from qiskit.visualization import  plot_histogram
from qiskit.quantum_info import Statevector
from qiskit_aer import AerSimulator
from qiskit import transpile
# Pick out 00

q = QuantumRegister(2)
c = ClassicalRegister(2)
qc_00 = QuantumCircuit(q,c)

qc_00.h(range(2))

qc_00.x(range(2))
qc_00.cz(0,1)
qc_00.x(range(2))

# Print the statevector of the circuit at the given moment
statevector = Statevector(qc_00)
display(statevector.draw(output = 'latex'))

\[- \frac{1}{2} |00\rangle+\frac{1}{2} |01\rangle+\frac{1}{2} |10\rangle+\frac{1}{2} |11\rangle\]

# Pick out 01

q = QuantumRegister(2)
c = ClassicalRegister(2)
qc_01 = QuantumCircuit(q,c)

qc_01.h(range(2))

qc_01.x(1)
qc_01.cz(0,1)
qc_01.x(1)

# Print the statevector of the circuit at the given moment
statevector = Statevector(qc_01)
display(statevector.draw(output = 'latex'))

\[\frac{1}{2} |00\rangle- \frac{1}{2} |01\rangle+\frac{1}{2} |10\rangle+\frac{1}{2} |11\rangle\]

# Pick out 10

q = QuantumRegister(2)
c = ClassicalRegister(2)
qc_10 = QuantumCircuit(q,c)

qc_10.h(range(2))

qc_10.x(0)
qc_10.cz(0,1)
qc_10.x(0)

# Print the statevector of the circuit at the given moment
statevector = Statevector(qc_10)
display(statevector.draw(output = 'latex'))

\[\frac{1}{2} |00\rangle+\frac{1}{2} |01\rangle- \frac{1}{2} |10\rangle+\frac{1}{2} |11\rangle\]

# Pick out 11
q = QuantumRegister(2)
c = ClassicalRegister(2)
qc_11 = QuantumCircuit(q,c)

qc_11.h(range(2))

qc_11.cz(0,1)

# Print the statevector of the circuit at the given moment
statevector = Statevector(qc_11)
display(statevector.draw(output = 'latex'))

\[\frac{1}{2} |00\rangle+\frac{1}{2} |01\rangle+\frac{1}{2} |10\rangle- \frac{1}{2} |11\rangle\]

def grover_amplification(qc, num_qubits):
    """
        Create a Grover's algorithm amplitude amplification for the general case of finding 
        some number of marked strings from a list of all possible binary strings fo a given 
        length.
        Inputs:
            qc (a qiskit circuit): The qiskit circuit to add the oracle to
            num_qubits (an int): The number of qubits in the circuit
    """    
    # Create a barrier to mark the start of the amplitude amplification algorithm
    qc.barrier()
    
    # Hadamard gates and then NOT gates for all qubits
    # followed by barier to separate the next part of the algorithm
    qc.h(range(num_qubits))
    qc.x(range(num_qubits))
    qc.barrier()
    
    # multi-controlled Z gate where the last qubit is the target and all other
    # qubits are the control
    qc.compose(MCMT(ZGate(), num_qubits - 1, 1), inplace=True)
    
    # barier to separate the next part of the algorithm
    # Hadamard gates and then NOT gates for all qubits
    qc.barrier()
    qc.x(range(num_qubits))
    qc.h(range(num_qubits))
    
    # Barrier to mark the end of the amplitude amplification algorithm
    qc.barrier()
grover_amplification(qc_00, 2)
grover_amplification(qc_01, 2)
grover_amplification(qc_10, 2)
grover_amplification(qc_11, 2)
qc_00.measure(range(2), range(2))
qc_01.measure(range(2), range(2))
qc_10.measure(range(2), range(2))
qc_11.measure(range(2), range(2))
<qiskit.circuit.instructionset.InstructionSet at 0x1427f7e50>
simulator_00 = AerSimulator()
t_qc_00 = transpile(qc_00, simulator_00)
results = simulator_00.run(t_qc_00).result().get_counts()
plot_histogram(results)

simulator_01 = AerSimulator()
t_qc_01 = transpile(qc_01, simulator_01)
results = simulator_01.run(t_qc_01).result().get_counts()
plot_histogram(results)

simulator_10 = AerSimulator()
t_qc_10 = transpile(qc_10, simulator_10)
results = simulator_10.run(t_qc_10).result().get_counts()
plot_histogram(results)

simulator_11 = AerSimulator()
t_qc_11 = transpile(qc_11, simulator_11)
results = simulator_00.run(t_qc_00).result().get_counts()
plot_histogram(results)

3 (25 pts.). Grover’s algorithm can be used for more than just finding a given binary string from all possible options. Check out this video where Grover’s algorithm is used to solve a famous dinner party problem and this site where Grover’s algorithm is used to solve a binary Sudoku problem and the triangle problem from graph theory. Using any of the above examples, any further examples you find online, or creating your own logic puzzle, create a Grover’s search algorithm to solve it. Your solution must be well commented explaining what each line of code does and you must comment on the results of the simulation (i.e. what do the results tell you are the best answers). For this question you may use your own oracles and amplification functions or the Qiskit built-ins.