Answer Happy

Let f be the function on four-bit strings defined by f(x, y, z, w) = x©y+y©z+z© w, where x, y, z, w = {0,1}, z denotes NOT(z) where we interpret z as a bit, denotes addition modulo 2 (equivalent to XOR on two bits), and + denotes standard integer addi- tion. Define the unitary Uƒ |x, y, z, w) |n) = |x, y, z, w) |n + f(x, y, z, w) mod 4) acting on six qubits, where n = {0, 1}² is interpreted as the standard 2-bit binary representation of an integer in the range 0 ≤ n ≤ 3. Let G denote the subspace spanned by the states x, y, z, w) corresponding to the solutions to f(x, y, z, w) = 3. Let IIG denote the orthogonal projector onto G. Define ZG = 1- 21IG, Z=12 |¢) (v| and I = −Z ZG. Let ) be the four-qubit state: |) = (0001) + |0010) + |0100) + |1000)). In this question, you may use without proof the following trigonometric identities: sin(n + m)0 = sin ne cos me + cos no sin mo, cos(n + m)0 = cos no cos m0 - sin ne sin mo.
d. Show that the Amplitude Amplification algorithm starting from the state ) can be used to find one of the solutions of f(x, y, z, w) = 3 using only a single call to Uf. [5 marks] e. Explain how the unitary Zę can be implemented in terms of Uƒ. For this part of the question, you may assume reversible quantum implementations of all 1- and 2-bit classical logic gates are available. [4 marks] f. How many calls to Uf would the standard Grover algorithm applied to f(x, y, z, w) require to find a solution with optimal probability? For this part of the question, you may state without proof any results covered in the lecture course concerning Amplitude Amplification and Grover's algorithm. [4 marks] g. Why is it that the algorithm from part ?? only requires a single call to Uƒ to find a solution with certainty, whereas the standard Grover algorithm requires more calls to Uf to find a solution with high probability? [4 marks]