Yeah but how fast is it? Part 2. August 20, 2006
Posted by Geordie in General.trackback
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.
topological quantum computing using your system is capable of some “interesting” uses, regardless of your focus on max clique. (ref Averin and Goldman, also Sneakers?
is this why you are selling services and not hardware?
looking ahead a decade, Vernam or McEliece?
fun stuff; my best regards.
We’re actually not all that interested in the potential cryptanalysis capabilities of the machine. There are many other potential apps that are better fits to the machine’s capabilities and access much larger markets. I’m not sure what will replace factoring primes in public key encryption once these machines are widespread; lots of asymmetric functions are provably secure against QCs I think.
Interesting comments..