Quantum Computer Demoed, Plays Sudoku

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

Comments

Traveling Salesman

[Short Circuit]

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.

Re:Traveling Salesman

[Ed Avis]

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.

Re:Traveling Salesman

[gazbo]

Even if you could solve TSP in polynomial time on a quantum computer, it still wouldn't show that P=NP as the machine would be nondeterministic. The goal of quantum computers is to sidestep the NP issue, not reduce it to P.

Re:Traveling Salesman

[Anonymous Coward]

You are pretty much correct--traveling salesman is NP-hard and most theorists believe that BQP, the class of problems efficiently solvable by a quantum computer in polynomial time, is strictly smaller than NP (and therefore contains no NP-complete problems). This is, of course, not shown--for all we know, it could even be strictly bigger than NP. The evidence is that the only two problems quantum computers can solve in polytime right now that a turing machine can't are integer factorization and discrete log, neither of which is believed to be NP-hard.

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

Re:Traveling Salesman

[hotdiggitydawg]

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.

Re:Traveling Salesman

[nasch]

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."

Re:Traveling Salesman

[tbo]

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

Re:Traveling Salesman

[DusterBar]

The first digital computer systems did not solve anything "amazing" but the fact that they solved anything at all was the amazing bit.

Quantum computing is very new (in the physically exists sense) and the fact that they figured out how to build, program, and extract the solutions for some, albeit relatively simple, problems is a major step forward.

Once the understanding is complete enough and reliable enough then the really tough problems will be sure to follow.

Nope

[Anonymous Coward]

"Anyone want to guess how long before "qubit" gets compressed to "quit" (as "bigit" became "bit" in the last century)?"

Nope.

http://myspace-271.vo.llnwd.net/00407/17/24/407284 271_s.jpg

BIGIT??

[CmputrAce]

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.

Re:BIGIT??

[HTH NE1]

Only if four of them is a quibble.

Re:BIGIT??

[cellocgw]

"qit is better."

I vote for "qute," pronounced like the way you'd describe your girlfriend if you had one.

Curious

[vlad_petric]

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.

Re:Curious

[paeanblack]

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?

This isn't fair!

[neo]

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.

Re:For real?

[jason8]

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.

Re:obligatory

[j00r0m4nc3r]

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.

Here me son of man!

[GodInHell]

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

Common misconceptions

[rbarreira]

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.

A bold leap forward in computing

[Rob T Firefly]

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...

More info...

[Panaflex]

Some more videos...
High level explanation
Protein matching
Sudoku

Also, here's some slightly older talk at Stanford with a higher-level audience

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:

[RMH101]

Geordie Rose's blog: http://dwave.wordpress.com/

Bill Cosby

[sconeu]

Lord, what's a Qubit?

Re:My suggestion for new tasks

[Farmer Tim]

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

Re:obligatory

[GodInHell]

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

Re:Sudoku: The np-easy version of Traveling Salesm

[Intron]

This is an example of using the wrong tool for the job.

You should have written it as a Word macro.