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)?
Traveling Salesman (Score:5, Interesting)
I imagine the USPS and other shipping organizations will be the first to buy commercial versions of these.
Sudoku: The np-easy version of Traveling Salesman (Score:2, Interesting)
I've built a Sudoku program to help me reduce the boring parts (filling in the only posssible option if it is known). I didn't know that it would solve all boards except for the hardest ones.
Then I've added another filter that still was not DFS and it solved all boards to this day except 2. One of which had 2 solutions and the second could be solved with a DFS of depth 1.
Took all the fun out of the game.
Some timing statistics: less than 1 second with Javascript on Firefox. About 30 seconds with Internet Explorer.
Curious (Score:5, Interesting)
For real? (Score:3, Interesting)
Re:Traveling Salesman (Score:5, Interesting)
Travelling Salesman is NP-hard, which means (I think) that if you find a polynomial time algorithm for it, any problem in NP can be done in polynomial time (hence P=NP). But I believe that even this quantum computer can't calculate TSP in polynomial time, except for instances small enough to fit inside the 16-qubit memory. Can anyone comment on this? By contrast, a conventional computer can always calculate TSP in the same time complexity (exponential time) no matter how large the input - you just have to hook up enough memory.
Re:Or rather... (Score:3, Interesting)
Anyone want to guess how long before hillbillies start asking "How many quberts you got in that there system?"
I think qubert rolls of the tongue easier than qubit. Let's push qubert as the new way of saying qubit!
breaking cryptopgraphy with Quantum computing (Score:4, Interesting)
If the NSA wanted to build a custom quantum computer to break traditional cryptographic systems what are the chances that's it's already been done (and in use)?
Mass producing a commercially viable quantum computer (or many sci-fi like technologies) is usually pretty hard, but producing one or two special purpose built systems are MUCH easier.
Re:Sudoku: The np-easy version of Traveling Salesm (Score:3, Interesting)
But of course they have solutions. Otherwise, you couldn't start with an empty 9x9 grid and create a Sudoku in it in the first place.
In any case, solving the things is a much more trivial problem than creating valid ones or arbitrary difficulty. But the fact that seemingly hundreds of different publishers are out there creating books without any quantum computers at all is probably a good hint that nothing to do with Sudoku is a particularly impressive computational task to use to show how great your new quantum computer is.
Re:Common misconceptions (Score:3, Interesting)
Re:Traveling Salesman (Score:2, Interesting)
Sure they do. School systems do this for bus routes. Some counties used to pay good money for that. For one school system I worked with it saved nearly 1 million in gasoline for the year and that school system wasn't that large and back then gasoline wasn't that expensive like it is now. The next year I suggested changing school start times to optimize it even further. They saved an additional 3 million that year and eliminated a number of busses entirely. This is just one example.
BTW, even though they don't travel in straight lines in practice, that doesn't matter. Simply consider the mileage as a line. After all they are confined to the road unless they have off-road capabilities.
Even the average Joe often does the TSP, probably without realizing it. When you have a number of places to go, do you just go to whichever first or do you plan your journey to optimize your time? Almost everyone I know figures this out before they leave. Sometimes if there is a group of us, I have even observed discussions on which routes and order would be best.
Re:Traveling Salesman (Score:5, Interesting)
Nobody is going to use Travelling Salesman in the real world to plan journeys. You can already quickly run an algorithm which will get you a journey plan that's maybe 99% as good as the optimum.
Actually, I think there is a theorem that finding an algorithm that efficiently produces highly-accurate approximate solutions to arbitrary problems in NP-hard is about as hard solving NP-complete problems exactly.
All this aside, it's worth noting that D-Wave is only claiming to provide a square-root speed-up for NP-complete problems, and there is some doubt as to whether they can even deliver that, as they scale up to larger numbers of quantum computers. While it's technically possible that P=NP, most people believe P!=NP, and it seems almost as likely that BQP [caltech.edu] != NP (BQP is the class of problems efficiently solvable with a quantum computer).
For an excellent discussion of what D-Wave has done and just how skeptical you should be, visit Scott Aaronson's blog [scottaaronson.com]. (No, I am not Scott Aaronson, but I do know him and can vouch for him being an extremely smart guy. I am also not the Quantum Pontiff, aka Dave Bacon.)