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

13 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 hotdiggitydawg · · Score: 5, Informative

      all a Sudoku puzzle is, at it's core, is a depth first search. Which is not an algorithm that runs in polynomial time. It is a DFS of all (legal, remaining) permutations, which is an exponential number.

      even on a moderately fast PC a DFS is fast enough to get a solution to a Sudoku puzzle in the blink of an eye. Regardless of how easy a 9x9 grid seems, Sudoku is still at its core an NP Complete (PDF warning) problem. Why is it therefore any less valid than any other NP complete problem? Travelling Salesman is also pretty easy with less than 10 nodes... likewise you can feasibly crack any encryption scheme by brute-force if you constrain it to have a tiny key size. It's all about scale.

      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.
    2. Re:Traveling Salesman by nasch · · Score: 5, Funny

      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.
      As the CS gangsta rapper MC++ put it, "if we could factor large composites in poly time, we'd have enough money to not have to rhyme."
  2. BIGIT?? by CmputrAce · · Score: 5, Informative

    Never heard of one (bigit). I have, however, heard of the "binary digit" that was shortened to "bit". Given that history, "qubit" is short for "quantum binary digit" - which is an oxymoron since quantum digits can be any (or all) of several states, not just on or off (binary). A more accurate acronymish shortening would be "quigit" - which sounds awkward enough to be shortened to "qit", (pronounced KIT rather than QUIT to avoid confusion).

    I think "qubit" is here to stay, though.

  3. Re:Curious by paeanblack · · Score: 5, Funny

    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.

    That's why quantum computers will be so fast. If not, they will constantly forget... Damn. Where was I going with this?

  4. This isn't fair! by neo · · Score: 5, Funny

    I want to solve sudoku. Now some computer can do it so fast that it's finished before they even start? What good is that? Sudoku is supposed to be about wasting time, not reversing it.

  5. Re:For real? by jason8 · · Score: 5, Informative
    Apparently not a true quantum computer. From a wired news article:

    D-Wave held its first public demonstration Tuesday of a machine it claims uses quantum mechanics to solve a certain type of problems, such as searching a database for matching molecular structures.

    But the company did not make the machine available for inspection and instead showed video from a remote location, saying it was too sensitive to be easily transported.

    And notwithstanding lofty claims in the company's press release about creating the world's first commercial quantum computer, D-Wave Chief Executive Herb Martin emphasized that the machine is not a true quantum computer and is instead a kind of special-purpose machine that uses some quantum mechanics to solve problems.

  6. Re:obligatory by j00r0m4nc3r · · Score: 5, Funny

    But... does it run Linux?

    It runs all possible operating systems at once, but once you type a command in the probability wave collapses and you're stuck using AmigaDOS.

  7. Here me son of man! by GodInHell · · Score: 5, Funny

    I come to warn you that there shall be a great outage.. go forth and build an array to save my creations. Make it 100 qubits long, 30 qubits wide, and 10 qubits deep. Into this hash all data in /usr/god/dataM/ .. and /usr/god/dataF/

    Do this, and you shall survive the outage I shall send.

    :D I can't resist a bad pun.

    -GiH

  8. Common misconceptions by rbarreira · · Score: 5, Informative
    To save some work to people replying to misconceptions, here's a list of the common misconceptions about quantum computing that I've seen lately:

    • Quantum computers can solve NP-complete problems quickly (in polynomial time) -> not true, the speedup given by Grover's algorithm is quadratic, not exponential. This means that an NP-complete problem which would take O(2^n) in a classical computer would take O(2^(n/2)) in a quantum computer, which is clearly not polynomial time in n
    • Quantum computers with N qubits are as efficient as 2^N classical computers -> not true, not all algorithms can get an exponential speedup with quantum computing
    • Quantum computers will render cryptography useless -> not true, breaking asymmetric ciphers with QCs are subject to the quadratic speedup I explained above which means it will be enough to double the size of the key in order to account for QCs. Some symmetric ciphers (i.e. public key systems) are broken by quantum computing (for example RSA and discrete logarithm), but it is thought that there are some symmetric ciphers which are not vulnerable to attacks by QCs (excluding by the grover search algorithm, which as I explained above is not very hard to account for). Quite ironically, I remember reading that the same attack which renders discrete logarithm public key cryptography useless also allows for the existence of a public key encryption which requires fast calculation of discrete logarithms.
    --

    The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
  9. A bold leap forward in computing by Rob+T+Firefly · · Score: 5, Funny

    Immediately after booting, the Quantum Computer disappeared in a flash of light and noise. It resurfaced in 1985, where it briefly took over a Commodore 64 and corrected some mistakes it made the first time around, before moving onto a UNIVAC in 1955...

    --
    Slashdot Burying Stories About Slashdot Media Owned
  10. Re:My suggestion for new tasks by Farmer+Tim · · Score: 5, Funny

    You don't want quantum computers anywhere near the Slashdot front page: it'll only lead to more accusations of spin.

    --
    Blank until /. makes another boneheaded UI decision.
  11. Re:obligatory by GodInHell · · Score: 5, Funny


    Dev: Ah.. finally got it up and..
    Linux: CRASH AND NOISE AND HORROR AND SCROLL SCREEN KERNEL DUMP!!
    Dev: .. stupid drivers.. grr..

    ||time passes||

    Dev: okay, this time.. it stays up..
    Linux: ...loading.. CRASH!! OH GOD MY SPLEEN! NOT MY HARD DRIVE!! OWWW!

    ||Five iterations later||

    Dev: Finally... now.. WORK!!
    Linux: ...loading.. Hello Dave, can I help you?
    Dev: Yes! Finally!! Tell me, what is the meaning of life, the universe, and everything!?
    Linux: Oh that's simple.. spending time with your wife and kids.
    Dev: What.. oh.. God.. NO!!!

    I like linux.. and I like jokes at linux.. go figure.

    -GiH