rose.blog

In the last post I implied that there are types of computational problems that are intractable, in the sense that they have exponential scaling with problem size. In this post I am going to discuss one particular type of problem like this: NP-complete problems.

I’m going to focus on these because this is the type of problem that our processors are designed for.

Obvious Statement #1: The first useful QC is going to be application - specific. What, you want us to build a general purpose QC right out of the gate?

Not only are our processors designed only for NP-complete problems, they actually are much more specific than this. They are designed to solve a particular NP-complete problem called Maximum Clique. This problem is equivalent to Maximum Independent Set and Minimum Vertex Cover.

So what do we know about Maximum Clique? A couple things. Since it’s NP-complete, it’s likely that the best possible algorithms (run on conventional computers) have exponential scaling. In addition, Max Clique is known to be “really really hard”, in the sense that it is intractable to even get good approximate solutions (experts: It’s APX-complete and see this). So right now, if you want to get an exact solution to a big Maximum Clique problem you’re usually out of luck.

We also know how good our systems have to be to beat conventional hardware/software on this problem, as there is good agreement amongst experts as to how well state-of-the-art exact and approximate algorithms perform on Max Clique (see here).

OK so what we’re building, if you ignore what’s going on under the hood, can be thought of as a “black box” for solving Maximum Clique. So this is the answer to the first question I get asked all the time (see my previous post), “what would you use one for?”. Our answer is: Getting real accurate and real fast solutions to big Maximum Clique problems.

Your response to this might be, uuuhhhh OK but what good is that? Great question. This is going to be the subject of lots of my posts. We have some cool ideas and have built one app already that we’re going to release shortly, probably via this blog.

I’m going to split this post up into a couple different posts as it is getting kinda lengthy.

What I want to discuss today is some jargon you should know in order to understand what quantum computers will ultimately be good at. It’s not too hard but some of the words aren’t that common, so here’s some groundwork for some follow-on posts where I’m going to try to clarify some common misunderstandings about quantum computation.

There are two questions I always get relating to our machines and quantum computation in general: (1) “what would you use one for?” and (2) “how good will they be at that?”. These questions are difficult to answer without using a computer science concept called computational scaling. So what I’m going to do is introduce the concept for beginners (if you’re an expert go and re-read Garey and Johnson).

Here’s the idea. Let’s say you want to watch your favorite movie (Rocky III) from beginning to end. This movie is 99 minutes long. So how long does it take to watch it once? 99 minutes, sucka!

Alright now let’s say you want to watch it two times. How many minutes is this? Assuming you don’t take a break (why would you), it’s two times 99 minutes = 198 minutes. How about three times. 3 times 99 minutes = 297 minutes. How about 15 times??? 15 times 99 minutes = 1485 glorious minutes!!! Eye of the tiger baby!

Every time we watch Rocky III we add 99 minutes to the total time. A shorthand notation for this is 99*N minutes, where N is the number of times we watch. This is called linear scaling, because the total time (99*N minutes) increases linearly with N.

Linear scaling is an example of what is more generally known as polynomial scaling. A problem scales polynomially if the difficulty of solving it increases like a polynomial of the problem size. In if the problem size is N, this means things like N^2, N^3, N^5, etc. as long as it’s N to the power of a fixed number, that’s polynomial. Generally polynomial scaling is a good thing, and the lower the power, the better, ie. N is better than N^2 etc.

OK now let’s say instead you are forced to watch the worst movie ever made (Secrets and Lies) at 142 horrible minutes. And let’s say that the time it takes you to recover from watching it doubles every time you watch it, starting at 1 week recovery time for watching it once. So one horrible viewing takes 1 week to recover from. If we are forced to watch it twice, we need 2*1 week = 2 weeks to recover. Three times, we need 2*2*1 week = 4 weeks to recover. The total number of weeks it takes to recover is [2*2*...*2 (multiply 2 by itself N-1 times) ] * 1 week if we’re forced to watch it N times. Writing this out in math shorthand, this is 2^(N-1) weeks. This is called exponential scaling (because the N is in the exponent).

Exponential scaling means something gets really big (or really small) really fast. If I make you watch Secrets and Lies 50 times in a row (taking a total of 142*50=7,100 minutes or about 120 hours), according to our formula above, it would take you 2^49 weeks to recover! This is about 10 trillion years!!!

OK so what does this have to do with anything. Let’s say we were to go back to Rocky III, and watch it in fast-forward, so that it only takes 10 minutes to watch. How much time does it take to watch it N times? 10*N minutes! Notice that it’s still linear scaling, just the number out in front has changed. Let’s say we watch it on super ultra fast forward, so that it only takes 1 microsecond to watch the whole movie. How long does it take to watch it N times? N microseconds! Still linear scaling.

Back to Secrets and Lies. Let’s say you’re allowed to wear earplugs while you watch, so that the time to recover from the first viewing is only one day instead of one week, but every time you watch the recovery time still doubles. How long does it take to recover from 50 back to back viewings? 2^49 days, or about 1.5 trillion years. Still exponential scaling, still a long time! What if we’re allowed to gouge out our eyes and wear earplugs? Let’s say it only takes 1 microsecond to recover from one viewing. How long does it take to recover from 50 viewings? 2^49 microseconds, or about 18 years! Still exponential, and still a really long time.

Computational problems where the best known algorithms scale exponentially are called intractable by computer scientists. What this means is that for big problems of this type, the problem can’t be solved no matter how “fast” or “parallel” a conventional computer is.

This is actually a very cool concept - that there exist computational problems that might not be solvable, even if we could use all of the computational resources of the universe.