What is a quantum computer and can they run Mario Kart?

Ever wondered what the difference is between a quantum computer and a normal computer? I’m going to assume the answer is yes, since you clicked on this article rather than one about something else.

So what is a computer, quantum or otherwise? Basically, computers are magical boxes that eat information, digest it for a bit, and then defecate some different information out.

The way they process the information depends on the program we are running. We might have a program for adding, which takes some numbers as an input, adds them, and then gives the result as an output. Or we might have a program that takes button presses as an input and gives a picture of an Italian plumber driving a go kart as an output. Either way, it’s a computer.

The atoms of mathematics

Computers usually don’t do all their computing in one go. Instead every program is built from a set of basic building blocks. These do simple little chunks of maths, which when combined can anything.

One way to break maths down into little chunks is using so-called logic gates. For these we need to write the input information in binary. Then, whether the input was text, a picture or the waving of a Wii remote, it just turns into a big string of 0s and 1s.

The logic gates are themselves tiny computers. Each of them look at no more than two bits, and spit just one out as output. Using lots of these we can read in an input as big as you like, and do any maths you like with it.

The simplest logic gate is the NOT: one bit in and one bit out, it just spits out the opposite of what you give it.

The XOR is another fun gate. It takes two bits and looks to see if there are an odd or even number of 1s. Then it spits out a 0 if there was an even number, and 1 for an odd.

Don’t worry, I won’t go through all the possible gates. I’ll just tell you about one more. The AND gate’s job is to look at two bits and see if they are both 1. If they are, the AND gate tells you so by giving you a 1. If not, it relays the news with a o.

If the only gates you have are NOTs and XORs, you’ll be very limited in what you can do. Only very simple and boring programs can be built from just these. No matter how hard you try, you’ll never get Mario Kart to run.

If you had just NOTs and ANDs, on the other hand, the world is your oyster. Everything can be built from these basic building blocks. Mario Kart. Facebook. Everything!

Computational Complicatedness

Don’t worry. I know that complicatedness isn’t a word. But complexity sounds so complex, and I’m trying to keep things simple.

Any computer program can be built from NOTs and ANDs. Sounds good, but how many if these bad boys do you need? If it’s too many, we’ll probably not bother, because would mean our computer would have to be huge, take ages to run the program, or both.

For some problems, like adding, you don’t need too many gates. To add two n-digit numbers you need around n gates. And multiplying in the way taught at school needs around n² gates. Not too bad.

Some problems are not so reasonable. If you wanted to factorize an n-digit number, for example, our best methods need an amount of gates that rises exponentially with n. The kinds of numbers that can be added in the blink of an eye would take longer than our lifetimes to factorize!

This is true whatever logic gates we use. It’s true whether we use a PC or a Mac, a supercomputer or a smartphone. All the computers we have, as different as they may be, are basically the same. Problems that require unreasonable resources for one, require unreasonable resources for all.

But a quantum computer would be different.

Boringly small computers

To start out in the wonderful world of quantum, we should start small. Let’s imagine a computer that takes just one bit as input, and gives one as output.

A computer this simple would not be able to run many programs at all. It could just give the input as the output. Or to spice things up it could do a NOT. Or it could just ignore the input and give something random as the output. But that’s pretty much it.

If the computer was allowed to do quantum stuff during the processing, it could do a little more. Quantum stuff can be in superpositions of many things at once. So we can take a quantum bit in a boring state like 0 or 1, and make it be both at the same time in an infinite number of possible ways.

Building bits that allow these quantum things to happen is not so easy. Quantum effects can be quite fragile. So any bits that manage it are rewarded by a new name. We call them qubits.

Quantum superpositions are often described as being a bit exotic and magical, like most non-technical descriptions of quantum stuff. So let’s bring it down to earth by comparing it to something normal.

How about a ball? Balls are normal. Kids play with balls. Adults watch other adults playing with balls. Everyone knows balls. A quantum bit is a bit like a ball.

In fact, it’s like this ball.

The direction of the valve is going to tell us what our qubit is doing. If the valve is pointing up, we can say that the qubit is just in the simple state 0. For down, we say that it is 1. Anything else neither 0 nor 1. It’s a superposition. Each different possible direction means a different possible type of superposition.

Now we have a lot more stuff we can do. We could do a NOT gate, just as with the normal bit. This would mean turning the ball over, and so turning 0 to 1 and 1 to 0. But we could also do half a NOT by just turning it halfway. Or any other possible fraction of a NOT.

Also, there are many ways to turn a ball over. We could follow any line of longitude we want. So for any of the infinite possible fractions of a NOT we might decide to do, there are an infinite number of ways to do it.

The simple NOT, simplest of all the logic gates, has now become something ludicrously complex. It just took a little quantum magic.

Magic is all very well and good. But us it useful for anything? Once it comes time to give an output, we have to go back to boring old 0 and 1 again.

If our qubit is still in a superposition at output time, it will be forced to choose one way or another. The closer it is to the top, the more likely it will choose 0. The closer to the bottom, the more likely 1 will be. But unless the qubit is exactly pointing up or down, there will always be some randomness to the result.

In the end, everything we can do with a single qubit quantum computer can be done with a single bit. The only resources you might need are a NOT and a random number generator. To start seeing what quantum can do, let’s get some more qubits involved.

Big and interesting computers

Let’s start with two qubits. Unfortunately, two qubits can’t be easily imagined as a ball. They can’t even be imagined as two balls if we want to do anything interesting. But we can still carry over some intuition from the single qubit case.

When building gates for multiple qubits, it turns out to be a lot nicer if they have the same number if inputs as outputs. So for a quantum XOR gate, we need to add another output.

The usual way we do this is called a controlled-NOT. We choose one input to be the control, and the other to be the target. The gate then does a NOT to the target if (and only if) the control bit is 1. This turns the target bit into the result of an XOR, which is what we want.

What if the control bit is not simply a 0 or 1, but a superposition? We could measure it before deciding whether to do the NOT or not. That would get rid of the superposition, but it wouldn’t be very quantum. So instead we find ways to do it so that a superposition of 0 and 1 on the target leads to a superposition of doing a NOT and doing nothing.

But don’t worry about that too much. For this article, we are going to focus more on another quantum possibility. Since we can do half a NOT on a quantum bit, we can also do half a controlled-NOT on two quantum bits. It just does half a not when the control is 1 instead of a while one.

Let’s call this gate a half XOR, so that we can compare it with the power of an XOR in a normal computer. Does itget us anywhere? Yes it does!

Recall that XORs on their own, or even in combination with NOTs, cannot do much. They can’t even play Mario Kart, which for me is the minimum requirement for a proper computer.

If this continues to hold true for partial XORs, it would start to seem like this quantum stuff isn’t very useful at all. But if the partial XORs have more computational power than the full ones, then quantumness would have provided a computational boost. And that would be interesting.

It turns out that using half XORs can be used to build an AND gate. I won’t provide the proof here, because you probably don’t want to read it while on your tea break. So I’ll just give you this link for when you are in the mood.

As I said before, with AND gates and NOTs we can do everything. So while XORs are rubbish, half XORs give us the computational clought pass the Mario Kart test!

Beyond Mario Kart

We’ve seen so far that making a computer quantum can turn something that doesn’t pass the Mario Kart test into something that does.

So what if we take a set of gates that can already play Mario Kart, and then quantumize that? Does it give us something beyond our wildest dreams.

The short answer is: Yes! That factorizing problem I told you about earlier, for example, would run much faster. The number of NOTs and ANDs needed to factorize an n digit number increases exponentially with n. But we would need only n⁴ half XORs and quarter NOTs. Which is much more reasonable.

Do we really need quantum?

I’ve been blathering on for a while now. So let’s take a minute to summarize.

Bits can be 0 and 1 only. Qubits can be anywhere in between too. So for any basic building block of a normal computer, we can also any fraction of them with quantum computers. That gives us more flexibility in working out how best to execute our programs. So much so that programs impossible to run in our lifetime will become possible to run in our tea break.

And Mario Kart. Always Mario Kart.

But isn’t there an easier way to do this. Why don’t we just let bits be any number between 0 and 1. Would that let us do the same thing?

In a perfect world, yes. But our world is not perfect. Errors happen, and a major reason for using the discreet values of 0 and 1 was to allow error correction. Without the discreteness, noise gets in the way and slows the computers down again.

Quantum computers avoid this by being neither completely discrete nor completely continuous. They are discrete enough to allow error correction, and continuous enough for awesome computing power. And that, more than anything else, is their secret.