The fourth annual π/ホワイト day animaths appreciation post

Qualia 8

Let us celebrate this day with Nadeko.

Okay, now let’s figure out what the hell Alice is trying to claim. Alice can solve equations by turning them into pictures and solve them instinctively like that. What implications does this have?

First, we probably want to talk about what the P/NP problem is. In computational complexity, we talk about the complexity of problems and we measure this as the amount of resources we need to solve a problem. The two most common measures are for time and space. That is, roughly the amount of time it takes to solve a problem or the amount of space (so, like memory) that’s required to solve a problem. This is expressed as a function of the size of the input.

Formally, all of this stuff is defined in terms of Turing machines, but we don’t need that level of specificity. Intuitively, we can think of P as the class of problems which we can solve in a reasonable amount of time (or “efficiently”) and NP as the class of problems for which we can verify the correctness of a given solution in a reasonable amount of time. By reasonable, we mean that the amount of time it takes scales reasonably depending on the size of the input or problem we want to solve.

The P/NP problem asks whether P is equal to NP. If you think about it for a bit, it seems kind of intuitive that those two classes shouldn’t be equal. It’s a lot easier to figure out whether an answer to a problem is correct than it is to find a correct answer. And most computer scientists also agree that that’s probably the case. The hard part is actually proving it, which no one has been able to do since 1971, when U of T’s Stephen Cook first formulated the problem.

The classical NP-complete problem is the satisfiability problem. If I have a boolean formula, is there an assignment of true/false values that makes the formula evaluate to true? Testing this is easy: if you give me an assignment that you claim works, I can check it in the amount of time it takes to look at each variable. Trying to come up with an assignment is a lot trickier. The easiest thing to do is try trial and error, but that could take an exponential amount of time. Of course, there are a lot of fancy tricks we’ve come up with for this problem, but we still have no way of solving this problem in a way that we can say is theoretically efficient (whether it’s the case for practical uses is a different matter).

What’s baffling about P/NP is that the idea is rather simple to prove or disprove. We have these notions of hardness and completeness which allow us to reduce problems to other problems. In particular, the class of NP-complete problems are those problems which are called NP-hard and contained in the class NP. These problems have the property of being able to reduce to any other NP-complete problem.

A reduction basically says that two problems are about as computationally hard as each other. The idea is that if I have some problem I want to solve but I don’t know how to do it, I can transform it (with a reasonable amount of time) into some other problem that I hypothetically do know how to solve. The reasoning is that if I can do that, then I know that the problem I wanted to solve takes about as much resources to solve as the problem I already know how to solve. And it’s pretty remarkable, then, that every NP-complete problem has this property of being able to reduce to any other one.

So the way to prove that P=NP is to figure out a way to solve any NP-complete problem in polynomial time. Since every NP-complete problem reduces to every other one, you just have to choose your favourite (read: easiest) NP-complete problem out of the several thousand that we know of and figure out an efficient algorithm for it. Because of the reducibility property, if you solve one efficiently, you’ve basically solved them all efficiently. This means that all problems in NP can be solved efficiently and it turns out P=NP. And yet, no one has been able to come up with an efficient algorithm for any NP-complete problems.

On the other hand, while at this point it’s pretty obvious that P≠NP, we have no idea how to prove it. The field of computational complexity and all the tools that we’ve developed over the last few decades are all interesting and useful, but they were all in an attempt to show that P≠NP and so far, nothing we’ve thrown at it has stuck. In fact, we’ve ended up creating a lot more questions that seem to have interesting structures and intuitive answers but we still have no way of proving a lot of these conjectures.

Of course, in the last decade or two, there’s been a lot of focus on quantum computing and with the rise of quantum computing, quantum complexity theory. It’s commonly believed that quantum computing gives us exponential speedup and allows us to solve NP-complete problems in polynomial time.

Well, it doesn’t.

The idea is that since you have a bunch of states in superposition, you also have all possible outcomes stored in those states. Unfortunately, it doesn’t work like that and there are a bunch of complications that arise in trying to extract outcomes of computations stored in qubits that render this whole point moot.

There’s nothing inherent in quantum computing that brings us closer to actually resolving questions that we have about the complexity hierarchy we’ve defined. In fact, quantum computations can be simulated on classical computers in exponential time, so it’s not like there’s nothing we don’t already know about computation, we can just certain kinds of computations faster.

And just like the other tools we’ve developed in computational complexity to try and resolve this question, quantum computing throws another wrench into the problem by introducing quantum analogues of classical complexity classes. Some of these, like QIP, the class of problems solvable by quantum interactive protocols, turn out to have no additional power (it was proved in 2010 by Jain, Ji, Upadhyay, and Watrous that QIP = IP). And some, like BQP, the class of problems solvable in bounded-error polynomial time, have the same problem where we’re not entirely sure how it relates to the other classes.

So knowing all of this, what does Alice’s claim mean exactly? Unsurprisingly, it doesn’t mean anything. If Alice can solve equations intuitively by drawing pictures, then she can probably already solve PSPACE-complete problems (since there are equation problems which are known to be in PSPACE), which means that it doesn’t even matter whether or not she has access to a quantum computer, since she can already solve problems harder than the ones in the quantum analogues of P and NP.

The lesson here is that little girls would not necessarily make very good mathematicians even if they can compute computationally intractable problems (this is basically what Gödel’s incompleteness theorems say too).

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.

Fun with computer science in Kaiba


I’d been rewatching Kaiba with a bunch of people a while ago. Kaiba’s a great show to watch if you want to talk about things, especially if you like dealing with the sorts of moral and ethical issues that come about in a world that’s so starkly different from ours. The obvious things to talk about revolve around identity and existence. Being the computer scientist and the guy who likes to make laboured analogies to things I like, I began to think about memories and cognition from a CS point of view.

Kaiba’s already done a lot of the “what if” in exploring the idea of memories that are as easy to work with as data on today’s computers. There was an observation in one of the episodes that it seemed like one of the characters’ had too many memories and seemed to be unable to create anymore since there was no more room to store them. The obvious answer to me seemed to be just to throw in another disk or something. Of course, another thing we can do, since we can manipulate memories like data, is to selectively choose less important things to throw onto that extra “disk”. In a way, that’s kind of like what we do already, except instead of having a machine suck out our memories, we do things like write them down or take pictures of them. And in the case of photos, it kind of is like having a machine suck a memory out. In either case, that relieves us of the burden of having to keep it in our brain.

In light of this, it’s kind of a good thing that our brain cells do decay eventually and we do forget things. Otherwise, without a way to manipulate our memories like they do in Kaiba, we’d actually run out of room. Usually, we like to think of data or information as this ethereal sort of thing, but realistically, it’s constrained by the physical world. Those bits have to be written down somewhere, whether it’s on a magnetic platter on a hard disk or in a cell in our brains or in a photon in a quantum computer or in a weird capsule like it is in Kaiba.

Recently, someone linked to something about solving NP-complete problems in polynomial time by taking advantage of the many-worlds interpretation of quantum mechanics. This lead me to some of Scott Aaronson’s papers. Scott Aaronson is a complexity theorist who does quantum stuff at MIT and writes a neat blog. I read through the lecture notes for this course he did while he was a postdoc at Waterloo called Quantum Computing Since Democritus and a paper called Why Philosophers Should Care About Computational Complexity. These two things attempt to tie computational complexity and quantum computing with philosophy (duh). The Democritus stuff is pretty accessible if you have a bit of mathematical background and it introduces concepts like computability, complexity, and quantum computation if you’re not familiar with them. The complexity for philosophers paper assumes you’ve done some computational complexity.

So in Kaiba, we can send our minds around and stick them in other bodies or even in machines. But if we can stick them in machines, what’s running it? We’re not sure, but if we can build machines to interface with our minds or run those processes, then we’ve got a computer that can simulate our brains. This is where computational complexity comes into play.

Aaronson notes that a lot of people who think they consider AI a metaphysical impossibility really haven’t thought it through that far and are only considering the practical impossibility. For instance, what can we extract from the fact that Kaiba has computers that can simulate brains? One thing is that simulating a brain can be done efficiently, presumably in polynomial time.

See, in computer science, a lot of things (like simulating a brain) are possible if you just hardcode everything into a lookup table. Luckily, like I mentioned before, there’s a finite amount of stuff we can hold in our heads. So yeah, you could simulate a brain like that and it’ll work because the table’s finite, but you’d probably run out of atoms in the universe to hold all of that data and the possible choices that would branch out that the computer could make as it went along. Of course, that’s only a practical concern.

Which is why Kaiba’s brain simulating must be efficient, otherwise it wouldn’t be physically feasible. This would seem to imply that simulating a brain didn’t turn out to be that hard. Of course, this means that we’ve got a way to formally describe and model the way brains work too. Anyhow, this is all to ask, if we did have a way of doing this, would a computer simulating a person be that person? And then, we can go a bit further and ask whether a person that we’ve fabricated the data for and is simulated by the computer also constitutes a person.

It’s kind of the same question as whether clones would be people, isn’t it? Except instead of creating perfect copies of the entire person, we can just create perfect copies of the person’s memories and throw it into a computer. Of course, this leads us to the implication that brains are deterministic. Otherwise, this entire memory transfer thing wouldn’t work. You wouldn’t be able to designate a person as their memories if how they behaved changed with the brain that they occupied.

We do have some indication that the brains seem to function differently based on the body that they’re controlling. When Kaiba is in Chroniko’s body and meets the girl who’s in the huge guy’s body, they mention something about getting used to the body. It does make sense that biological processes are governed by the brain and isn’t tied to the person’s identity, but then we see how the body interacts with the person when they start to have ~feelings~ for each other. Of course we can consider the body as another part of the input into the brain and then that discrepancy goes away.

So the thing is that in Kaiba, we’ve got a way of creating something that’s literally indistinguishable from a person. Well, okay, we did start with the premise that it’s possible to simulate a person’s brain, which is kind of a stretch in the real world. But now we ask, what properties would human consciousness need to have in order for a computer to be unable to efficiently simulate it?

It turns out there are some possible ways for this to happen. For instance, if we could solve NP-complete problems or do quantum computations, then a classical computer wouldn’t be able to simulate our brains. Of course, that’s assuming P≠NP, so if it turns out that P=NP, then we might have to rethink this condition, and a quantum computer will be able to do quantum computations, so if we ever built one of those, then that also reduces our options. And of course, the bigger problem is that it assumes we can solve NP-complete problems or do quantum computations in our head.

On a slight tangent, this idea of quantum computations in our head leads to the question of what happens if our brains stored quantum information. That would make it very difficult to make perfect copies of our memories because of the no-cloning theorem in quantum information. The theorem is exactly what it sounds like: it’s impossible to make a perfect copy of an unknown quantum state. What this would imply is that if you tried to make a copy of yourself, it would not be 100% identical to you. Admittedly, it’s pretty unlikely that our brains can store any quantum information.

To close, something that’s slightly related, since it happened around the same time as I was watching, was a department seminar I went to where the guy was talking about neuroscience and brain imaging and tying it into graph theory. Essentially, what he did was he took a bunch of MRI scans of someone’s brain and created some graphs on them somehow. He then ran a bunch of algorithms on the graphs for a bunch of metrics to see if graph theory were any use for neuroscience purposes.

What he found was that the brain activity that could be seen from the scans translated to changes on the graph. Those graph transformations acted on the graphs in a predictable way from the metrics. He raised the possibility of linking thought or computations in the brain with graph transformations. The nice thing about graphs is that, even though there are plenty of problems that are hard, we still know a lot about them and we’ve got a ton of graph algorithms already.

Who knows, maybe we’re further along in figuring this brain thing out than we might think.