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?

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.

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.