EPR paradox

This post attempts to model the EPR paradox with a very simple quantum computer. That way, we won't understand the weirdness, but at least we'll understand that it is weird.

This post is a follow up to two other posts: understanding quantum computation and the double-slit experiment.

I said that the double slit experiment convinced me that quantum stuff was weird. The EPR paradox failed to convince me, at first. I remember hearing something about two particles heading off in different directions, and when people observed the particles, it miraculously turned out that some property about them was always the same. If one was observed to be positive, then the other one would turn out to be positive as well. And then they'd go on to say how this would be true even if the particles were observed lightyears apart from each other.

But I thought, maybe the particles agreed on a value right from the start, before going lightyears apart from each other. And they would say, no no that's impossible! Quantum particles only decide what to be when you observe them! And I wasn't convinced.

But now I am convinced, and I will attempt to convince you with a simple quantum computer.

Simple Model

This section will be easier to understand after reading understanding quantum computation and the double-slit experiment, and will use the copy, random and half-random gates from those posts.

Our computer will start with two qubits which we'll initialize to 0. Next, we'll send the first qubit through a random gate, so that it is either a 0 or a 1. Then we'll send both qubits through a copy gate, so that the value of the first qubit is sortof copied into the second qubit. We actually did this in the Copy Gate section of understanding quantum computation, and the result is a state like this [sqrt(.5), 0, 0, sqrt(.5)], where there's a 50% chance that both qubits are 0, and a 50% chance that both qubits are 1.

Now, we ship one qubit to Alice and the other to Bob, who live lightyears apart. And if Alice opens her qubit and sees a 1, then "miraculously" Bob's qubit will also have a 1 inside. So far, the "they were both the same to begin with" theory is looking ok.

But What If...

But what if Alice and Bob both have a random gate lying around that they could pass their qubit through before opening it. Then there are four possibilities: they could both not use the gate, Alice could but not Bob, Bob could but not Alice, or they both could.

We can represent each possibility with a matrix. If neither uses the random gate, then it's just an identity matrix like this [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]].

If Alice uses it, but not Bob, then we need some Kronecker product magic to combine the random gate matrix [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]] with a 2x2 identity matrix like this: [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]] ⊗ [[1, 0], [0, 1]] = [[sqrt(.5), 0, sqrt(.5), 0], [0, sqrt(.5), 0, sqrt(.5)], [sqrt(.5), 0, -sqrt(.5), 0], [0, sqrt(.5), 0, -sqrt(.5)]].

If Bob uses it, but not Alice, then we need to use the Kronecker product in the opposite order like this: [[1, 0], [0, 1]] ⊗ [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]] = [[sqrt(.5), sqrt(.5), 0, 0], [sqrt(.5), -sqrt(.5), 0, 0], [0, 0, sqrt(.5), sqrt(.5)], [0, 0, sqrt(.5), -sqrt(.5)]].

If they both use it, then we need to Kronecker two random gates together -- like we did at the end of the Copy Gate section mentioned above -- which goes like this: [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]] ⊗ [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]] = [[.5, .5, .5, .5], [.5, -.5, .5, -.5], [.5, .5, -.5, -.5], [.5, -.5, -.5, .5]].

Now let's multiply our state [sqrt(.5), 0, 0, sqrt(.5)] by each possibility:

If neither Alice nor Bob uses a random gate, then we get: [sqrt(.5), 0, 0, sqrt(.5)] * [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]] = [sqrt(.5), 0, 0, sqrt(.5)]. This means they'll either both see a 1, or they'll both see a 0, each with 50% probability.

If Alice uses a random gate, but not Bob, then we get: [sqrt(.5), 0, 0, sqrt(.5)] * [[sqrt(.5), 0, sqrt(.5), 0], [0, sqrt(.5), 0, sqrt(.5)], [sqrt(.5), 0, -sqrt(.5), 0], [0, sqrt(.5), 0, -sqrt(.5)]] = [.5, .5, .5, -.5]. Squaring each number gives us a 25% chance of each possibility. So the contents of their respective qubits will be like the outcomes of two independent coin flips.

If Bob uses a random gate, but not Alice, then we get: [sqrt(.5), 0, 0, sqrt(.5)] * [[sqrt(.5), sqrt(.5), 0, 0], [sqrt(.5), -sqrt(.5), 0, 0], [0, 0, sqrt(.5), sqrt(.5)], [0, 0, sqrt(.5), -sqrt(.5)]] = [.5, .5, .5, -.5]. This is what we saw if just Alice used a random gate. So if just one person uses a random gate, then the outcomes of their qubits will be like two independent coin flips.

If both Alice and Bob use a random gate, then we get: [sqrt(.5), 0, 0, sqrt(.5)] * [[.5, .5, .5, .5], [.5, -.5, .5, -.5], [.5, .5, -.5, -.5], [.5, -.5, -.5, .5]] = [sqrt(.5), 0, 0, sqrt(.5)]. This is what we saw if neither used a random gate. So if they both use or don't use a random gate, then they'll both see the same random outcome.

So this is a little weird. At first glance, it seems like the qubits sent to Alice and Bob need to communicate over lightyears of space to say whether or not they went through a random gate, so that they know whether to be the same as each other or not.

Of course, the qubits could also decide ahead of time what to do in each case. For instance, Alice's qubit could say: "If Alice opens me right away, I'll be a 0, but if she first sends me through a random gate, then I'll be a 1." And then Bob's qubit could agree and say: "Ok, so I'll also be a 0 if Bob opens me right away, and a 1 if he first sends me through a random gate."

And of course the outcomes need to appear appropriately random if the experiment is repeated a bunch of times, so they could agree on a sequence of things to be in each repetition of the experiment. Let's say the experiment will be repeated ten times. The qubits could represent what they'll do in every possible case with two strings of ten bits, like 0110100111 and 1010101001. The first bit in the first sequence says what each qubit will be in the first trial of the experiment if that qubit is not sent through a random gate. The first bit in the second sequence says what each qubit will be in the first trial of the experiment if that qubit is sent through a random gate. And the next bit in each sequence says what to do in the second trial of the experiment. And so on.

Note that the two sequences need to have certain properties, so that the qubits can fool us all into thinking that true randomness is happening. First, each sequence needs to appear random. Second, the sequences need to appear uncorrelated with each other. That is, knowing a bit in the first sequence shouldn't tell us anything about the corresponding bit in the second sequence. Of course, the qubits can achieve both of these goals if they create each sequence by flipping a coin over and over, which seems easy enough.

But What If Also...

But what if Alice and Bob both also have a half-random gate lying around that they could pass their qubit through before opening it. And let's say that they'll choose to use their random gate or their half-random gate or neither gate before opening their qubit. Then there are nine possibilities. If we represent not using a gate with n, using a random gate with r, and using a half-random gate with h, then the possibilities are: nn, nr, nh, rn, rr, rh, hn, hr, and hh, where "nr" represent Alice not using a gate, and Bob using a random gate.

We can represent each possibility with a matrix. To reduce our work, we'll note that the outcomes are going to be symmetric for cases like nr and rn, as we saw above. So we really have six possibilities: nn, nr, nh, rr, rh, and hh, and we already know the matrix for nn, nr, and rr, from above, so we just need a matrix for nh, rh and hh.

The matrix for nh is: [[1, 0], [0, 1]] ⊗ [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]] = [[cos(π/8), sin(π/8), 0, 0], [sin(π/8), -cos(π/8), 0, 0], [0, 0, cos(π/8), sin(π/8)], [0, 0, sin(π/8), -cos(π/8)]].

The matrix for rh is: [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]] ⊗ [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]] ≈ [[.653, .271, .653, .271], [.271, -.653, .271, -.653], [.653, .271, -.653, -.271], [.271, -.653, -.271, .653]].

The matrix for hh is: [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]] ⊗ [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]] ≈ [[.854, .354, .354, .146], [.354, -.854, .146, -.354], [.354, .146, -.854, -.354], [.146, -.354, -.354, .854]].

Now let's multiply our state [sqrt(.5), 0, 0, sqrt(.5)] by each new possibility:

For nh we get: [sqrt(.5), 0, 0, sqrt(.5)] * [[cos(π/8), sin(π/8), 0, 0], [sin(π/8), -cos(π/8), 0, 0], [0, 0, cos(π/8), sin(π/8)], [0, 0, sin(π/8), -cos(π/8)]] ≈ [.653, .271, .271, -.653], which agrees with what we saw in the symmetric hn situation in the double-slit experiment post. When we square these values, we get about [.427, .073, .073, .427], meaning there's a .427 + .427 ≈ 85% chance that both Alice and Bob's qubits are the same as each other, and a .073 + .073 ≈ 15% chance that their qubits are different.

For rh we get: [sqrt(.5), 0, 0, sqrt(.5)] * [[.653, .271, .653, .271], [.271, -.653, .271, -.653], [.653, .271, -.653, -.271], [.271, -.653, -.271, .653]] ≈ [.653, -.271, .271, .653]. When we square these values we get about [.427, .073, .073, .427], which is the same as nh above.

For hh we get: [sqrt(.5), 0, 0, sqrt(.5)] * [[.854, .354, .354, .146], [.354, -.854, .146, -.354], [.354, .146, -.854, -.354], [.146, -.354, -.354, .854]] ≈ [.707107, 0, 0, .707107], which looks a lot like [sqrt(.5), 0, 0, sqrt(.5)], which we recognize as meaning that both Alice and Bob will see the same outcome, be it a 0 or a 1.

Let's summarize what's going on. If both Alice and Bob use the same gate -- either nn, rr or hh -- then they'll both see the same outcome. If one person uses a random gate, and the other person uses no gate, then the outcomes will be completely uncorrelated. And if one person uses a half-random gate, and the other person uses either a no gate or a random gate, then there's an 85% chance that they'll both see the same outcome.

Now let's imagine a scenario like before where there are going to be ten repetitions of the experiment, and the qubits are trying to decide ahead of time what to do in each case. They'll now need three sequences of bits to cover the three possible decisions each person could make: no gate, random gate, or half-random gate.

Now what constraints do they need to place on the sequences? First note that the sequences will be the same for each qubit, since they need to make sure that if both Alice and Bob do the same thing to their qubit, then they'll each observe the same value when they open their qubit -- this covers the nn, rr and hh cases.

We recall from before that the sequences will need to appear random, and that the first and second sequences should be uncorrelated, to account for the nr (or symmetric rn) case.

Now we just need to account for the nh and rh (or symmetric hn and hr) cases. In the nh case, Alice uses no gate, and Bob uses a half-random gate, and we saw that there is an 85% chance that they both see the same outcome. Hence, the first sequence needs to be 85% correlated with the third sequence. That is, 85% of the time, the bit we see in the first sequence should be the same as the bit we see in the third sequence. In the rh case, there is also an 85% chance that both Alice and Bob see the same thing. This means that there is also an 85% correlation between the second sequence and the third sequence.

So we have three random sequences of bits. The first sequence is uncorrelated with the second sequence, but both the first and second sequences are 85% correlated with the third sequence.

It turns out this is impossible. The best we can do is make the third sequence 75% correlated with the first and second sequences. We could do this as follows: whenever the first and second sequences have the same bit, make the third sequence also have that bit. This will happen 50% of the time, since the first two sequences are uncorrelated. The rest of the time, the first and second sequences will have a different bit, so the third sequence can't be the same as both of them, so it will need to choose. If we align with the first sequence half the time, and the second sequence half the time, then we'll get our 75% correlation with both sequences. We could become more correlated with one sequence, but only by becoming less correlated with the other sequence. Hence, it is impossible to be 85% correlated with both sequences.

This means that the qubits can't decide ahead of time what to do in each case in such a way that they can satisfy all the possible expected outcomes. Whatever they chose to do, Alice and Bob could happen to use their gates in such a way that they would expect to see a certain correlation -- based on their quantum mechanical understanding -- that would be violated. For instance, if the qubits decided to have the third sequence be 85% correlated with the first sequence, meaning that the second sequence wasn't 85% correlated with the third sequence, then Alice could use a random gate and Bob could use a half-random gate every time, such that the correlation should be 85%, but wouldn't be.

Conclusion

And that is the paradox: Alice's qubit must magically know what sort of gate Bob's qubit passed through in order to decide what to do, and vice versa. But this would suggest some sort of faster-than-light communication, since Alice and Bob are lightyears apart.

A consequence I thought would come from this is the ability to communicate across great distances instantly. But no. This technique can't actually be used to send messages between Alice and Bob. From either person's perspective, their qubit is randomly a 0 or a 1 no matter what sort of gate they pass it through. It is only when they meet each other again to compare notes about their observations that they see spooky correlations.

The real consequence has to do with how we model the universe. As computer scientists, we might try to model everything as a giant cellular automaton (like the game of life), where each cell is like a point in space which contains a particle or doesn't. And it would be nice if the laws of the universe were simple cellular automaton update rules applying to each cell based on nearby cells. However, the EPR paradox suggests that this doesn't work. Sometimes a cell will need to know something about a very distant cell. Hence, if we wanted to use a cellular automaton to model the universe, it seems like the update rules for each cell would need to examine every other cell in the system, which seems very complicated and messy. Alas.