QUANTUM ALGORITHMS
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 = |endi.
• |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 ◦ Ds ◦ A† ◦ DA where DA is a reflection operator for |Ai and Ds is a reflection operator for |starti (use the phase shift eiθ for both).
1. Draw the circuits for both reflection operators and also write out the operators for them (e.g. D0 = (eiθ − 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 eiθ in this case?
1
