HW4 - Problem 2

Problem 2: The Perfect Magic Trick

(This problem is taken from Ryan O’Donnell’s 2018 offering of a quantum computing course.)

Alice is on Mars, Bob is on Jupiter, Charlie is on Saturn. With each of them is a referee. The referees have agreed before hand to uniformly pick one of the following four strings: 111, 100, 010, 001. The players know that these are the four options too. The first bit will be presented to Alice, the second to Bob, and the third to Charlie.

Upon receiving their bit, Alice, Bob, and Charlie must quickly respond with a 0 or a 1. They “succeed with the magic trick” if:

  • The referees presented 111: The responses have an even number of 1’s
  • The referees presented a single 1 and two 0’s: The responses have an odd number of 1’s

We assume that the spatial distance between the three parties prevent them from communicating at all, but they are allowed to coordinate before the game and bring anything they want with them.

  1. Design a deterministic (classical) strategy for Alice, Bob, and Charlie in which the probability that they succeed is 3/4.

Suppose that Alice, Bob, and Charlie prepare the following 3-qubit state on Earth before the magic trick begins:

\(\frac{1}{2}\left|000\right> - \frac{1}{2} \left|011\right> - \frac{1}{2} \left|101\right> - \frac{1}{2} \left|110\right>.\)

Alice takes the first qubit, Bob the second, and Charlie the third qubit to their respective planets. Now, when they receive their challenges, they each use the following strategy:

  • If they are given a 1, they measure their qubit and respond with the outcome.
  • If they are given a 0, they first apply a Hadamard gate to their qubit, and then measure and respond with the outcome.

Let’s analyze the probability that Alice, Bob, and Charlie succeed with the magic trick.

  1. If they are all given a 0, what’s the probability that they win?

  2. If one person gets a 1 and the other two get a 0, what’s the probability that they win? (You only need to consider the case where Alice is the person to get a 1, since the game is symmetric)