COMP SCI 4413, 4813, 7413
Introduction to Quantum Computing
Assignment 4
Author: Frank Neumann
Intructions
• Answer all questions. Remember to show your workings in your solutions.
Question 1 10 marks
Prove that the matrix −I + 2A used in Grover’s search algorithm is unitary. Hint: Start by
showing that A2 = A holds.
Question 2 15 marks
Execute Grover’s search algorithm for n = 5 and the function f : {0, 1}5 → {0, 1} where f (11111) = 1 and f(x) = 0 if x ̸= 11111. Show 2 iterations of the algorithm including the state after each phase inversion and each inversion about the mean.
Question 2 10 marks
Compute the period of the function f(x) = 5x mod 128, x ≥ 0 integer.
Question 3 15 (10+5) marks
• Compute the period of the function fa,N(x) = ax mod N, x ≥ 0 integer, for a = 5 and
N = 32.
• Writethestate x∈{0,1}m |x,fa,N(x)⟩
φ2 = √2m
in Shor’s algorithm after the application of Ufa,N for N = 32, n = 5, m = 10, and a = 5.
⇐= End of file =⇒
1