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....
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!
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?
"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?
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.
CNNMoney.com Comment Policy: CNNMoney.com encourages you to add a comment to this discussion. You may not post any unlawful, threatening, libelous, defamatory, obscene, pornographic or other material that would violate the law. Please note that CNNMoney.com makes reasonable efforts to review all comments prior to posting and CNNMoney.com may edit comments for clarity or to keep out questionable or off-topic material. All comments should be relevant to the post and remain respectful of other authors and commenters. By submitting your comment, you hereby give CNNMoney.com the right, but not the obligation, to post, air, edit, exhibit, telecast, cablecast, webcast, re-use, publish, reproduce, use, license, print, distribute or otherwise use your comment(s) and accompanying personal identifying information via all forms of media now known or hereafter devised, worldwide, in perpetuity. CNNMoney.com Privacy Statement.