3.2.7 The power of entanglement

In fact, entangled quantum bits are truly more powerful than probabilistic bits! In the following we will only have a glimpse, but we will see many more examples in the coming weeks.

Let us illustrate the power of entanglement by a little story which follows up on 3.13. There, you helped Alice decode the position of her donkey robot, which was in one out of four locations, labeled by two bits a,b∈{0,1}a,b\in\{0,1\}. Alice does not have time to pick up the donkey, so she wants to send the position onwards to Bob. Unfortunately, Alice is running low on her quantum mobile phone plan, so she can only send a single qubit to Bob. But sending a single quantum bit will certainly not be enough to perfectly communicate two bits. We know this because the only way for Bob to extract information is by measuring the qubit – but from the measurement he only learns a single bit and then the original state of the qubit is gone.

Happily enough, Alice and Bob had the foresight of sharing a maximally entangled state |Φ+⟩\left|\Phi^{+}\right\rangle. By this we mean that Alice is in possession of the first qubit and Bob is in possession of the second qubit. Can we help Alice send the donkey’s location (i.e., the two bits aa and bb) by transmitting a single qubit? This can indeed be done and the key ingredient is the following:

Exercise 3.14 (Transforming one Bell state into any other).

Show that Alice can, by applying local operations on her qubit alone, transform the maximally entangled state |Φ+⟩\left|\Phi^{+}\right\rangle into any of the three other Bell states |Φ−⟩\left|\Phi^{-}\right\rangle, |Ψ+⟩\left|\Psi^{+}\right\rangle, and |Ψ−⟩\left|\Psi^{-}\right\rangle.

Solution. Note from Eqs. 3.69, 3.70, 3.71 and 3.72 that the Bell states differ only by bit flips and signs. Recall that we can flip a bit using a local NOT\mathrm{NOT} operation and that we can introduce some signs by applying local ZZ operations, where ZZ is defined in Eq. 2.26. To create |Φ−⟩\left|\Phi^{-}\right\rangle, Alice can simply apply a ZZ operation on her qubit:
(Z⊗I)⁢|Φ+⟩=(Z⊗I)⁢(12⁢|00⟩+12⁢|11⟩)=12⁢|00⟩−12⁢|11⟩=|Φ−⟩.\displaystyle(Z\otimes I)\left|\Phi^{+}\right\rangle=(Z\otimes I)\left(\frac{1% }{\sqrt{2}}\left|00\right\rangle+\frac{1}{\sqrt{2}}\left|11\right\rangle\right% )=\frac{1}{\sqrt{2}}\left|00\right\rangle-\frac{1}{\sqrt{2}}\left|11\right% \rangle=\left|\Phi^{-}\right\rangle.
To create |Ψ+⟩\left|\Psi^{+}\right\rangle, Alice instead applies an NOT\mathrm{NOT} operation on her qubit:
(NOT⊗I)⁢|Φ+⟩=(NOT⊗I)⁢(12⁢|00⟩+12⁢|11⟩)=12⁢|10⟩+12⁢|01⟩=|Ψ+⟩.\displaystyle(\mathrm{NOT}\otimes I)\left|\Phi^{+}\right\rangle=(\mathrm{NOT}% \otimes I)\left(\frac{1}{\sqrt{2}}\left|00\right\rangle+\frac{1}{\sqrt{2}}% \left|11\right\rangle\right)=\frac{1}{\sqrt{2}}\left|10\right\rangle+\frac{1}{% \sqrt{2}}\left|01\right\rangle=\left|\Psi^{+}\right\rangle.
To create |Ψ−⟩\left|\Psi^{-}\right\rangle, Alice applies first an NOT\mathrm{NOT} operation and then a ZZ operation on her qubit:
(Z⁢NOT⊗I)⁢|Φ+⟩=(Z⊗I)⁢(12⁢|10⟩+12⁢|01⟩)=−12⁢|10⟩+12⁢|01⟩=|Ψ−⟩.\displaystyle(Z\,\mathrm{NOT}\otimes I)\left|\Phi^{+}\right\rangle=(Z\otimes I% )\left(\frac{1}{\sqrt{2}}\left|10\right\rangle+\frac{1}{\sqrt{2}}\left|01% \right\rangle\right)=-\frac{1}{\sqrt{2}}\left|10\right\rangle+\frac{1}{\sqrt{2% }}\left|01\right\rangle=\left|\Psi^{-}\right\rangle.

It is now clear how Alice and Bob can solve the challenge. Assume that Alice and Bob have beforehand agreed on a mapping between the four possible values of the two bits [a⁢b][ab] and the four Bell states (say, [00][00] corresponds to |Φ+⟩\left|\Phi^{+}\right\rangle, [01][01] corresponds to |Ψ+⟩\left|\Psi^{+}\right\rangle, and so on). Using 3.14, Alice first applies an operation on her part of the maximally entangled state to turn the state into the Bell state that corresponds to the donkey’s location. Next, she sends her quantum bit over to Bob. Now Bob has both quantum bits in his possession and he knows that they are in one of the four Bell states. Thus, he can simply apply the same operations as in 3.13 and measure the two qubits to figure out the donkey robot’s location.

The procedure we have just described is known as the superdense coding protocol, since we are transmitting two deterministic bits by sending a single quantum bit (at the cost of using up one maximally entangled state shared between Alice and Bob). Could Alice and Bob have just as well used probabilistic bits instead of an entangled state to solve this challenge (e.g., a pair of perfectly correlated bits)? Interestingly, this is not the case. Thus, superdense coding demonstrates that quantum entanglement provides an advantage for communication tasks.

In the following homework problem you can encounter another famous situation in which quantum entanglement provides an unambiguous advantage. The problem may perhaps look a bit daunting – but this is mostly because we could not resist telling a little story around it. As usual, do not hesitate to ask any questions on Discord!

Homework 3.7 (An entangled game (challenging)).

Alice and Bob are bored in class, so they ask their quantum mechanics teacher Ronald to pose them a challenging puzzle. After only a brief pause, Ronald explains to them an interesting game. The goal of the game is for Alice and Bob to cooperate as well as possible (they are not playing against each other). However, they are not allowed to communicate with each other while the game is going on! The rules of the game are as follows:

  • •
    ​

    To start, Ronald secretly tosses two fair coins. He tells Alice the result of the first coin toss (bit xx) and Bob the result of the second coin toss (bit yy). We call these input bits.

  • •
    ​

    After receiving the bits, Alice and Bob each have to answer with a bit of their own (bits aa and bb).

  • •
    ​

    Alice and Bob win the game under the following condition: if x=y=1x=y=1 then they win the game if a≠ba\neq b; otherwise, they win the game if a=ba=b.

[Uncaptioned image]

Before the game starts, Alice and Bob briefly get together to discuss their strategy. First, they consider simply applying two functions f,g:{0,1}→{0,1}f,g:\{0,1\}\to\{0,1\} on their input bits xx and yy and compute their answers as follows: a=f⁢(x)a=f(x) and b=g⁢(y)b=g(y).

  1. 1.
    ​

    Show that in this case they can win the game with probability 75%, but no higher.

Next, they consider coordinating their play using shared randomness. Bob suggests using more complicated functions ff and gg with an extra binary argument and to compute their answers as follows: a=f⁢(x,r)a=f(x,r) and b=g⁢(y,s)b=g(y,s), where rr and ss are two random bits jointly described by some two-bit probability distribution.

  1. 2.
    ​

    Show that they still cannot win with probability higher than 75%, no matter what the functions ff and gg are and what the joint distribution on the bits rr and ss is.

It begins to dawn on our protagonists that surely Ronald had a quantum-mechanical strategy in mind. Alice has an ingenious idea and proposes that they should share a maximally entangled state |Φ+⟩\left|\Phi^{+}\right\rangle before the game starts. She proposes that upon receiving their bits, she will rotate her qubit by some angle θx\theta_{x} (that depends on her input bit xx) and measure it to obtain her answer aa, while Bob should instead rotate by some other angle ωy\omega_{y} (depending on his input bit yy) and then measure to obtain his answer bb.

  1. 3.
    ​

    Write down the state after Alice and Bob applied their rotations in the form (3.31). Confirm that the probability of winning the game is

    14⁢(cos2⁡(θ0−ω0)+cos2⁡(θ0−ω1)+cos2⁡(θ1−ω0)+sin2⁡(θ1−ω1)).\frac{1}{4}\left(\cos^{2}(\theta_{0}-\omega_{0})+\cos^{2}(\theta_{0}-\omega_{1% })+\cos^{2}(\theta_{1}-\omega_{0})+\sin^{2}(\theta_{1}-\omega_{1})\right).

    Hint: Use the trigonometric formulas from Eqs. 2.30 and 2.36.

Alice and Bob quickly figure out that θ0=0\theta_{0}=0, θ1=π/4\theta_{1}=\pi/4, and ω0=π/8\omega_{0}=\pi/8 are good choices, but they are struggling with the last angle and time is quickly running out.

  1. 4.
    ​

    Find an angle ω1\omega_{1} such that they win the game with probability higher than 75%.

Hack.
  1. 1.
    ​

    There are four possible options for the ‘questions’ xx and yy and each arises with 25% possibility. Thus, the probability of winning is either 0%, 25%, 50%, 75%, or 100%, depending on how many questions they answer correctly. Simply ignoring the questions and outputting a=0a=0 and b=0b=0 already allows them to win with 75% probability. Are there functions f⁢(x)f(x) and g⁢(y)g(y) that work with 100% probability? If this were the case then

    f⁢(0)\displaystyle f(0) =g⁢(0),\displaystyle=g(0), f⁢(0)\displaystyle f(0) =g⁢(1),\displaystyle=g(1), f⁢(1)\displaystyle f(1) =g⁢(0),\displaystyle=g(0), f⁢(1)\displaystyle f(1) ≠g⁢(1).\displaystyle\neq g(1).

    The first three equations imply that f⁢(1)=g⁢(1)f(1)=g(1), which contradicts the last one.

  2. 2.
    ​

    Let us denote by wr,sw_{r,s} the probability that Alice and Bob win the game when using the functions a=f⁢(x,r)a=f(x,r) and b=g⁢(y,s)b=g(y,s) for fixed values of rr and ss. By the first part, we know that wr,s≤75%w_{r,s}\leq 75\%. How about if rr and ss are two random bits with probability distribution p=∑r,spr,s⁢[r,s]p=\sum_{r,s}p_{r,s}[r,s]? In this case the probability of winning using random bits is just the average of the wr,sw_{r,s}, i.e.,

    ∑r,spr,s⁢wr,s≤∑r,spr,s⁢75%=75%,\displaystyle\sum_{r,s}p_{r,s}w_{r,s}\leq\sum_{r,s}p_{r,s}75\%=75\%,

    where we used that the probabilities pr,sp_{r,s} are nonnegative and sum to one.

  3. 3.
    ​

    After applying their respective rotations, their state is

    (U⁢(θx)⊗U⁢(ωy))⁢|Φ+⟩\displaystyle\quad(U(\theta_{x})\otimes U(\omega_{y}))\left|\Phi^{+}\right\rangle
    =12⁢U⁢(θx)⁢|0⟩⊗U⁢(ωy)⁢|0⟩+12⁢U⁢(θx)⁢|1⟩⊗U⁢(ωy)⁢|1⟩\displaystyle=\frac{1}{\sqrt{2}}U(\theta_{x})\left|0\right\rangle\otimes U(% \omega_{y})\left|0\right\rangle+\frac{1}{\sqrt{2}}U(\theta_{x})\left|1\right% \rangle\otimes U(\omega_{y})\left|1\right\rangle
    =12⁢(cos⁡(θx)⁢|0⟩+sin⁡(θx)⁢|1⟩)⊗(cos⁡(ωy)⁢|0⟩+sin⁡(ωy)⁢|1⟩)\displaystyle=\frac{1}{\sqrt{2}}\left(\cos(\theta_{x})\left|0\right\rangle+% \sin(\theta_{x})\left|1\right\rangle\right)\otimes\left(\cos(\omega_{y})\left|% 0\right\rangle+\sin(\omega_{y})\left|1\right\rangle\right)
    +12⁢(−sin⁡(θx)⁢|0⟩+cos⁡(θx)⁢|1⟩)⊗(−sin⁡(ωy)⁢|0⟩+cos⁡(ωy)⁢|1⟩)\displaystyle+\frac{1}{\sqrt{2}}\left(-\sin(\theta_{x})\left|0\right\rangle+% \cos(\theta_{x})\left|1\right\rangle\right)\otimes\left(-\sin(\omega_{y})\left% |0\right\rangle+\cos(\omega_{y})\left|1\right\rangle\right)
    =12⁢(cos⁡(θx)⁢cos⁡(ωy)+sin⁡(θx)⁢sin⁡(ωy))⁢|00⟩\displaystyle=\frac{1}{\sqrt{2}}\left(\cos(\theta_{x})\cos(\omega_{y})+\sin(% \theta_{x})\sin(\omega_{y})\right)\left|00\right\rangle
    +12⁢(cos⁡(θx)⁢sin⁡(ωy)−sin⁡(θx)⁢cos⁡(ωy))⁢|01⟩\displaystyle+\frac{1}{\sqrt{2}}\left(\cos(\theta_{x})\sin(\omega_{y})-\sin(% \theta_{x})\cos(\omega_{y})\right)\left|01\right\rangle
    +12⁢(sin⁡(θx)⁢cos⁡(ωy)−cos⁡(θx)⁢sin⁡(ωy))⁢|10⟩\displaystyle+\frac{1}{\sqrt{2}}\left(\sin(\theta_{x})\cos(\omega_{y})-\cos(% \theta_{x})\sin(\omega_{y})\right)\left|10\right\rangle
    +12⁢(sin⁡(θx)⁢sin⁡(ωy)+cos⁡(θx)⁢cos⁡(ωy))⁢|11⟩\displaystyle+\frac{1}{\sqrt{2}}\left(\sin(\theta_{x})\sin(\omega_{y})+\cos(% \theta_{x})\cos(\omega_{y})\right)\left|11\right\rangle
    =cos⁡(θx−ωy)2⁢|00⟩−sin⁡(θx−ωy)2⁢|01⟩+sin⁡(θx−ωy)2⁢|10⟩+cos⁡(θx−ωy)2⁢|11⟩\displaystyle=\frac{\cos(\theta_{x}-\omega_{y})}{\sqrt{2}}\left|00\right% \rangle-\frac{\sin(\theta_{x}-\omega_{y})}{\sqrt{2}}\left|01\right\rangle+% \frac{\sin(\theta_{x}-\omega_{y})}{\sqrt{2}}\left|10\right\rangle+\frac{\cos(% \theta_{x}-\omega_{y})}{\sqrt{2}}\left|11\right\rangle

    Thus, if Alice and Bob measure the state then they obtain the same outcome (a=ba=b) with probability

    2⁢(cos⁡(θx−ωy)2)2=cos2⁡(θx−ωy),\displaystyle 2\left(\frac{\cos(\theta_{x}-\omega_{y})}{\sqrt{2}}\right)^{2}=% \cos^{2}(\theta_{x}-\omega_{y}),

    and distinct outcomes (a≠ba\neq b) with probability

    sin2⁡(θx−ωx).\displaystyle\sin^{2}(\theta_{x}-\omega_{x}).

    Given the rules of the game, it follows that the probability of winning is indeed

    14⁢(cos2⁡(θ0−ω0)+cos2⁡(θ0−ω1)+cos2⁡(θ1−ω0)+sin2⁡(θ1−ω1)).\displaystyle\frac{1}{4}\left(\cos^{2}(\theta_{0}-\omega_{0})+\cos^{2}(\theta_% {0}-\omega_{1})+\cos^{2}(\theta_{1}-\omega_{0})+\sin^{2}(\theta_{1}-\omega_{1}% )\right).
  4. 4.
    ​

    If we plug in the three angles we get

    14⁢(cos2⁡(−π8)+cos2⁡(−ω1)+cos2⁡(π4−π8)+sin2⁡(π4−ω1))\displaystyle\quad\frac{1}{4}\left(\cos^{2}\left(-\frac{\pi}{8}\right)+\cos^{2% }(-\omega_{1})+\cos^{2}\left(\frac{\pi}{4}-\frac{\pi}{8}\right)+\sin^{2}\left(% \frac{\pi}{4}-\omega_{1}\right)\right)
    =14⁢(2⁢cos2⁡(π8)+cos2⁡(ω1)+sin2⁡(π4−ω1)).\displaystyle=\frac{1}{4}\left(2\cos^{2}\left(\frac{\pi}{8}\right)+\cos^{2}(% \omega_{1})+\sin^{2}\left(\frac{\pi}{4}-\omega_{1}\right)\right).

    Note that this expression is maximal whenever cos2⁡(ω1)+sin2⁡(π4−ω1)\cos^{2}(\omega_{1})+\sin^{2}\left(\frac{\pi}{4}-\omega_{1}\right) is maximal. We can rewrite this as follows:

    cos2⁡(ω1)+sin2⁡(π4−ω1)\displaystyle\cos^{2}(\omega_{1})+\sin^{2}\left(\frac{\pi}{4}-\omega_{1}\right) =12+12⁢cos⁡(2⁢ω1)+12−12⁢cos⁡(π2−2⁢ω1)\displaystyle=\frac{1}{2}+\frac{1}{2}\cos(2\omega_{1})+\frac{1}{2}-\frac{1}{2}% \cos\left(\frac{\pi}{2}-2\omega_{1}\right)
    =1+12⁢[cos⁡(2⁢ω1)−sin⁡(2⁢ω1)]\displaystyle=1+\frac{1}{2}\left[\cos(2\omega_{1})-\sin(2\omega_{1})\right]
    =1+12⁢[cos⁡(π4)⁢cos⁡(2⁢ω1)−sin⁡(π4)⁢sin⁡(2⁢ω1)]\displaystyle=1+\frac{1}{\sqrt{2}}\left[\cos\left(\frac{\pi}{4}\right)\cos(2% \omega_{1})-\sin\left(\frac{\pi}{4}\right)\sin(2\omega_{1})\right]
    =1+12⁢cos⁡(π4+2⁢ω1)\displaystyle=1+\frac{1}{\sqrt{2}}\cos\left(\frac{\pi}{4}+2\omega_{1}\right)

    This is maximal when the cosine equates to 11, i.e., when 2⁢ω1=−π/42\omega_{1}=-\pi/4. So, we find that we must take ω1=−π/8\omega_{1}=-\pi/8. Plugging this into the expression that calculates the success probability yields:

    14⁢(2⁢cos2⁡(π8)+cos2⁡(π8)+sin2⁡(3⁢π8))=cos2⁡(π8)≈85.355%.\frac{1}{4}\left(2\cos^{2}\left(\frac{\pi}{8}\right)+\cos^{2}\left(\frac{\pi}{% 8}\right)+\sin^{2}\left(\frac{3\pi}{8}\right)\right)=\cos^{2}\left(\frac{\pi}{% 8}\right)\approx 85.355\%.

    Hence, they can win with probability bigger than 75%75\%, which is an improvement over the optimal classical strategy!

In the first two parts of the homework, you showed that any strategy using classical bits cannot win the game with probability higher than 75%. This is an example of a Bell inequality. The version above goes back to John Clauser, Michael Horne, Abner Shimony, and Richard Holt, so the game that Alice and Bob play with Ronald is often called the CHSH game. The quantum mechanical strategy that you discovered in the homework violates this Bell inequality. It is an empirical fact that Bell inequalities can indeed be violated by quantum mechanics. This was first demonstrated by Alain Aspect in the 80s and recently confirmed under very stringent conditions in a beautiful experiment by Ronald Hanson and his team at TU Delft.

Interestingly, Alice and Bob can not only play the CHSH game better using a shared maximally entangled state, but they can in fact convince Ronald that they must be using some quantum tricks to play the game so well. Indeed, since using only probabilistic strategies they cannot win the game with more than 75% probability, if they somehow succeed winning it more often then the only possible explanation for this is that they must be using something more powerful. In fact, using some further tricks they can even convince Ronald that they must be using the maximally entangled state and applying the rotations with the particular angles. Effectively, this means that they can prove to Ronald in an irrefutable way that they have small quantum computers that can manipulate single qubits and share entanglement. This is a very important observation, since it lets you use the CHSH game to verify that somebody genuinely has built a quantum computer! Indeed, if two of your classmates would claim that they have each built a quantum computer in their garages, you could simply ask them both to play together this game against you. If they manage to win with probability that is significantly larger than 75%, you would know that they indeed are not lying to you and they have real quantum computers. But if they cannot win it with more than 75% then you would easily refute their claims. Isn’t this amazing?

These types of verification procedures is something that researchers around the world are currently actively working on. This is a very important problem because various large companies, such as IBM, Google, and Microsoft are trying to build a quantum computer. If they claim they have built one, you would probably believe them more than your classmates. However, it is still great if you can actually verify this!