Slashdot Mirror

← Back to Stories (view on slashdot.org)

Quantum Computer Demoed, Plays Sudoku

Posted by kdawson on from the more-qubits dept.

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)?

11 of 309 comments (clear)

  1. Traveling Salesman by Short+Circuit · · Score: 5, Interesting

    Does this mean we'll be able to solve the Traveling Salesman problem soon? That would lead to a revolution in efficiency of everything from travel to mass transit to shipping.

    I imagine the USPS and other shipping organizations will be the first to buy commercial versions of these.

    --
    tasks(723) drafts(105) languages(484) examples(29106)
    1. Re:Traveling Salesman by Ed+Avis · · Score: 4, 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. Besides, real things (even salesmen) don't just have to travel in straight lines between points in space. There are other factors like lunch breaks and the location of good restaurants, which the problem doesn't account for.

      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.

      --
      -- Ed Avis ed@membled.com
    2. Re:Traveling Salesman by ebvwfbw · · Score: 2, Interesting
      Nobody is going to use Travelling Salesman in the real world to plan journeys.

      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.

    3. Re:Traveling Salesman by tbo · · Score: 4, Interesting

      Disclaimer: I am a physicist who works on quantum computing and also has a computer science background

      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 != 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. (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.)

  2. Sudoku: The np-easy version of Traveling Salesman by Anonymous Coward · · Score: 2, Interesting

    Actually you don't need the DFS.

    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.

  3. Curious by vlad_petric · · Score: 4, Interesting

    I'm actually curious - for how long do the 16 qubits stay coherent? You can only do quantum computations while the qubits remain coherent. Furthermore, IIRC coherence times where (at best) in the range of a few microseconds.

    --

    The Raven

  4. For real? by DurendalMac · · Score: 2, Interesting

    Is this a true quantum computer, or one that simply uses certain quantum properties? Scientists weren't predicting this for another 20-30 years. Wouldn't a 1024 qubit computer be far faster than any cluser on earth? And if I'm not mistaken, a 16 qubit computer would be faster than any single computer. I'd like to see some speed comparisons for parallel tasks.

  5. Re:Or rather... by kabocox · · Score: 2, Interesting

    Anyone want to guess how long before "qubit" gets compressed to "quit" (as "bigit" became "bit" in the last century)?
    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!

  6. breaking cryptopgraphy with Quantum computing by Danathar · · Score: 3, Interesting

    I wonder....

    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.

  7. Re:Sudoku: The np-easy version of Traveling Salesm by geoffspear · · Score: 2, Interesting

    They're not Sudoku.

    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.

    --
    Don't blame me; I'm never given mod points.
  8. Re:Common misconceptions by khallow · · Score: 2, Interesting

    You ignore what is probably the source of the misconceptions, namely Shor's algorithm which solves integer factorization in O(N^3) time and O(N) space (where N is the log of the number to be factored). However, integer factorization probably is not NP-complete and no one has figured out how to recast in polynomial time an NP-complete problem as a factoring problem that the Shor algorithm can handle.