oh github pages

I didn't realize it, but the little webpage http://dglittle.github.com/smiley-slider on github that shows the smiley-slider in action had been broken. Whenever people would go to dglittle.github.com/smiley-slider, they would be redirected to glittle.org/smiley-slider, which was nothing -- a 404.

This redirection happened as a result of me setting up my homepage glittle.org to be served from github, which involved having github redirect dglittle.github.com to glittle.org. Apparently this breaks all my project pages.

This behavior is apparently foretold in a tip at the bottom of this article. Paraphrasing, it says: project pages like dglittle.github.com/smiley-slider will be redirected to things like glittle.org/smiley-slider unless they have a file telling them to redirect somewhere else. Of course, the very next tip says that they won't actually be redirected anywhere if there is such a file.

Which is strange. But great. It means that maybe I can fix my problem by adding a file to the smiley-slider repo telling it to redirect to some bogus domain, like example.com (except specifically not example.com, since github knows that that domain is bogus), which would cause it not to redirect anywhere. In particular, causing it to not redirect to glittle.org/smiley-slider, which is nothing -- a 404.

This did work. Sortof. I thought the behavior would be that it wouldn't redirect dglittle.github.com/smiley-slider anywhere, but the actual behavior is that it does redirect dglittle.github.com/smiley-slider to glittle.org/smiley-slider just like before, except that miraculously, glittle.org/smiley-slider shows the content held in the smiley-slider repo. And I have no idea what it would show if the homepage repo happened to have a directory called smiley-slider.

Anyway, I'm confused, but it seems to work. However, this means I need to put a bogus file in all my projects telling github that they are being served on some domain that they are not being served on. I suppose one alternative is to have my homepage in a regular project, so it doesn't cause dglittle.github.com to redirect, but that would mean having my homepage it a github branch called gh-pages, rather than master, which seems confusing, but maybe less confusing.

[update: now I do have my homepage in a regular project so it doesn't cause dglittle.github.com to redirect]

DotTracker

..going through old crap, I found this "DotTracker" program. It's something I wrote in undergrad for, um, tracking colored dots in video. Here's a description of the algorithm I found in a file appropriately labeled "writeup of algorithm.txt", though I can tell it's a rough draft, because the file has above it some text where I was obviously writing a new/better description, but never finished:

Orange Dot Tracking Algorithm

Consider a "tracker" to be an object capable of tracking a moving dot in a video sequence.

The tracker is defined by a center, a color, and a size:

center - the x,y position of the tracker within a frame of video; this variable is updated every frame

color - the color that the tracker is tracking; this variable is initialized to the color of the pixel that the user clicks on when "placing" a tracker. This variable NEVER CHANGES once it is initialized.

size - the algorithm essentially examines a square set of pixels centered around the "center" of the tracker; the "size" variable defines the size of this square.

The crux of the tracking algorithm is an update function which centers the tracker on a splotch of color.

Here's an image in that directory that I used for testing. Note that the dots on my arm are not orange, but green. Apparently the algorithm could track any color, not just orange ;)

The code is now on github: https://github.com/dglittle/DotTracker

reduction

When talking about computer sciency problems -- the sort of problems that people like to call NP-complete and such -- people often say things like "problem A can be reduced to problem B".

The word reduce is confusing to me.

This "reduction" makes it sound like a large problem called A is becoming smaller -- reducing in size -- so it can fit somehow in B.

But that's wrong. B is generally a bigger and harder problem than A.

For example, we might "reduce" the problem of finding the maximum number in a set of numbers to the problem of sorting the numbers. That is, we can sort the numbers, and then we'll get the maximum number for free by looking at the last number in the sorting. But sorting is harder than finding the max, so we didn't really reduce the size of the problem of finding the maximum number when we sorted the numbers -- we did more work than we needed to.

So, I propose that we stop saying "reduce", and saying something like "embed" or "express in terms of".

I can embed the problem of finding the maximum number into the problem of sorting numbers, or I can express the problem of finding the maximum number in terms of the problem of sorting numbers.

arguing

My uncles have lively discussions -- arguments one might call them. I have inherited the trait of enjoying arguing, and I can get pretty emotionally vested in them.

My philosophy of arguing changed a bit when I did debate in High School. Since I was forced to argue both sides of each topic, I grew to feel that both sides of every argument were "right". Of course, the topics tended to be chosen for having good points on both sides.

In any case, I'm not sure whether both sides of an argument are "right", but here's a made-up word-to-the-wise about arguing:

You can only truly win an argument if you can argue in favor of your opponent's side better than they can.

homesick sentimental scenes

Occasionally I get this feeling of.. not sure what to call it.. homesick? sentimental? It's a good feeling. I think. I can't quite put my finger on it.

Anyway, here are some situations, mental images, where the feeling comes up for me:

1. The image of a car in the country leaving home, at night, on a long journey.

2. Cars in the rear view mirror on the freeway at night, with their headlights reflected on the freeway surface.

3. Outside a high, flat, featureless wall of an arabian night's style building, at night with the moon shining, where the whole scene is clean and pristine, and nobody's around.

4. Being inside a car during a rainstorm.

I see a couple themes here: cars and night time.

singularity

I had a little conversation with a friend today about the "singularity" -- the name commonly given to the idea of what will happen to humanity as people can be wired together with computers, and computers become powerful enough to simulate human level intelligence.

A couple things occurred to me. First, although I believe that something like the singularity will eventually happen in reality, I also want it to happen, and so it's hard to know if my belief in the singularity is distorted by that desire, in the way some people might accuse religious people of just wanting religion to be true so they don't think life is meaningless.

Second, I have a somewhat unconventional view of my hopes for the singularity. A lot of people who believe in the singularity see it as a way for man to become immortal, which is an appealing way to avoid the modern "scientific" belief that death is the complete end of a human's existence.

I don't have that belief though. I told my friend that I wasn't concerned if I made it to the singularity or not. And he pressed me about why. And it forced me to articulate my reason, which is this: I'm not sure I'll make it to the singularity. I might die first. And I can't prevent the possibility of my death, no matter what I do. So I want a view of the singularity that makes it "ok" if I die tomorrow.

Incidentally, my belief -- that makes it "ok" to die tomorrow -- is something along the lines of believing that the universe is on a course toward greater intelligence, which is somehow weirdly inevitable by the laws of nature -- the strange force that causes life to arrise and tend toward more complex and interesting life. And I am a part of that. I am programmed to act as a sort of neuron in the brain of humanity, and I can't help myself but do that. That is, whether I like it or not, it seems like that's what I do, and I've decided that I like it. It makes me less concerned about what happens to Greg, allowing me to concentrate more on "solving problems", which is what my programming tells me to do anyway (which is a bit circular I realize, since no matter what I do, or what viewpoint I take, I can say that's what I'm programmed to do...). Anyway, I need to think about this more to articulate what exactly I find appealing about it...

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.

near

Summary: Answer the question to the right, and see how other turkers and blog readers answered similar questions. After you answer the question, the red dots will show where people answered "yes".

This is just for fun. Stuff like this has been done before. For instance, this CrowdFlower post shows what names people give to different colors.

I had originally wanted to ask if the dot was "above" the bar, but I feared the result might look to boring, like a rectangle.

Technical tid-bits:

The url in the iframe is exactly the same url I posted on MTurk. The JavaScript detects if it is being viewed on MTurk and does two things. First, if it is being viewed in preview mode, it overlays a grey rectangle with the word "preview" to prevent people from accidentally answering the question before they accept the HIT. Second, it makes it so that answering the question submits the HIT, rather than showing the results. The utility function for submitting the HIT creates a form with the necessary elements, including a dummy result so that MTurk doesn't feel left-out -- this is necessary, since MTurk considers it an error to submit no results. Of course, the actual result is submitted to my server via ajax before submitting the HIT.

I only use one API call to MTurk, and that is to create the HIT. I don't get results, and I don't approve people. I don't get results because they have already been submitted to my server, and I don't approve people because they will automatically be approved after one hour -- this is a parameter when creating the HIT. But Greg, doesn't that mean people can cheat? Well, yes, but I find that people typically don't cheat on questions like this, because they're simple and kindof fun. Also, I wouldn't know if they did cheat. Each person is only allowed to answer the question once, so I can't even see if their results are statistically improbable.

Another tidbit is that I sometimes have unrealistic scalability fears, like "what if lots of people read this post and answer the question, endlessly increasing the size of the data structure until it takes forever for people to download?" So, I made this data structure have a maximum size: there are a finite number of points it will ask about (you can see them arranged on a grid after you answer the question), and it just records the number of yesses and noes for each location. But Greg, that doesn't really limit the size of the data structure, since the number of yesses or noes can grow infinitely. True, but first, that is a scalability issue I'm willing to sleep at night with, and second, JavaScript numbers cannot actually be infinitely large, like Python numbers can. I think JavaScript uses 64-bit floating point numbers under the hood. So at some point, the data structure would just be wrong, rather than too big...

UIST 2012

Attended UIST again. Reconnected with the user interface community, and since the conference was held near MIT, I got a chance to talk to new students in my old lab. A conversation with one of these students sparked a new research project, and hopeful collaboration.

Micro Outsourcing

Max Goldman at MIT has a tool called Collabode for giving programmers etherpad-like access to an Eclipse coding environment. We collaborated running an experiment where a programmer outsources small bits of code in real-time to a pool of oDesk workers, to see what programming this way is like. The results appear in Max's thesis, starting on page 96.