Quantum computing and Sudoko, part III
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!
Posted by Jim Ledbetter 3:30 PM 3 Comments comment | Add a Comment

Who cares about Sudoku? No offense Browser (I enjoy your blog), but maybe you should focus more on the practical applications of a quantum computer rather than 3 posts of Sudoku. What advantages do quantum computers have over traditional computers? Is it the beginning of a new wave of technologies? Will we finally calculate the meaning of life or just have better Sudoku and Chess tournaments?
Posted By Peter Hooper, Greensboro, NC : 9:29 AM  

"Who cares about Sudoku?" is a very valid question, especially given the hype that often surrounds the technology industry. The answer is: every theoretical computer scientist, and ultimately, you and me. Sudoku grids larger than 9 X 9 fall into the NP-complete class of computer problems. As the IEEE article cited above says, "an efficient algorithm for any NP-complete problem . . . automatically provides an efficient algorithm for solving all." Oversized Sudoku puzzles may not be a pressing problem for humanity, but these other NP-complete problems, or their applications (including gene sequencing, complex mass transit scheduling, optimization of manufacturing processes, etc.) are. Computationally solve generalized Sudoku, and you solve these, too. All this from a puzzle slightly bigger than one you'd find in a newspaper - who would have thought it?
Posted By Noah Green, New York, NY : 1:36 PM  

Okay. Read this article and then tell me the problem is really about Sodoku.
In as much as 10x10 and greater sized Sodoku puzzles are NP-Complete, then yes, it's about Sodoku. Beyond that,
it's about quantum vs. binary computing.

Posted By Jesse Perry, Richardson, Texas : 2:47 PM  

To send a letter to the editor about The Browser, click hereTop of page

Got a news tip? Send it to The Browser