Problem 1  (25 points) Simplify the following circuits as much as possible. Use only the gates x , z , CNoT , H, TOFFOLI, and Control-z gates.  Hint:  Try to think of tricks to reduce the amount of work you have to do.

(i)

(1)

(ii)

(2)

(iii)

(iv)

(3)

(4)

(v)

(5)

Problem 2  (15 points) What is the output of the following circuit?

(6)

Question 3 is on the next page.

Problem 3  (20 points) Suppose you are given two qubits 1w〉and 1o〉and you are wondering how similar they are to one another.   Note that you have the physical states, and not the vector descriptions. Consider the following circuit involving a controlled swap gate.

(7)

What are the probabilities of obtaining each measurement outcome?  (Note that the possible outcomes are just 0 and 1.) In each case, what is the post-measured state of the 2nd and 3rd qubit? Notation: The box with an arc and arrow in it represents a basic qubit measurement.