Q&A: D-Wave's Geordie Rose

Continued from page 2

JP: Are you really claiming that the Orion can solve NP-complete problems? [NP-complete problems, of which the most famous is the traveling salesman problem, are the hardest problems in complexity theory for which a solution might be efficiently verified. Very common in real life, they are hard to solve because their solution seems to require considering every permutation of a set of variables, which takes time that increases exponentially with the number of variables. Computer scientists doubt that NP-complete problems can be solved in any reasonable amount of time. Rose has attracted controversy by claiming that the Orion could create approximate solutions that are good enough for business.]

GR: It solves them in the sense that it provides approximate solutions to things that are good enough in the sense that they meet the requirements of the user. These classes of problems are ubiquitous in business. It's suspected that no machine, regardless of the kind, can efficiently and exactly solve these types of problems, at least in the worst case. But that's an overly restrictive definition of what "solving" means. Generally, if a business has one of these problems embedded in its daily operations, it uses what is called a heuristic to solve it, which is a set of rules of thumb that gives good approximate solutions quickly. Our machine has as its intended purpose competition with those heuristics. We're not claiming that we can exactly, efficiently solve worst-case problems, no--but we are claiming that this thing will be competitive and eventually surpass all conventional approaches at solving these sets of problems.

JP: I am not a mathematician, but I play one on TV. What about the PCP theorem that says that an approximate solution in these cases is as difficult as the best solution?

GR: It depends on what you mean by "approximate."

JP: Well, tell me what you mean by "approximate." Is Geordie Rose using "approximate" in some special sense that no one else uses?

GR: "Approximate" means something specific in computer science. It's not the way the term is used conventionally in business. So, say that you have yet to pick a route through a bunch of cities--

JP: The traveling salesman problem?

GR: Yes, for example. Any route is a solution. Any route is also an approximate solution. How good the approximate solution is is somehow the difference between the one that you've got and the best possible one. So, as the solutions get better and better, they get less and less approximate. So, what computer scientists tend to mean by "approximate" in these cases is something very specific about how great the approximation is, and they tend to mean something that is very close to exact.

JP: You mean that when you use "approximate" in this sense, you are using the word as businesspeople would use it, and not as computer scientists use it?

GR: It's the same sense that people use when they solve these problems today. You need a solution; you'd prefer one that is the best possible solution with the resources that you have available to you, and that is by any definition an approximation solution. You'd like it to be better, but those things are not available to you because of the nature of the problem. So this particular machine that we've built is designed to compete with the machines that give those types of solutions.