An interview with Geordie Rose, founder and Chief Technology Officer of D-Wave, has clarified some issues. First: The Sudoku demonstration was a last-minute addition. A D-Wave employee who is a Sudoku fan wrote the application "a couple of days before the event, and we thought, we'll show that, too," Rose told The Browser. Second, the Sudoku demonstration was NOT intended to show the best abilities of quantum computing. "The point was not to demonstrate superior performance [to conventional computing]," Rose said. "It was to show that it was possible at all."

In other words, this was a proof-of-concept event for quantum computing in general (you can read more about Rose and D-Wave in this Business 2.0 article from 2004). Rose says he anticipates that his system will "become better than conventional approaches" by the end of 2008.

So what might a genuine quantum computing approach to Sudoku look like? Here's how Noah Green, a programmer who is a VP with Lehman Brothers Fixed Income Research, describes the problem:

It's easy to write a [Sudoku] solver and most computers can do it in under a second. However, if you go out past 9 X 9 [squares in a Sudoku grid], believe it or not you enter into a whole different problem space. Why this is and what this implies is the subject of a huge research area of theoretical computer science. Basically the generalized (i.e. > 9x9) Sudoku problem is "NP complete," which means it's a problem that will take forever to solve computationally. Note the word "computationally" - this means a person can conceivably still solve it unsystematically in a much shorter time....

Till now, you could throw all the hardware you want at this stuff and still reach the same frustrating conclusions. What was true in the 1940s and 50s, when Turing did his work, is still true today. That's what is so elegant about theoretical computer science - it's about math, not transient things like hardware. However, hardware could make a big difference if the hardware was something that shifted us away from the Turing mathematical model and/or the von Neumann architectural model. People often tout quantum computing as being that hardware. Of course, we haven't really had quantum computers before.

Green also recommends this article for those wanting to know more about the science of Sudoku.

All told, I'd say D-Wave's Sudoku demonstration created a classic public relations quandary: they succeeded in getting people's attention, but at the same time blurred slightly what exactly makes their approach distinctive--most of the coverage treated the Sudoku puzzle-solving as a gee-whiz achievement.

But at least we're now clear on the benchmark for '08--a 10 x 10 Sudoku grid solution or bust!