[Solved] Quantum Homework 9

We will consider a generalization of Grovers algorithm. Suppose that we are given the following.

• A, a quantum circuit.
• Basis vector |starti and quantum state |endi (i.e. norm 1) with A|starti = |end
• |endi = |Ai + |Bi with hA | Bi = 0, hA | Ai = a, and hB | Bi = b = 1 a.

Let us consider |Ai as consisting of a superposition of correct outcomes of algorithm A.

Upon measuring |endi, the probability of observing |Ai is a.

We assume that we have a basis (_i)_iI such that I = AB and a function : I {0,1} such that (A) = 1 and (B) = 0. Define

|(,)i = |Ai + |Bi

and note that |(1,1)i = |endi. Define G = A D_s A D_A where D_A is a reflection operator for |Ai and D_s is a reflection operator for |starti (use the phase shift eⁱ for both).

1. Draw the circuits for both reflection operators and also write out the operators for them (e.g. D₀ = (eⁱ 1)|0ih0| + I as in the usual Grovers algorithm).
2. Calculate G |(1,1)i and write your answer in the form |(x,y)i for some x,y (you should specify their values).
3. Suppose that A works with probability 1/4 (i.e. a = 1/4). Show that taking = (as in the usual Grovers circuit) makes G A acting on |starti exact (i.e. it produces a correct answer with probability 1).
4. Show that when A works with probability 1/2 there is a choice of so that G A acting on |starti is exact. What is the value of eⁱ in this case?