Following the first set of notes covered in class on the Grover algorithm, outline the steps to implement the Grover algorithm for a system of 4 bits. You have N = 24 = 16 possible states in this case. Your initial state in the Grover algorithm will be the 4-qubit state |0, 0, 0, 0 > which can be represented by a 16X1 column vector with 1 on the first row and zeroes in all the other rows. • Write down the explicit expression of the 16X16 Hadamard matrix operating in the 16X1 4-qubit states as well as the expressions of the 16X16 Uquery and U0 matrices. • Write a code to apply the Grover operator sequentially and determine the number of iterations needed to reach the target state dt , which is a 16X1 column vector with zeroes on the first 15 rows and 1 on the bottom row. • Calculate the probability to be in the target state after each application of the Grover operator.
Final: Individual Project on Grover Algorithm This project will count as your final exam. This is an individual effort. You must return your project by 5pm on the last day of the semester. It will count for 25 % of your grade. Problem 1: Following the first set of notes covered in class on the Grover algorithm, outline the steps to implement the Grover algorithm for a system of 4 bits. You have N = 24 = 16 possible states in this case. Your initial state in the Grover algorithm will be the 4-qubit state |0, 0, 0, 0 > which can be represented by a 16X1 column vector with 1 on the first row and zeroes in all the other rows. • Write down the explicit expression of the 16X16 Hadamard matrix operating in the 16X1 4-qubit states as well as the expressions of the 16X16 Uquery and U0 matrices. • Write a code to apply the Grover operator sequentially and determine the number of iterations needed to reach the target state dt, which is a 16X1 column vector with zeroes on the first 15 rows and 1 on the bottom row. • Calculate the probability to be in the target state after each application of the Grover operator. Problem 2: Starting with the more general Hadamard matrix H(a) = ( √ 1− a2 a a − √ 1− a2 ) . (1) where a = 1/ √ 2 for the regular Hadamard matrix. • Show that H(a) is unitary. • Calculate UH , the tensor product of H(a) with itself. • Find the expressions of the 4X1 column vectors h0, h1, h2, h3 such that UHδ0 = h0, UHδ1 = h1, UHδ2 = h2, UHδ3 = h3, (2) where the δ′is (i=0,1,2,3) are the following column vectors (T is the transpose oper- ator), δ0 = (1, 0, 0, 0) T , δ1 = (0, 1, 0, 0) T , δ2 = (0, 0, 1, 0) T , δ3 = (0, 0, 0, 1) T . • Show that the following is true UHδk = hk, (3) for k=0,1,2,3. 1 Grover Algorithm Assignment Deadline: April 20, 2021 at 11:59 PM • Repeat the first derivation of the Grover algorithm for a system of 2-qubits derived in class using the generalized Hadamard matrix given above. Calculate the probability to find to the state of the 2-qubit system to be in the target state δt = [0, 0, 0, 1 T after one iteration of the Grover algorithm (your initial 2-qubit state is given by |0, 0 >.) • Plot the value of the probability to reach the target state found in the previous step as a function of the parameter a when the latter is varied in the interval [ 1√ 2 − 0.1, 1√ 2 + 0.1]. This question is used to illustrate the important of noise affecting quantum gates. Problem 3: Following the notes covered in class on a first exposure of the Grover algorithm, write down the explicit expressions of the 4X4 matrices U0 and Uquery which must be used in the 2-qubit Grover algorithm in order to reach the target 2-qubit state |0 > |1 > in just one iteration. Use the regular form of the Hadamard matrix in the algorithm and |0 > |0 > as the initial state of the 2-qubit system. Problem 4: Following the notes covered in class on a first exposure of the Grover algorithm for a 2-qubit system, • Calculate the expression of the 2-qubit state after one iteration of the Grover al- gorithm if the initial state of the 2-qubit system at t=0 is not |0 > |0 > but the entangled Bell state β00 shown in the diagram below. The latter has the explicit expression β00 = 1√ 2 [|00 > +|11 >]. (4) • Is the 2-qubit state after one iteration of the Grover algorithm an entangled state? If so, write it as a linear combination of some of the states |00 >, |01 >, |10 >, and |11 >. • If you keep on applying the Grover operation, calculate the probability to find the 2-qubit in the state |00 > after each application of the Grover algorithm. Calculate that probability for the first 10 applications of the Grover operator. Do not do this by hand, write a program to do your calculations. Explain what the program does. Problem 5: For a system of 3-qubits, what are the explicit forms of the 8X8 matrices UH , Uquery, and U0 which must be used to apply the Grover algorithm and eventually reach the target state |1, 1, 1 >. Assume that your initial 3-qubit state in the Grover Algorithm in given by |0, 0, 0 >. Problem 6: A store uses 4X4 tags such as the one illustrated on the figure below to mark the boxes in which they store their products. Each tag is a 4X4 array in 2 Figure 1: Illustration of the quantum circuit used to generate the entangled Bell State β00 which each square can either be black or white (for a total of 216 different products). Write a Grover algorithm which will be able to identify which product is inside a box with the tag shown below. In your algorithm, how many applications of the Grover operator are needed to identify the specific product? The initial tag you use to start the algorithm is one for which each square is black. 3 Figure 2: Illustration of a 4X4 tag used to identify a specific product in a store. It is a tile of 16 either white or black squares 4