EPR Paradox: What's paradoxical about it?

The EPR Paradox is the one where two particles go lightyears apart from each other, and when someone observes one and sees that it's positive, it turns out that the other one is negative. And the physicist is like: "Spooky! How did the other one know to be the opposite?" And you're like: "Uh.. they chose to be that way to begin with?"

But the setup isn't quite that simple. It's more like this:

Imagine an old box maker makes two boxes. Each box has three buttons on top: a red button, a green button and a blue button. Pressing a button opens the box, revealing a coin. The coin might be heads up or tails up.

The box maker claims that the first time the boxes are opened, the following is true: if one box is opened by pressing the red button and the other box is opened by pressing the blue button, then the coin sides will be different — one heads and one tails. Otherwise, the coin sides will be the same. This is true even if the boxes are first opened lightyears apart from each other.

If you can explain how the boxes work without faster-than-light communication, then you have "solved" the EPR Paradox.

update: Another thing worth pointing out is that although faster-than-light communication appears to take place in this setup, this does not imply that the boxes can be used to actually communicate anything. I didn't say this above, but an extra claim about the boxes is that the first box to be opened, no matter how it is opened, has a 50% chance of showing heads or tails.

Hence, the second box to be opened, in the absence of knowledge about what happened with the first box, also appears to have a 50% chance of showing heads or tails. It is only when the box openers get together later and compare their results that they'll notice that their coins are the same or different according to which buttons they both pressed.

many worlds interpretation

By looking at the figure on Wikipedia for the many-worlds interpretation of quantum mechanics, it seems like universes branch off as "observations" are made, where the outcome of the observation is one thing in one branch (e.g. cat dead), and another thing in the other branch (e.g. cat alive).

However, I think the many-worlds interpretation is more like: all possible universes always exist, with different amounts of probability, and these probabilities shift over time. And the way they shift depends on the distribution of probability, which seems to imply that the future of our current universe depends in part on the probability of various parallel universes.

This in turn implies that there isn't really one version of history, but rather, the current state of our universe feeds from a distribution of possibilities for our immediate past. I think this is what is meant by the statement in Wikipedia: "Many-worlds implies that all possible alternative histories ... are real".

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.

double-slit experiment

This post attempts to model the double-slit experiment with a very simple quantum computer. That way, we won't understand the weirdness, but at least we'll see some simple math that reproduces it.

This post is an update to a previous post, and it may be helpful to read that one first.

The double slit experiment convinced me that quantum stuff was weird. The experiment goes something like this. We shine a light at two thin slits near each other, and we expect to see two thin bars of light on the other side. However, somehow the thinness of the slits causes the light to spread out, as if the photons are hitting the sides of the slits and being deflected. But that's not all. If the light just spread out behind each slit, we would expect to see two wider patches of light, but instead we see many bands of light.

The common explanation is that the light is behaving like a wave, where the bands of light are analogous to water waves from two pebbles dropped in a lake interfering with each other.

However, if we dim the light so that only one photon is going at a time, we still see the interference pattern. This is weird because it suggests that a single photon must somehow be going through both slits, and then interfering with itself.

At this point, someone got the bright idea to try and detect which slit each photon went through. I don't know how they do that. It seems impossible to "see" a photon. But they manage, and when they do, they see the photon go through one slit or the other, but the interference pattern goes away. This leads people to scratch their heads and say things like "quantum stuff is all crazy and wave like until you observe it, and then it quickly shapes up and acts normal".

Simple Model

Now let's model what's going on with a simple quantum computer. This section will be easier to understand after reading this post, and will use the random and copy gates from that post.

At first, our computer will involve a single qubit. This qubit represents the photon. The qubit can be 0 or 1. We'll say that 0 is analogous to a photon in the double-slit experiment going through the first slit, and 1 is analogous to the photon going through the second slit.

Next, we need to model the "spreading out" of the photon after it goes through a slit. We'll do this with a gate called half-random. The gate works like this: if we send a 0 through it, then it will probably stay a 0, but it might change to a 1. If we send a 1 through it, then it will probably stay a 1, but it might change to a 0. This is meant to represent a photon going through a slit and probably hitting the wall directly behind that slit, but maybe hitting somewhere else.

The matrix for the gate is [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]]. We can model sending a 0 through it, by first recalling that a 0 is represented with the state vector [1, 0], and then doing some matrix multiplication [1, 0] * [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]], which is [cos(π/8), sin(π/8)]. If we square each element to get the probabilities, we get [0.85, 0.15], which is an 85% chance of seeing 0, and a 15% chance of seeing 1. If we send a 1 through it, I swear that the opposite happens: there's a 15% chance of seeing a 0, and an 85% chance of seeing a 1.

Now we just need something to simulate firing a photon at the two slits such that we don't know which slit it goes through. We'll do this by taking a qubit and sending it through a random gate. The matrix for this gate is [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]]. If we initialize our qubit to 0 and send it through this gate, it enters the state [sqrt(.5), sqrt(.5)]. When we square each element to get probabilities, we get [.5, .5] which is a fifty-fifty chance of being a 0 or a 1, which seems random enough.

So what happens when we send a qubit first through random, simulating firing a photon at the two slits and not knowing which one it went through, and then sending the qubit through half-random, simulating the photon "drifting" from the slit it went through before it hits the wall? I claim that if this wasn't a leading question, people would guess that it would remain a fifty-fifty split between 0 and 1, since a 0 has as much chance to drift to 1 as a 1 has to drift to 0.

Let's try it. We initialize our qubit to 0, which is the state [1, 0]. After it goes through random it becomes [sqrt(.5), sqrt(.5)], as we saw above. Next we multiply this by the half-random matrix like so [sqrt(.5), sqrt(.5)] * [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]], yielding [0.92, -0.38]. When we square these we get [0.85, 0.15], which is an 85% chance of seeing a 0, and 15% chance of seeing a 1.

I claim that this strange non-even distribution of probability is analogous to the interference pattern we see in the double slit experiment. Of course, with the light, there are many places each photon can end up on the wall, so there is room to create fancy looking interference patterns. In our simplified version, there are only two places the qubit can end up: 0 or 1. So really, anything that isn't a fifty-fifty split is as close to a "fancy interference pattern" as we can get.

Observation

We want to simulate observing which slit the photon passes through. We could do this by simply opening the qubit after passing it through the random gate. This would force it to be a 0 or a 1, and when we sent it along through the half-random gate, that gate would behave as expected, without any interference pattern. But somehow this feels like cheating. It feels like someone stopping the photon before it passes through a slit, and then sending an entirely new photon out the back of the slit toward the wall.

Somehow we want to "observe" the qubit without actually opening it. We can do this with a copy gate. We'll send a qubit through random, then we'll send that qubit along with a fresh 0 qubit into copy. Now we have two copies of the first qubit, or as close as we can get, so we can send one through half-random, and we can open the other one to see what the qubit was before sending it through half-random.

The first half of this we've already done in the previous post, sending one qubit through random, and then copying that qubit. The result is: [sqrt(.5), 0, 0, sqrt(.5)], which is a 50% chance that both qubits are 0, and a 50% chance that both qubits are 1.

We saw before that we can't decompose this into a state vector for each qubit, i.e., they are entangled. So we need to treat the action of sending one qubit through half-random and leaving the other qubit alone as a single gate. We can model "leaving a qubit alone" with a do-nothing gate represented by an identity matrix. Next we need to do some Kronecker product magic to combine the matrices for these gates together: [[cos(π/8), sin(π/8)], [sin(π/8), -cos(π/8)]] ⊗ [[1, 0], [0, 1]], which yields [[cos(π/8), 0, sin(π/8), 0], [0, cos(π/8), 0, sin(π/8)], [sin(π/8), 0, -cos(π/8), 0], [0, sin(π/8), 0, -cos(π/8)]].

Now the moment of truth. We multiply our state vector [sqrt(.5), 0, 0, sqrt(.5)] by the large harry matrix we just created like so [sqrt(.5), 0, 0, sqrt(.5)] * [[cos(π/8), 0, sin(π/8), 0], [0, cos(π/8), 0, sin(π/8)], [sin(π/8), 0, -cos(π/8), 0], [0, sin(π/8), 0, -cos(π/8)]], giving us about [0.653, 0.271, 0.271, -0.653]. If we square these values we get about [0.427, 0.073, 0.073, 0.427]. These probabilities are associated with the states 00, 01, 10 anad 11, where the first bit in each state represents the first qubit which went through the half-random gate, and the second bit represents the second qubit which we left alone.

So what is happening here. If the second qubit is a 0, meaning we think that the first qubit was a 0 before entering the half-random gate, then there's a 0.427/(0.427 + 0.073) ≈ 85% chance that the first qubit is a 0. This is what we would expect if the first qubit really was a 0 before entering the half-random gate. So no interference so far. Also, if the second qubit is a 1, meaning we think that the first qubit was a 1 before entering the half-random gate, then there's a 0.427/(0.427 + 0.073) ≈ 85% chance that the first qubit is a 1. This is also what we would expect if the first qubit really was a 1 before entering the half-random gate. So no interference at all.

I claim that this is analogous to the elimination of the interference pattern in the original double-slit experiment when experimenters were able to sneakily detect which slit a photon went through, without disturbing the photon.. too much. Note that we don't actually need to open the second qubit in order for the interference to go away. The fact that we could open it is enough.

Philosophy of Observation

This business of "observation" in quantum mechanics is a bit of a contentious issue. I keep saying we "open" a qubit to see what's inside, and this action causes the qubit to become either definitely 0 or definitely 1, destroying whatever strange probabilistic state it was in before.

But, it seems like quantum mechanics is the model of how everything works. And we, as experimenters, are also part of everything. Which suggests that we are just qubits, in the same quantum system as our experiments. So how can we "open" the qubits in our experiment? That would be like part of a quantum computer opening the qubit of another part of the quantum computer. But this can't happen, because opening a qubit is destructive — it changes the state of a qubit to be exactly 0 or 1, forgetting what it could have been — and we believe quantum computation is reversible, so destruction is not possible.

I think the answer lies in the simple quantum computer we built above. The copy gate (which is not destructive, since it only copies if the second qubit is 0, so we know if both qubits are the same afterwards that the original second qubit was a 0) entangles one qubit with another. This entanglement is "observation" in the quantum sense. That is, if we think we're observing the contents of a qubit, what's really happening is that the qubits in our brain have become entangled with the qubit, and the giant state vector of the universe has some analog of the state [sqrt(.5), 0, 0, sqrt(.5)] where there's a 50% chance that the qubit was a 0 and our brain believes it was a 0, and a 50% chance that the qubit was a 1 and our brain believes it was a 1, and both of these states exist as far as the quantum universe is concerned. It's just that we as humans can't see the whole state vector of the universe. We can only "see" the state that represents a human believing it can see a particular state. I think that is what is meant by the many-world interpretation, but I'm not sure.

understanding quantum computation

"Intro" lectures on quantum computation for computer scientists are popular, because as computer scientists we want to know what's going on. But pretty quickly, the lecture starts using crazy symbols like |ψ⟩ and I get lost. Recently, I spent some time trying to break through this learning barrier, which involved getting stuck over and over. Now that I think I "get it", I figured I'd share. Of course, maybe I don't get it. Someone will tell me, I'm sure.

This blog post attempts to explain the core concepts of quantum computation using standard linear algebra, and many of the computations are links to Wolfram Alpha so you can see exactly what is going on.

A qubit is like a ball that can be opened. When we open — observe — the ball, there is a number written inside. The number can be 0 or 1. We can change the number if we want, and close the ball again.

A gate is like a box that we can send qubits through. Some gates can take more than one qubit at a time, but all the qubits that go into a gate will come out the other end. Gates typically change the numbers written inside the qubits that pass through them.

Random Gate

One day, we encounter a mysterious new gate. We want to know what it does, so we run some experiments. We take a qubit, set it to 0, and send it through the gate. When we open it, it is a 1. We try again — setting it to 0 again and sending it through the gate — but this time it comes out 0. We try many times, and half the time it comes out 0 and half the time it comes out 1, with no discernible pattern. If we send a 1 through the gate, we see the same thing: half the time it comes out 0 and half the time it comes out 1.

We call this gate random, since it seems to take our qubit and write a random number inside it.

Now one experimenter is testing the random gate, sending a 0 through it, recording the output, and setting the qubit to 0 again before sending it through the gate again. But one time, the experimenter forgets to open the qubit before sending it through the gate again. This time, they notice that the qubit is still 0. Coincidence perhaps. But they try sending it through the random gate twice in a row again, and again it comes out 0. They try again, and again it comes out 0. Every time they send a 0 twice in a row through the random gate, without opening it in between, it comes out 0. They try setting it to 1, sending it through the gate twice. It comes out 1. Every time. Every time they send a qubit through the gate twice in a row, it comes out the same as it started. This is an example of interference.

So we thought the random gate was just writing a random number inside the qubit, but this wouldn't explain the strange behavior where sending a qubit through the gate twice in a row leaves the qubit unchanged.

A model that seems to work for explaining the random gate goes like this: the state of a qubit is represented by two numbers. We'd like these numbers to represent the probability that the qubit is a 0 or a 1 respectively, but it will turn out to be useful for the numbers to be negative sometimes. Hence, we'll let the numbers be negative, and we'll square them to get the probabilities, which removes the negativeness.

So the square of the first number represents the probability that the qubit is a 0 when we open it. The square of the second number represents the probability that the qubit is a 1 when we open it. These probabilities must sum to one. When we open a qubit, it is either a 0 or a 1, but the information about what it could have been is lost forever — it is now definitely a 0 or a 1. If it is a 0 when we close it, then it is in the state [1, 0]. If it is a 1 when we close it, then it is in the state [0, 1].

The random gate is a 2x2 matrix. It looks like this [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]] (see Hadamard gate). We model sending a qubit through the gate by multiplying the qubit's state vector by the matrix. So if we send a 0 through the gate, that means we're sending a [1, 0] through the gate, which we model as [1, 0] * [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]], which equals [sqrt(.5), sqrt(.5)]. If we square each number, we get [.5, .5] which means 50% chance of 0 and 50% chance of 1. This models the fact that the qubit is random if we send it once through the gate.

Now if we don't open the qubit yet, it will stay in the state [sqrt(.5), sqrt(.5)]. And if we send it through the random gate again, then we model this as [sqrt(.5), sqrt(.5)] * [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]], which equals [1, 0]. If we square each number we still get [1, 0], which means 100% chance of 0, and 0% chance of 1. So that works. Sending a 0 through the gate once randomizes it, and sending the qubit through the gate again without opening it yields a 0 again.

If we send a 1 through the gate, we get a qubit in the state [sqrt(.5), -sqrt(.5)]. Note the negative sign in the second number. However, when we square each number, we get [.5, .5], which is 50% chance of 0, and 50% chance of 1. So sending a 1 through the random gate still randomizes it, even though the state vector is slightly different than the state vector we got when we sent a 0 through the random gate.

Now if we don't open the qubit, and send it through the random gate again, then we model this as [sqrt(.5), -sqrt(.5)] * [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]], which equals [0, 1]. If we square each number, we still get [0, 1], which means 0% chance of 0, and 100% chance of 1. So that works too. Sending a 1 through the gate once randomizes it, and sending the qubit through the gate again without opening it yields a 1 again.

Copy Gate

One day we encounter another mysterious gate. It has two input holes labeled source and dest. It seems to copy the number written in the source qubit into the dest qubit. Well, almost. It copies like this if the dest qubit is a 0. But if the dest qubit is a 1, then it copies the opposite of the source qubit to the dest qubit. But we can avoid this disturbing behavior by always sending a 0 into the dest.

We call this gate copy, since it seems to copy one qubit to another, as long as the dest is a 0.

So what happens if we take a 0 and send it through a random gate, and then copy this qubit by sending it into the source of a copy gate along with a fresh 0 in the dest of the copy gate? The state of the source qubit is [sqrt(.5), sqrt(.5)], so maybe now both qubits have the state [sqrt(.5), sqrt(.5)]?

If so, then if we open both qubits, we would expect the result to be like flipping two coins, with an equal probability of seeing heads-heads, heads-tails, tails-heads and tails-tails. However, if we perform the experiment, we notice that the qubits might be 0 or 1, but they are always the same as each other, which is weird. It's like flipping two coins and only getting both heads or both tails.

So maybe the copy gate "opened" the source qubit, setting its state to [1, 0] or [0, 1], and then that was copied?

If so, then if we send each qubit coming out of the copy gate into a random gate, each qubit should be randomized to [sqrt(.5), sqrt(.5)] or [sqrt(.5), -sqrt(.5)], and we should have the two coin flip situation again. However, if we run the experiment, sending each qubit through a random gate, they are still the same when we open them.

So our model appears to be broken again. Even using two numbers to represent each qubit, we can't model the strange behavior we see from the copy gate.

A model that seems to work for explaining the copy gate goes like this: the state of n qubits is represented by 2ⁿ numbers. We'd like these numbers to represent the probability that the qubits are in each possible configuration. For instance, if there are three qubits, then there are 2³ or 8 numbers representing the probability of being in the configurations 000, 001, 010, 011, 100, 101, 110, and 111. As before, we'll square each number to get the actual probability of being in each configuration.

The copy gate operates on two qubits, so we can represent the qubits using 2² or 4 numbers. In our scenario, we have one qubit in the state [sqrt(.5), sqrt(.5)], and another in the state [1, 0]. We want to get the probability of being in the states 00, 01, 10, and 11. The probability of 00 is the probability of both qubits being 0, which seems easy enough to calculate by multiplying these probabilities together. However, if we multiply the probabilities together, we'll always get a positive number, whereas we'd like to keep around the possibility for negative numbers, so we multiply the square roots of the probabilities together instead. Which works, apparently. So if our states are [a, b] and [c, d], then our resulting four element state vector is [a*c, a*d, b*c, b*d] — this is called a Kronecker product, and can be written like [a, b] ⊗ [c, d] — and the result in our case is [sqrt(.5), 0, sqrt(.5) 0]. If we square each number we get [.5, 0, .5, 0], which is a 50% chance of 00, and a 50% chance of 10, meaning the first qubit is a 0 or 1, but the second qubit is definitely a 0, which sounds like what we had to begin with.

The copy gate itself is a 4x4 matrix. It looks like this [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]] (see CNOT gate). When we multiply our state vector by this matrix we get [sqrt(.5), 0, sqrt(.5) 0] * [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]], which is [sqrt(.5), 0, 0, sqrt(.5)]. If we square each number we get [.5, 0, 0, .5], which is a 50% chance of 00, and a 50% chance of 11, meaning that either both qubits are 0, or both qubits are 1. That's good so far: we've modeled the fact that the qubits are always the same as each other when we look at them after going through the copy gate.

Next we want to send each qubit through another random gate. In order to do so, we'd like to decompose the state [sqrt(.5), 0, 0, sqrt(.5)] into a separate vector for each qubit. We'd like two vectors [a, b] and [c, d] such that [a, b] ⊗ [c, d] = [sqrt(.5), 0, 0, sqrt(.5)]. But this turns out to be impossible. Imagine that we had two vectors [a, b] and [c, d] such that [a*c, a*d, b*c, b*d] is [sqrt(.5), 0, 0, sqrt(.5)]. This would mean that a*d=0, so either a or d is 0. Also, a*c=sqrt(.5), so a and c are both not 0. This means that d is 0. But b*d=sqrt(.5), which means d can't be 0. This is a contradiction, meaning we can't find any vectors [a, b] and [c, d] that work like we want. This inability to decompose a state vector into separate state vectors for each qubit is called entanglement.

So how do we model sending each qubit through another random gate? Well, if we can't decompose the state vector, maybe we can treat the two random gates as a single random gate that acts on two qubits. We do this the same way we combine state vectors for qubits to get larger state vectors for multiple qubits: with the Kronecker product: [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]] ⊗ [[sqrt(.5), sqrt(.5)], [sqrt(.5), -sqrt(.5)]], which yields: [[.5, .5, .5, .5], [.5, -.5, .5, -.5], [.5, .5, -.5, -.5], [.5, -.5, -.5, .5]]. This is a 4x4 matrix just like we wanted.

Now let's send our qubits through the combined random gate by doing [sqrt(.5), 0, 0, sqrt(.5)] * [[.5, .5, .5, .5], [.5, -.5, .5, -.5], [.5, .5, -.5, -.5], [.5, -.5, -.5, .5]], which is yields [sqrt(.5), 0, 0, sqrt(.5)]. If we square each number we get [.5, 0, 0, .5], which is a 50% chance of 00, and a 50% chance of 11, like we saw before. So even if we send each qubit through a random gate and look at them, they're still the same, which means our model explains what we saw.

The Matrix

By the way, there are a few interesting things to note about the matrices we keep seeing. First, they are always square. This makes sense because when we multiply a state vector with n elements by a matrix, we want a state vector with n elements as a result, since all the qubits that enter a gate also leave the gate.

Second, the result of multiplying a state vector by a matrix should actually be a state vector, meaning if we square all the elements of the new vector to get probabilities, these probabilities should sum to one. And of course, a gate can't prevent us from shoving qubits in any valid state into it, so any valid state vector multiplied by the matrix should be a valid state vector.

This second constraint turns out to make the matrices unitary. Unitary matrices have many nice properties. For instance, every row in the matrix is itself a valid state vector. In fact, the top row is what the result will be if the input state vector has a one as the first number, and zeroes for all the rest. It also happens to be the case that each row is orthogonal to all the rest, i.e., if we take the dot product of any two rows, we'll get zero.

Also, unitary matrices are always invertible. In fact, they are easy to invert. We just take the transpose. The fact that the matrices are always invertible means that we could, in theory, figure out what the original state vector looked like by running a computation in reverse, assuming we knew what the final state vector looked like. This is what people mean when they say that quantum computation is reversible.

What Am I Leaving Out?

• I say that state vectors consist of the square roots of probabilities, whereas real quantum people allow imaginary numbers, and call them probability amplitudes. Everything I said is true for real numbers, but if we want to generalize it to support imaginary numbers, we need to make some changes involving complex conjugates and conjugate transposes. The main change is that instead of squaring a probability amplitude to get the probability, we need to multiply it by its complex conjugate — of course, if it's a real number, then this is the same as squaring it. I left out imaginary numbers because I don't know of any motivating experiments that show their usefulness. As far as I can tell, all the stuff we're told is "weird" about quantum mechanics can be modeled without imaginary numbers. But I'm sure someone will point out a case that requires them.

• I use row vectors to represent state vectors, whereas real quantum people use column vectors. This means they need to multiply all the matrices in reverse order, which I find confusing. It also means that their matrices will look like the transpose of my matrices. Of course, I'm only really using two matrices in this post, one for the random gate, and one for copy, and both of these happen to be their own transpose, so if you look up the matrices for these gates online (where they'll be called Hadamard and CNOT), they'll look the same.

Future Work

In subsequent posts, I'll try to explain two popularly weird quantum phenomena in terms of simple quantum computation: the double-slit experiment, and the EPR paradox. I'll also give my take on what's going on when we "observe" a qubit, and how that is related to the "many-worlds interpretation" of quantum mechanics.