How to decode 2-bit message from 2 entangled qubits?

Question

I'm trying to do exercise 3 of this quantum course.

Alice and Bob prepare an EPR pair in the Bell + state. They each take one qubit home.

Suddenly, Alice decides she wishes to convey one of 4 messages to Bob; in other words, she wants to convey a classical string $uv \in \{00, 01, 10, 11\}$ to Bob.

Alice does the following in the privacy of her own home: First, if $u = 1$, she applies a NOT gate to her qubit (else if $u = 0$ she does nothing here).

Next, if $v = 1$, she applies a $Z$ gate to her qubit (else if $v = 0$, she does nothing here).

Finally, she walks to Bob’s house and silently hands him her qubit. Show that by measuring in a proper basis, Bob can determine the message that Alice wants to send.

---

My solution so far:

If you measure both in the standard computational basis you can tell that if the bits are different, the first digit that Alice wants to send is 1.

The problem I have is how to tell that Alice applied the $Z$ gate, while at the same time getting a 0-1 (apart from the phase that the gate added).

These being all the possible cases.

$$1/\sqrt{2} \left| 00 \right> - 1/\sqrt{2} \left| 11 \right>$$

$$1/\sqrt{2} \left| 00 \right> + 1/\sqrt{2} \left| 11 \right>$$

$$1/\sqrt{2} \left| 10 \right> - 1/\sqrt{2} \left| 01 \right>$$

$$1/\sqrt{2} \left| 10 \right> + 1/\sqrt{2} \left| 01 \right>$$

I think I am missing some extra bit of info? Bob should not be supposed to use an extra ancilla qubit to do a CNOT with the one that Alice gives him so that he makes 3 measurements (1 for +-, 1 for the first and one for the second bit), because it's just 2² cases. 2 measurements should suffice with the qubits that already exist but I am confused on how to proceed.

Answer 1

This procedure is referred to as superdense coding protocol; you can find a lot of detailed explanations of it, starting with the Wikipedia article. If you want a hint before getting a full explanation...

Effectively you need to distinguish the four Bell states. You can always do this with 100% accuracy, since all the states are orthogonal to each other. To do that, you need to find a unitary transformation which will convert these states to the four 2-qubit basis states $|00\rangle$, $|01\rangle$, $|10\rangle$ and $|11\rangle$. It might be easier to start thinking about converting the 2-qubit basis states to Bell states and then inverting that transformation.