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

## Re: (Score:2, Redundant)

That would lead to a revolution in efficiency of everything from travel to mass transit to shipping.Certainly a better example than a Sudoku solver... all a Sudoku puzzle is, at it's core, is a depth first search. You can speed up the algorithm with Dancing Links, but 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.

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

## Re:Sudoku: The np-easy version of Traveling Salesm (Score:2)

I didn't know that it would solve all boards except for the hardest ones.I've written one using DFS, it will solve all puzzles that have a solution. It stops when it reaches one solution. Having an application that can solve most, but not all puzzles isn't much help.

Took all the fun out of the game.I never thought it was fun to begin with.

## Re: (Score:2)

## Re: (Score:2)

Those puzzles are generally considered "broken" - but you can obtain a valid solution from those puzzles.

As an example of what I mean, consider the following puzzle grid - in the upper left corner, the digit is 1, in the far lower right hand corner, the number is 9 - multiple solutions exist that have a 1 in the (1,1) position and a 9 in the (9,9) position, and

## Re: (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 sho

## Re: (Score:2)

my wife thought I was insane, I learned a lot more about excel though.

I got it to two tier away solutions- if this can't be a 5, that must be a 7.

but never a third.. my head exploded just following the examples I saw on line of three dependencies to determine one number...

and trying to calculate how to account for that, other than brute force checking.....

## Re:Sudoku: The np-easy version of Traveling Salesm (Score:5, Funny)

You should have written it as a Word macro.

## Re: (Score:2)

## Re: (Score:3, Insightful)

## Re:Sudoku: The np-easy version of Traveling Salesm (Score:2, Funny)

I've built a Sudoku program to help me reduce the boring parts (filling in the only posssible option if it is known)Wait, those are the boring parts??

Took all the fun out of the game.I told you!

## Re: (Score:2)

## Re: (Score:2)

So is the travelling salesman problem, if you want to define it that way.

## Re:Traveling Salesman (Score:5, Informative)

The beauty is, if you solve

anyNPC problem you solve themall, 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: (Score:2)

## Re:Traveling Salesman (Score:5, Funny)

## Re: (Score:2)

Unfortunately, as the size of the puzzle increases to a level above what a human would ever try the sudoku solver would take a long, long time.And they didn't say the size of the puzzle they solved! So the demonstration could be: look, solves 9x9 *blink* done. Ok, 100x100 *blink* done.

## Re:Traveling Salesman (Score:4, Insightful)

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.

## Re:Traveling Salesman (Score:4, Insightful)

## Re: (Score:2, Insightful)

## 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:Traveling Salesman (Score:4, 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).

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2)

Currently the best solutions for TSP are based on

parallelsolutions, for which there is no shortage of hardware. Granted large parallel systems are not cheap (I'm not referring to little 4- and 8-way systems), but they do exist and are heavily used by researchers that require such technology.Distributed parallel clusters such as the approach used by the SETI "screen saver" also work for such classes of problems. Each node computes just

onepossible solution, but tens of thousands of nodes chew at solu## Re: (Score:2)

## Re:Traveling Salesman (Score:4, Funny)

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.Which, of course, clearly demonstrates the utility of the Bistro Drive for all Traveling Salesmen.

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

## Re: (Score:2)

Also, no one has proven that P != NP.

## Re: (Score:2, Funny)

## Re: (Score:3, Funny)

I think that it will solve the Traveling Salesman problem of course (find best possible path for salesman).

Unfortunately it shall to be run by salesman before every travel - so it isn't very useful.

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

## Re: (Score:3, Funny)

Did you at least try to scribble it in the margin of your book?

## Nope (Score:4, Funny)

Nope.

http://myspace-271.vo.llnwd.net/00407/17/24/40728

## BIGIT?? (Score:5, Informative)

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

## Re: (Score:2)

a|0> +b|1>, where |0> and |1> are linearly independent vectors in the state space, andaandbare complex numbers. I don't see why you couldn't have a third independent vector, giving qutits (?) of the forma|0> +b|1> +c|2>, and it probably doesn't even make the maths much harder; but binary qubits are easier to find in the physical world, such as the polarisation of photons.## Re: (Score:2)

## [QUIT] vs [KIT] (Score:4, Insightful)

And to avoid the massive worldwide suicide of voice-recognition software who suddenly log-out the computer, in the mid of the dictation of some research paper...

Dear aunt, let's set so double the killer delete select all.## Re: (Score:2)

"Qubit" is typically pronounced the same as "cubit", which is (IMHO) a lot catchier than "quit" or "qit".

## Qubit's a better word than bigit was. (Score:2)

One often over-looked factor in the shortening of words (because its completely subjective and unquantifiable) is whether or not the original word was cooler sounding and rolled off the tongue or not. "Bigit" just doesn't. "Qubit" is better. Both are two syllable words, so brevity isn't as much a factor, for English speakers at least, as it is for other shortened words like "auto." Ultimately, the relative awk

## "Bigit" never existed. (Score:4, Informative)

http://en.wikipedia.org/wiki/Binary_digit [wikipedia.org]

## Quick! (Score:2)

## Bill Cosby (Score:5, Funny)

## Re: (Score:2)

That led to the old joke - "When they build base-4 computers, will they call it quits?"

Anyway, qubit IS the right term, for Quantum Bit, or Quantum Binary Digit. It is perfectly binary, there are two eigensates, |0> and |1>, but the qubit can be in a linear combination of them. In fact, it can be in an imaginary linear combination of them, and the qub

## kit (Score:3, Funny)

"qit", (pronounced KITI don't think so, Michael.

## Re:BIGIT?? (Score:5, Funny)

## Re:BIGIT?? (Score:4, Funny)

## Re: (Score:3, Funny)

The metric system is the tool of the devil! My car gets forty rods to the hogshead, and that's the way I likes it!Jesus, you should start looking for a fuel leak. [google.co.uk]

## Re: (Score:3, Funny)

## Re:BIGIT?? (Score:5, Funny)

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

## Curious (Score:5, Interesting)

## Re:Curious (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?

## For real? (Score:3, Interesting)

## Re:For real? (Score:5, Informative)

## Ask the companies founder - here's his blog: (Score:5, Informative)

## Re: (Score:2)

## Re: (Score:2)

Wouldn't a 1024 qubit computer be far faster than any cluser on earth?Maybe, at factoring large numbers or something. But for doing your taxes or playing Quake it would be completely useless.

## Re: (Score:3, Funny)

But for doing your taxes or playing Quake it would be completely useless.I'm not sure about that...I've heard rumors of IBM unleashing

Deep Pwnupon the FPS world next year## Re: (Score:2)

Yes, you are mistaken [slashdot.org].

## This isn't fair! (Score:5, Funny)

## Or rather... (Score:4, Funny)

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

## Re: (Score:3, 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!

## Here me son of man! (Score:5, Funny)

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

:D I can't resist a bad pun.

-GiH

## Re:Here me son of man! (Score:4, Funny)

## Re: (Score:3, Funny)

## Re: (Score:2)

Otherwise it's just bloody annoying.

## I'm sorry but... (Score:2)

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2)

There was some talk a few years ago about DNA computing, which solved problems by generating all of the possible solutions in DNA and then doing an O(1) step to figure out which strand had the right properties for your solution. But since a TSP of 100 nodes required DNA weighing more than the planet Earth, tha

## Re: (Score:2)

## 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: (Score:2)

Also if it was so easy to do the NSA would be concerned about American info being snooped on. Surely they would rather that nothing can be snooped on than a free for all where everything can be snooped on.

## A what? (Score:2)

## Common misconceptions (Score:5, Informative)

requiresfast calculation of discrete logarithms.## Re:Ahhhh... But this is Analog (Score:2)

I'm guessing similarly this machine might quickly calculate solutions to things like Traveling Sales Man problem and other NP complete problems, but not be guaranteed to have found

## Re: (Score:2)

## Re: (Score:2)

That's a lot of number crunching. using a "true" quantumn computer you could set up a mul

## Re: (Score:2)

Also I don't think qubit is the right word any more because it sounds like each of the 16 qubits in this machine is really a whole value like a byte or a word, else it wouldn't be "analog"

Perhaps this thing will rock at some application that needs thousands or millions of NP-complete approximations per second to be practical. Maybe it can efficiently simulate neural networks. Maybe it can speed voice or vision recognition or assist

## Re: (Score:3, Interesting)

## Re: (Score:2)

## Re: (Score:2)

speedup, not quadratic running time. In other words, running time O(sqrt(2^n)) instead of O(2^n). As you probably have learned, sqrt(2^n) is sqrt(2^(n/2)).## Oops (Score:3, Funny)

Obviously that second sqrt() shouldn't be there, apologies (my original post is correct).

## A bold leap forward in computing (Score:5, Funny)

## Re: (Score:2)

## Let's ask corporations (Score:2)

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

## The funny thing about quantum computing is... (Score:3, Funny)

From what I understand, when you run Windows on a quantum computer it won't crash unless you look at it.

Also, the last time I used a machine with qubits, I had a hard time keeping them from jumping off the friggin' pyramid.

You've been great... I'm here all week... remember to tip your waiter.

## Details needed (Score:2)

## QIT not QUIT (Score:2)

It will be pronounced kit (no U sound) same as bit.

## Re:obligatory (Score:5, Funny)

Dev: Ah.. finally got it up and..

Linux: CRASH AND NOISE AND HORROR AND SCROLL SCREEN KERNEL DUMP!!

Dev:

||time passes||

Dev: okay, this time.. it stays up..

Linux:

||Five iterations later||

Dev: Finally... now.. WORK!!

Linux:

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: (Score:3, Funny)

Of course it is a quantum computer, so maybe it's done already and we just don't know it, because every time we look at it, it changes.

On the other hand it can only play Sodoku so far, so maybe not.

## Re:obligatory (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.

## Re:My suggestion for new tasks (Score:5, Funny)

## Re: (Score:2)

Meh. I'll believe it when I'm simulated by it.Who needs quantum mechanics? I can do it with an old TRS-80

10: Read Message

20: Make Smart Ass Reply

30: GOTO 10

RUN

## Re: (Score:2)

Meh. I'll believe it when I'm simulated by it.So PCs hit the mainstream when they could stimulate [pron] you.

Quantum computers will hit the mainstream when they can simulate you.

hmmm...

## Re: (Score:2)