Quantum Computer Demoed, Plays Sudoku 309
prostoalex writes "Canadian company D-Wave Systems is getting some technology press buzz after successfully demonstrating their quantum computer (discussed here earlier) that the company plans to rent out. Scientific American has a more technical description of how the quantum computer works, as well as possible areas of application: 'The quantum computer was given three problems to solve: searching for molecular structures that match a target molecule, creating a complicated seating plan, and filling in Sudoku puzzles.' Another attendee provides some videos from the demo." Anyone want to guess how long before "qubit" gets compressed to "quit" (as "bigit" became "bit" in the last century)?
BIGIT?? (Score:5, Informative)
I think "qubit" is here to stay, though.
Re:For real? (Score:5, Informative)
Re:Traveling Salesman (Score:4, Informative)
Common misconceptions (Score:5, Informative)
Re:Traveling Salesman (Score:4, Informative)
BTW, of course a problem instance must fit in memory--but the idea is that we should be able to build a 1000 qubit computer, while going through 2^1000 possibilities to brute-force a problem of size 1000 is intractable. But with our knowledge now, even if you fit a traveling salesman instance, the quantum computer wouldn't know what to do with it.
As GP pointed out, we do have excellent approximations for TSP and most practical problems--the issue is mathematical--that we don't have algorithms that can guarantee the absolute best solution. The one place quantum computers are potentially useful is crypto--nearly all of which revolves around the hardness of factoring and discrete logs (which I think is a very strange coincidence, if it is one).
"Bigit" never existed. (Score:4, Informative)
http://en.wikipedia.org/wiki/Binary_digit [wikipedia.org]
More info... (Score:5, Informative)
High level explanation [youtube.com]
Protein matching [youtube.com]
Sudoku [youtube.com]
Also, here's some slightly older talk at Stanford with a higher-level audience [stanford.edu]
Additionally, it's not exactly a "true quantum computer"(tm) - but it utilizes quantum mechanics as a quantum computer would. So it quacks like a duck, etc.
Ask the companies founder - here's his blog: (Score:5, Informative)
Re:Traveling Salesman (Score:5, Informative)
The beauty is, if you solve any NPC problem you solve them all, by definition. So, Mr. Smarty Pants, if your Sudoku solver is good enough to solve any grid in polynomial time, please show the rest of us, as you've just cracked every encryption scheme invented to date.
Yeah, I didn't think so.
Re:Traveling Salesman (Score:1, Informative)
We already have a solution to the Travelling Salesman Problem. Do you really think NP-complete problems are so hard and mystical that we can't currently run computers to solve them? Yes, the best (100% accurate) solutions we have currently increase the execution time exponentially with the problem size. So what?
NP-complete != impossible. NP-complete != slow. NP-complete = slow for big problems. A few years ago I was playing around with NP-completeness in my spare time. Using GNU Guile [gnu.org] (hint: this was not a blazingly fast implementation), I was able to solve a typical n=1000 subset sum [wikipedia.org] instance in under a minute on commodity hardware.
With a clever heuristic or two, and a clever programmer, and a clever optimizing compiler, I wouldn't be surprised if USPS could solve Travelling Salesman Problems where the number of nodes is on the order of magnitude of 10000, without overly exorbitant hardware costs. Maybe I'm naive, but I don't think USPS has more than 10000 stops on most of its shipping routes.
If USPS wanted to use the Travelling Salesman Problem, they would be using it already. Using a quantum computer would do nothing for them but add headaches and cost. NP-complete problems are only hard when you're looking at big data sets, and I just don't think USPS making shipping routes would fall into that category.
Re:Traveling Salesman (Score:2, Informative)
There is already a good solution (Score:3, Informative)
With a few heuristics, the worst case becomes very rare, and it usually finds something closer to the best solution.
So if we solve the NP travelling salesman in a perfect way, at most we'll get paths that are half the length.
That could be an improvement, but not a revolution.