a,b,c,d?

2. (7 Points) Let's recall how the Berinstein-Vazirani algorithm works. 1. We begin with n00 state. 2. Apply H (Hadamard) to every qubit. 3. Apply the phase kick-back for a function f(x)=xs. 4. Apply H to every qubit. 5. When we read off all the qubits, we obtain the bit-string s. In this problem, we will study a modified version of the Bernstein-Vazirani algorithm in which the state begins with the 11 state. In this problem, we shall assume that x and s are n-bit strings: x=xn1x0 and s=sn1s0. Their dot product is defined as xs=(i=0n1xisi)mod2. (a) (2 Points) Suppose we instead begin with the n11 state. After applying H to every qubit, we will obtain a state of the following form: 2n1x=02n1(1)g1(x)x for some function g1(x). What is g1(x) ? (b) (2 Points) Continuing from (a), applying the phase kick-back for the function f(x)=xs, we will get a state of the following form: 2n1x=02n1(1)g2(x)x for some function g2(x). What is g2(x) ? (Hint: Recall that the phase kick-back operation of f(x) maps x to (1)f(x)x) (c) (2 Points) Continuing from (b), now we apply H to every qubit. We will obtain a bit-string upon measurement. Will you always get the same measurement result, or not? Explain your reasoning. (d) (1 Points) How can we deduce s from the bit-string obtained in (c)