Kenji the quantum computer, Part 2

He will use this knowledge in less than 24 hours.

So back when I was moving in at the start of the school year, I decided to try out my BD player on my hot new Dell monitor. Since I didn’t want to take out my Kara no Kyoukai BDs from their box, I opted to crack open the cheap flimsy Summer Wars case and throw in the disc. I hadn’t actually tried playing it yet anyway. I opted to skip the OZ introduction and go straight to the opening. First of all, I was disappointed that Funimation set the credits in goddamn Arial. Seriously, what? I find it difficult to believe they didn’t have Helvetica already from one of countless projects they could’ve used it on already.

More importantly, Funimation translated the chapter title of the book that Kenji was reading on the train. It turns out he was reading about Shor’s Algorithm. Shor’s Algorithm is the quantum algorithm that can factor integers in polynomial time. I alluded to it when I talked about Summer Wars and cryptography a while back and now’s as good a time as ever to get into it, since, you know, this means Kenji really is a quantum computer and all.

In quantum computing, instead of dealing with bits that are 1s and 0s, we deal with quantum bits, or qubits, that are denoted $|1\rangle$ and $|0\rangle$. These are really just quantum states. Quantum states have interesting properties, the most famous of which is being in superposition. Essentially, what this means is that we can have qubits that are in a state where it represents 1 and 0 simultaneously.

This turns out to be a very neat property to have. If we’ve got $n$ qubits, then we’ve got like $2^n$ inputs simultaneously. That’s great, right? We can compute things exponentially fast now! Well, it turns out it isn’t that simple.

Suppose that we do end up running an algorithm or something on our $2^n$ states. What happens when we want an answer? Well, we measure the state. The problem with that is that on measuring a quantum state, you won’t get all $2^n$ results. You’ll only get one of those results with a certain probability. What’s more is that once you measure a quantum state, you’re stuck with whatever it gave you and you can’t go back and check for another result.

That is obviously no good, because we want not just any answer, but, you know, the right answer. So it looks like approaching our problem from the naive interpretation doesn’t seem to work. And in fact, that immediately tells us that quantum computers aren’t a magic bullet that can help us solve SAT in a reasonable amount of time.

What we can do is manipulate our resultant quantum state so that the actual correct result we want is the one with very, very high probability and reduce the probability of getting any of the other results to near-zero. Of course, the problem is that we don’t know which result is the correct one to begin with. It’s actually this exact hitch that prevents us from efficiently solving general NP-complete problems.

Luckily, if we want to factor some numbers, we can take advantage of this. We can reduce the problem of factoring any old number into prime factors to the problem of order finding, which I’d mentioned before. For an integer $N$, there’s another integer $m$ such that $k^m=1\bmod N$ and we call $m$ the order of $k$ in the integers modulo $N$.

So suppose we have $k\bmod N$ with order $m$ and we decide to keep on taking powers of it, like $k\bmod N,k^2\bmod N, k^3\bmod N$ and so on. Eventually, we’ll get up to $k^m\bmod N$, at which point, that’s just $1$ and we start our cycle over again. The thing to note here is that this sequence is finite and periodic, which narrows down what we have to search through.

So what do we do? We create a quantum state for our period that’s in a superposition over all the powers of $k$ in $\bmod N$. We don’t know what our period is (that’s what we’re trying to find), so we just choose a large enough one that our order will be in the period. Now, in order to find this order, we do some magic with a Quantum Fourier Transform.


So I mentioned at the beginning that when we look at a quantum state in superposition, we can think of it as returning one of the possible states with a certain amount of probability. How the probabilities for these quantum states work is actually more complicated and it’s from this that we can massage an answer out of our magic quantum algorithm.

Quantum states have something called amplitudes, which are kind of like probabilities, except that amplitudes can be basically any complex number as long as all of the amplitudes $a_i$ for a quantum state satisfy $\sum|a_i|^2=1$. If we’re just measuring a quantum state, this really doesn’t change anything, we just get state $|i\rangle$ back with probability $|a_i|^2$. But when we’re manipulating quantum states, there’s more to the amplitudes to consider.

If we think about amplitudes in terms of waves, we can see that we can cancel waves out. For instance, the states $\alpha|1\rangle$ and $-\alpha|1\rangle$ have the same probability if we were to measure them (since $|\alpha|^2=|-\alpha|^2$), but if we put them together and add them, they’d cancel each other out. What’s more is that since amplitudes are complex numbers, so we can think of them as having a direction (like a vector on the complex plane) and we end up with weird stuff like having things partially cancel out.

So just like a regular Fourier transform extracts some information about frequencies from a sequence, we can use the Quantum Fourier Transform to extract some information about all of this amplitude stuff that we can’t see just by measuring the state. And this is exactly how we can manipulate our state so that it increases the probability of the answer we want when we go to measure it and depress the probabilities of all the other answers.

Now after rambling about amplitudes and Fourier transforms and orders, we should probably step back and see what we’ve done in perspective. What we have is a way to find the order $m$ of an element $k \bmod N$. Well, actually, we don’t even have that quite yet. What we get out of all of that quantum stuff is just some information about $m$ that we have to manipulate further, except we just do that with plain old number theory instead of quantum computation. But, what we’ve kind of stumbled through is kind of a vague description of Shor’s algorithm.

Like I mentioned in the first Summer Wars post, this is the only way we know of so far that lets us factor large numbers (especially the ones that are used in cryptography) within a feasible amount of time. Again, Kenji (or at least his brain) is basically a quantum computer. Coincidentally, I played around a bit with what the implications could be if our brains were quantum computers in an earlier post on Kaiba.

But even if Kenji isn’t a quantum computer, he’s goddamn smart for a high school student. The theory behind the computing part of quantum computing is really just a ton of linear algebra, so an understanding of quantum mechanics isn’t really necessary (which is great, because I don’t know any of that crap). The quantum computing course that I took in my undergrad only had second year linear algebra as a formal prerequisite, but that was mainly to allow students from different departments to take it and also implies that you’ve got first and second year math down at the very least.