0. Acknowledgements.  (0pts) The assignment will receive a 0 if this question is not answered.

(a) If you worked in a group, list the members of the group. Otherwise, write “I did not work in a group.”

(b) If you received significant ideas about the HW solutions from anyone not in your group, list their names here.  Otherwise, write  “I did not consult without anyone except my group members” .

(c) List any resources besides the course material that you consulted in order to solve the material. If you did not consult anything, write “I did not consult any non-class materials.”

1.  Can a function be evaluated at two places with a single quantum query? (6pts) Here we consider the problem where we have a query oracle for a function f : {0, 1} - {0, 1} and the goal is to obtain information about both f (0) and f (1) with a single query. We assume that the query oracle is in the usual form of a unitary operator Uf  that, for all a, b e {0, 1}, maps la, b) to la, b · f (a)) .  For simplicity, we consider methods that employ only two qubits in all and are expressible by a circuit of the form

where V and W are two-qubit unitaries and the gates labelled χ are measurements in the computational basis. Therefore, it can be assumed that the input state to the query (i.e., right after V is applied) is a two-qubit state of the form α00 l00)+α01 l01)+α10 l10)+α11 l11) , where lα00 l2 + lα01 l2 + lα10 l2 + lα11 l2  = 1.

(a) For each of the four functions of the form f : {0, 1} - {0, 1}, give the quantum state right after the query has been performed.

(b) If there is a measurement procedure that perfectly distinguishes between the four states in part (a) then they must be mutually orthogonal. Show that, for a measure- ment to be able to perfectly determine the value of f (0), it must be the case that α 10  = α 11 . (Hint: think of the orthogonality relationships that need to hold.)

(c)  Show that, if the states are such that f (0) can be determined perfectly from them, then f (1) cannot be determined with probability better than 1/2 (which is no better than random guessing). (Hint: You may use the result in part (b) for this.)

(d)  Optional for bonus credit for all students: The above analysis is restricted to methods that use two qubits.  Show that, for all m > 2, any strategy that uses m qubits (V and W are m-qubit unitaries and the query gate Uf  acts on the last two qubits) and determines f (0) perfectly cannot determine f (1) with probability better than 1/2.

2.  Classical and quantum algorithms for the OR problem (Part I). (6pts) In these next two questions, we consider the problem where we are given a black box for a function f : {0, 1} - {0, 1} and the goal is to determine f (0) ^ f (1) (the logical OR of f (0) and f (1)) with a single query to f .

(a)  Optional for bonus credit for undergrad students: Give a classical probabilis-

tic algorithm that makes a single query to f and predicts f (0)^f (1) with probability 2/3.  The probability is respect to the random choices of the algorithm; the input instance of f is assumed to be arbitrary (worst-case). (Note that it is not correct to give an algorithm that always outputs 1, and claim that this succeeds with proba- bility 3/4 because, for three of the four functions, f (0) ^ f (1) = 1. There exists an f for which the success probability of that algorithm is 0.)

It turns out that no classical algorithm can succeed with probability greater than 2/3 (but you are not asked to show this here).

(b)  Give a quantum circuit that, with a single query to f , constructs the two-qubit state  ╱(_1)f (0) l00) + (_1)f (1) l01) + l11) ← .

(Hints:  First construct a circuit for  ╱(_1)f (0)l00) + (_1)f (1)l01) + (_1)f (1)l11) ← . The gate

╱ ^(^)   _^(^)、

and the controlled-Hadamard gate might be helpful for this. Next think about how to “supress” the phase for l11) .)

(c) The quantum states of the form in part (b) are three-dimensional and have real- valued amplitudes.   This makes it easy for us to visualize the geometry of these states (as vectors or lines in R3 ).  Consider the four possible states that can arise from part (b), depending on which of the four possible functions f is. What is the absolute value of the inner product between each pair of those four states?

3.  Classical and quantum algorithms for the OR problem (Part II). (6pts)

(a) Based on the results of Part I (question 2), give a quantum algorithm usting only unitary operations and measurements in the standard basis for the OR problem that makes a single query to f and: succeeds with probability 1 whenever f (0)^f (1) = 0; succeeds with probability 8/9 whenever f (0) ^ f (1) = 1.

(b)  Optional for bonus credit for undergrad students: Note that the error prob-

ability of the algorithm from part  (a) is one-sided in the sense that it is always correct in the case where f (0) ^ f (1) = 0.  Give a quantum algorithm for the OR problem that makes a single query to f and succeeds with probability 9/10.  (Hint: take the output of the one-sided error algorithm from part (a) and do some classical post-processing on it, in order to turn it into a two-sided error algorithm with higher success probability.)