rose.blog

A very interesting and fundamental question is whether or not there exist computational problems that just can’t be solved, even in principle. It’s common for people to assume that it’s just a matter of time and smarts and we can figure everything out.

Unfortunately this probably isn’t the case. One class of problems (called NP-complete) are probably not exactly solvable, no matter how big, fast or advanced computers get. How can we know this for sure, you ask?

Here’s one way: assume a certain set of laws of physics, and then use these to derive what can and can’t be calculated, and how resource requirements (time and memory) scale with problem size.

If the universe really ran using the laws of classical physics, then whether or not NP-complete problems are intractable is the P=NP question. It is overwhelmingly likely that P does not equal NP and therefore in a classical universe, NP-complete problems of sufficiently largeness can never be solved.

Ah, but you say, our universe isn’t classical. The fundamental laws of physics are probably something more like quantum mechanics. Unfortunately, even though the verdict isn’t fully in yet, it looks like even in a quantum mechanical universe (which is probably the one we live in) NP-complete problems are STILL intractable!

So you might be asking yourself, so what. OK well NP-complete problems show up everywhere. Let’s stretch a bit and imagine that we could cure cancer if only we could solve a certain NP-complete problem. If this problem could never be solved, even in principle, by anything obeying the laws of physics, then we could NEVER cure cancer,even if we evolved for another 1,000,000 years and our brains were quantum computers the size of the milky way.

Kind of humbling, eh?

Anyway, questions like this are really fun to think about, and motivate a particular way of studying the power of quantum computers, which brings me back to what I wanted to talk about in this post.

Usually what people mean by “solving a problem” is getting the exact solution. For example, if I ask what 4*6 is, you don’t get half marks for saying it’s 23.

But what do you do if you can’t get an exact solution, but something close to exact might be OK? You settle for an approximate solution.

Let me elaborate on this by talking a little bit about the particular NP-complete problem we attack using our systems - Max Clique.

Max Clique is a graph theory problem. It’s pretty simple. Given a graph (which is a set of vertices and edges between some of these vertices), find the largest set of vertices where each vertex in the set is connected by an edge to all other members of the set. Here’s an example from here:

The biggest set of vertices with the clique property is the red set {3, 4, 5, 6}.

Note that there are a bunch of cliques with 3 vertices (like {7, 8, 9}). These cliques aren’t the biggest (ie. not exact solutions), but they are “approximate” solutions, in the sense that 3 is almost 4. All NP-complete problems have this feature, that possible answers can be ranked using some “goodness” criteria.

This is important because even if we can’t exactly solve a problem, it may be possible to find a “good enough” solution by using an algorithm designed to get a good approximation quickly. In practice, everywhere NP-complete problems show up in real-world applications, this is the approach that is taken - first we figure out what “good enough” means, and then we find an algorithm that gives this “good enough” solution as quickly as possible.

For example, for Max Clique, lots of approximation algorithms that run in polynomial time are known. Here is one (called Qualex-MS) that scales like N^3, where N is the number of vertices in the input graph. Note that even though the algorithm terminates after order (N^3) steps, it’s of course not guaranteed to find the exact answer after it terminates, although in practice it usually gives a pretty good answer.

OK so what does this have to do with QCs? Well let’s assume for a moment that for QCs NP-complete problems remain intractable (which I believe is the case). If getting exact solutions is out of the question (which again I believe is the case), what should we do to figure out how one of these machines performs?

We have to do the same thing as we do in conventional approximation algorithms - run the machines using polynomial time, and see how good the answer we get out of the QC is. We don’t expect the answer to be exact, but maybe for alot of cases it will be (although we can’t guarantee this).

This way of looking at the performance of QCs (as “hardware heuristics”) is non-standard, and only makes sense for problems where “approximate solution” is a meaningful concept. For example if we want to break codes, an approximate key doesn’t cut it - we need the exact key or nothing happens. For QCs applied to NP-complete problems the “approximate is good enough” approach makes a lot of sense, especially if we want to apply the machines to real-world situations where today approximate answers are good enough.

So physically how does a QC operate to get an approximate answer to an NP-complete problem? Imagine we’ve built an AQC, and its energy levels are as shown in the picture below (think of the x-axis as time, with the beginning of the calculation the the left, and the end of the calculation to the right). At the end of the calculation we get the exact answer if we’re in the lowest energy level. If we’re not in the lowest energy level, we get an approximate answer. The lower the energy level is we end up in, the better the approximation.

The way AQC works is that at the beginning of the calculation (s=0) we always start in the lowest energy level (the lowest blue line). At the place labeled “minimum gap” we can skip up to a wrong answer (the green line), where we get stuck until the end of the calculation. If this happens, we get an approximate answer (in this case, the second-best solution, like the 3-clique above). So if we run this AQC on a problem with energy levels like this, with 100% certainty we’ll either get the exact solution or the next-to-best solution by the time we get to s=1.

So for any problem like this, we can sweep the s parameter (think of this like time) pretty quickly and guarantee a pretty good solution.

Which leads me to:

When people say QCs speed up the solution of NP-complete problems quadratically, they mean for the special case of requiring the exact solution. This speed-up has very little to do with the real question, which is how good an approximate answer do QCs get, given some fixed amount of computational time.