Quantum Homework 9 Solved

Description

We will consider a generalization of Grover’s 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)_i∈I such that I = A∪B 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^iθ for both).

1. Draw the circuits for both reflection operators and also write out the operators for them (e.g. D₀ = (e^iθ − 1)|0ih0| + I as in the usual Grover’s 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 Grover’s 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^iθ in this case?