Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS294-66 Quantum Computation Problem Set 1
Instructions: Solutions should be legibly handwritten or typset. Sets are to be returned in the mailbox outside 615 Soda Hall.
Problem 1 (Expectation of an operator). In practice, we care about the outcome of a quantum system averaged over many trials. Consider a qubit |ψi ∈ C2 and associate the measurement |0i with +1 and a measurement of |1i with −1.
1. (2 points) Show the expectation of this experiment is hψ|Z|ψi where Z = 1 0 0 −1 = |0ih0| − |1ih1| .
2. (2 points) This gives rise to the notation, hZiψ = hψ|Z|ψi (or hZi when the state ψ is clear from context). Give an experiment with expectation hXi where X = 0 1 1 0 .
Problem 2 (CHSH Game). (4 points) Recall the CHSH game discussed in the first lecture. In this game, Alice and Bob receive random inputs x, y ∈ {0, 1} and they win when they output a, b ∈ {0, 1} such that a ⊕ b = xy. In other words they play to maximize the Pr[a ⊕ b = xy]. Physicists often describe the same game in different notation. As before Alice and Bob receive random inputs x, y ∈ {0, 1}, but now they output u, v ∈ {1, −1}. Denote by ux Alice’s output when she receives x, and vy Bob?s output when he receives y. Then in this notation, the goal of the players is to maximize S = E(u0v0) + E(u0v1) + E(u1v0) − E(u1v1). Make sure that you understand why the physics formulation is equivalent to the version discussed in class. In particular, show that the maximum value of S for classical players is 2, whereas for quantum players it is at least 4(cos2 π/8 − sin2 π/8) = 2 √ 2.
Problem 3 (The GHZ game). In this problem, we explore another game, like the CHSH game, that demonstrates this “spooky action” at a distance.
The setup of the game is the similar to that of the CHSH game, except there are 3 players Alice, Bob and Charlie. The referee will send each of the players as input the string “x” or the string “y” and expects in return a bit {+1, −1}. However, the referee will only give out inputs consisting of zero or two y’s; the 4 possible inputs are {xxx, xyy, yxy, yyx}. The players win if in the case that the input is xxx, the product of their outputs is +1 and in the case that two of them received y as input, the product of their outputs is −1. Equivalently,
input: xxx −→ output product: + 1
input: xyy −→ output product: − 1
input: yxy −→ output product: − 1
input: yyx −→ output product: − 1
1. (2 points) Show that if the 3 players, Alice, Bob and Charlie each employ a deterministic strategy, they cannot win with probability 1. (Hint: proof by contradiction). Give a simple deterministic strategy that wins with probability 3/4.
2. (2 points) Argue that even if Alice, Bob and Charlie share randomness, they still cannot win with probability 1.
3. (2 points) Now, we will come up with a quantum strategy that wins with probability 1. Suppose that Alice, Bob, and Charlie share one part of the tripartite cat state |γi = |000i + |111i √ 2 . On input x, assume each player measures their part of the cat state in the |+i = √ 1 2 (|0i + |1i),|−i = √ 1 2 (|0i − |1i) basis (the eigenstates of the X operator). Show that this measurement strategy allows the players to win with probability 1 on input xxx.
4. (2 points) On input y, assume each player measures their part of the cat state in the |+ii = √ 1 2 (|0i + i |1i),|−i = √ 1 2 (|0i − i |1i) basis (the eigenstates of the Y = iXZ operator). Show that this measurement strategy allows the players to win with probability 1 on input xyy.
5. (2 points) Argue by symmetry that for the input cases yxy and yyx, the players win with probability 1.
Problem 4 (Quantum teleportation). Imagine Alice and Bob are on Earth and the Moon, respectively, and Alice wants to send to Bob her favorite qubit |ψi. Unfortunately, the only communication channel Alice and Bob have is classical; they can only send bits. However, before Bob left for the Moon, Alice and Bob came together to generate an EPR state, |Φi = |00i + |11i √ 2
and each kept one half of the state. We will now construct a scheme in which Alice will perform measurements on |ψi and her half of the EPR pair and send the measurements to Bob who can use the measurements to recover the state |ψi.
The following is the purported scheme as a quantum circuit. Alice controls the top two wires (the original state |ψi and half of the EPR pair) and Bob controls the bottom wire. After Alice performs her measurements in the standard basis for outputs x and z, she classically transports the bits x and z to Bob who applies gates conditionally. Here, we employ the convention that X 1 = X and X 0 = I.
|ψi • H z x X x Z z |ψi |Φi (1)
One way to analyze the correctness of this scheme is to write |ψi = α |0i + β |1i and work through the unitaries and the measurements. Instead, we can use our understanding of delayed measurements and unitary multiplication to vastly simplify this analysis.
1. (2 points) Conclude that for an EPR state |Φi and any one qubit unitary U, U ⊗ I |Φi = I ⊗ U > |Φi.
Show that this holds even if the unitary U is controlled on a third 3 qubit. I.e. show that the following two circuits are equivalent: • U |Φi • U> |Φi
2. (2 points) Therefore, the following transformation of the circuit from (1) is valid:
|ψi • H z x X x Z z |ψi |Φi (2)
Notice that this circuit is no longer a teleportation circuit as Alice and Bob apply a shared quantum gate; this circuit is purely for analysis purposes.
Now using the principle of deferred measurement, argue that it is sufficient to consider the following circuit for all x. |ψi • H z |xi X x Z z |ψi (3) 3. (2 points) By commuting gates, argue that we can further simplify to only considering the following circuit. |ψi • H z |0i Z z |ψi (4)
4. (2 points) By expanding |ψi as α |0i + β |1i, show that (4) is valid.