Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Quantum Computer Demoed, Plays Sudoku

kdawson posted more than 7 years ago | from the more-qubits dept.

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

cancel ×

309 comments

Traveling Salesman (5, Interesting)

Short Circuit (52384) | more than 7 years ago | (#18023386)

Does this mean we'll be able to solve the Traveling Salesman [wikipedia.org] 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 (1, Redundant)

RailGunner (554645) | more than 7 years ago | (#18023454)

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 (2, Interesting)

Anonymous Coward | more than 7 years ago | (#18023588)

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.

Re:Sudoku: The np-easy version of Traveling Salesm (1)

RailGunner (554645) | more than 7 years ago | (#18023692)

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:Sudoku: The np-easy version of Traveling Salesm (1)

sglider (648795) | more than 7 years ago | (#18023938)

Correctly done, Sudoku puzzles have only one solution -- perhaps I'm missing something in your statement?

Re:Sudoku: The np-easy version of Traveling Salesm (1)

RailGunner (554645) | more than 7 years ago | (#18024196)

Depending on how many initial numbers are given at the start of the puzzle, multiple solutions to a specific initial set of numbers could exist.
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 a complete solver should account for that. My application does not - it finds the first solution that meets that criteria.

Re:Sudoku: The np-easy version of Traveling Salesm (2, Interesting)

geoffspear (692508) | more than 7 years ago | (#18024376)

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.

Re:Sudoku: The np-easy version of Traveling Salesm (1)

jared9900 (231352) | more than 7 years ago | (#18024332)

Correctly DESIGNED Sudoku puzzles have only one solution. It's possible to make a puzzle that is ambiguous by removing too many numbers, or just the wrong number, from a puzzle.

Re:Sudoku: The np-easy version of Traveling Salesm (1)

way2trivial (601132) | more than 7 years ago | (#18024160)

I wrote one using excel.

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 (0)

Anonymous Coward | more than 7 years ago | (#18024210)

Having an application that can solve most, but not all puzzles isn't much help.

I disagree. Such a program will allow the human to focus on the interesting boards, identify new patterns, etc. I never wrote it to solve the boards, I was actually amazed that it did.

Besides, what are you trying to prove? That you can write a Sudoku solver better than me? You won technically, as I never wrote a sudoku solver and you did.

Let's get to the point: Demonstrating a 16-quit computer on the Sudoku "optimization" task is only useful for show-off reasons, it is not technically needed. I'm quite sure a 10-year-old TI calculator can do the job cheaper.

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

pato101 (851725) | more than 7 years ago | (#18023838)

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:Traveling Salesman (1)

rbarreira (836272) | more than 7 years ago | (#18024478)

all a Sudoku puzzle is, at it's core, is a depth first search.


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

Re:Traveling Salesman (5, Informative)

hotdiggitydawg (881316) | more than 7 years ago | (#18024506)

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 [u-tokyo.ac.jp] (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 (3, Insightful)

TorKlingberg (599697) | more than 7 years ago | (#18023690)

There are fast and almost-exact algorithms for Traveling Salesman problem that are good enough for practical purposes.

Re:Traveling Salesman (2, Insightful)

Anonymous Coward | more than 7 years ago | (#18023808)

I think you've missed the point of the Traveling Salesman problem. It's a theoretical mathematical exercise, not a practical issue in mass transit or shipping. The important bit is that we could solve all sorts of other, more interesting problems if we could solve that one.

Re:Traveling Salesman (4, Interesting)

Ed Avis (5917) | more than 7 years ago | (#18023844)

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 (5, Informative)

gazbo (517111) | more than 7 years ago | (#18024008)

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 (4, Informative)

Anonymous Coward | more than 7 years ago | (#18024212)

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 (1)

KurtP (64223) | more than 7 years ago | (#18024276)

Actually, to be quite clear, the "Travelling Salesman" problem is one of traversing an arbitrary graph, which can indeed include information representing non-straight distances and preferred edges where the "good lunch places" can be found. It's a very general optimization problem, and has been effectively solved for practial use for a number of years, using the "simulated annealing" method.

Re:Traveling Salesman (1)

georgep77 (97111) | more than 7 years ago | (#18024446)

Actually there are many variations on the Traveling Salesman that an optimal solution is required for. In a previous life I worked on some software for laying out circuit boards, massive circuit boards. In fact the speed of the production line was limited by how long it would take the robots to place everything on the board. We managed to have a fairly optimal solution by dividing up the card into smaller regions (bands) and solving each one individually. The less distance the robot would traverse the better, thus the traveling salesman.

Cheers,
      _GP_

Re:Traveling Salesman (1)

khallow (566160) | more than 7 years ago | (#18024606)

But an optimal solution is not required in the routing problem you cite. After all, you went for "fairly optimal" rather than optimal because at some point, the cost of computing time required (assuming generously that the problem is solvable in our universe, it doesn't take much for a routing problem to pass that threshhold) exceeds the benefit to be gained.

Re:Traveling Salesman (3, Funny)

Zdzicho00 (912806) | more than 7 years ago | (#18023980)

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.

/Z

Re:Traveling Salesman (1)

Short Circuit (52384) | more than 7 years ago | (#18024128)

Unfortunately it shall to be run by salesman before every travel - so it isn't very useful.
My understanding of quantum computers is certainly limited, but the only inherent time limitation I know of involves loading all possible solutions into the computer before telling the computer to select the best solution. If one can find a way to re-use the solution set, that problem goes away.

Nope (4, Funny)

Anonymous Coward | more than 7 years ago | (#18023426)

"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 [llnwd.net]

Moo (1)

Chacham (981) | more than 7 years ago | (#18023450)

Anyone want to guess how long before "qubit" gets compressed to "quit"

Actually, people "quit" "Q-Be(r)t" a decade ago. Hmm.. quantum machanics is funny that way.

(as "bigit" became "bit" in the last century)?

No, bigots still (unfortunately) play a very large role.

BIGIT?? (5, Informative)

CmputrAce (300653) | more than 7 years ago | (#18023490)

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

wolverine1999 (126497) | more than 7 years ago | (#18023560)

qit is better. Reminds me of KITT though :)

Re:BIGIT?? (1)

GungaDan (195739) | more than 7 years ago | (#18023612)

More accurate still would be QWIJIBO.

Re:BIGIT?? (1)

CmputrAce (300653) | more than 7 years ago | (#18023664)

(nice tag, BTW)

Quidigit? (1)

maroberts (15852) | more than 7 years ago | (#18023872)

Sounds like a game played on flying broomsticks...

Re:BIGIT?? (1)

uptimejesus (1053366) | more than 7 years ago | (#18023880)

And eight of them is a kite, right?

Re:BIGIT?? (1)

Wooster_UK (963894) | more than 7 years ago | (#18023930)

Well, a qubit is binary in the sense that while it can be can be in a superposition of many different states, those states are all constructed from two basis states, normally written "0" and "1". It's only a sense, granted, but the description isn't completely without foundation.

Re:BIGIT?? (1, Insightful)

Red Jesus (962106) | more than 7 years ago | (#18023966)

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).
Close but not quite. The "several states" a single qubit can assume are all just combinations of a zero and a one. Think of it as a qubit being an expression like "37% zero, 63% one." Physicists write the percentages as complex numbers (which adds an extra complication called "phase," but we've still got "(0.733+0.431i) zero, (0.375-0.369i) one."

Things do get more complicated when multiple qubits are strung together but they still represent zeroes and ones. A three-qubit system can be described by eight complex numbers that keep track of the probability (called "amplitude") of the states 000, 001, 010, 011, 100, 101, 110, and 111. Qubits are bits.

If you want to be annoying and say, "What about a three-state system, where instead of dealing with spin up and spin down, you get spin up, spin zero, and spin down?" then you would have a valid point. But nobody calls such a system a "qubit," any more than we could say that an ordinary electrical circuit holds an ordinary bit if it's allowed to assume three distinct voltages instead of just the usual "high" and "low."

Good job getting one of the first posts, though.

Re:BIGIT?? (1)

Excors (807434) | more than 7 years ago | (#18023998)

But qubits are a superposition of the two binary states – they're a|0> + b|1>, where |0> and |1> are linearly independent vectors in the state space, and a and b are complex numbers. I don't see why you couldn't have a third independent vector, giving qutits (?) of the form a|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:BIGIT?? (1)

LihTox (754597) | more than 7 years ago | (#18024020)

"Qubit" is pronounced "Q-bit", not "kwuh-bit" or the like; it seems unlikely that "Q-bit" would become "quit" or "qit" in spoken English.

[QUIT] vs [KIT] (3, Insightful)

DrYak (748999) | more than 7 years ago | (#18024150)

"qit", (pronounced KIT rather than QUIT to avoid confusion).


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:BIGIT?? (1)

Thuktun (221615) | more than 7 years ago | (#18024162)

Never heard of one (bigit).
It appears kdawson coined it on the spot. "Bit" came directly from "binary digit" without an intervening abbreviation.

"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. (1)

Valdrax (32670) | more than 7 years ago | (#18024234)

I'm going to argue that "qubit" will most likely never be shorted, and certainly not to "quit."

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 awkwardness of saying the long version would be a greater factor.

However, I think the biggest factor stopping the use of "quit" is that it's semantically confusing. Using the word "bit" for a binary digit meshes well with an existing meaning -- a small piece or fragment. Even without knowing the etymology of "bit," a new reader to the subject material quickly absorbs its meaning because of this. Using "quit" for quantum bit does not really mesh with existing meanings and would only add confusion to new readers. I don't think it'll catch on for that reason.

"Bigit" never existed. (3, Informative)

caveat (26803) | more than 7 years ago | (#18024262)

Claude E. Shannon first used the word bit in a 1948 paper. He attributed its origin to John W. Tukey, who had written a Bell Labs memo in 9 January 1947 in which he contracted "binary digit" to simply "bit".
No mention of "bigit", seems to have just been invented today.

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

Quick! (1)

benhocking (724439) | more than 7 years ago | (#18024542)

Who's going to be the first to add [wikipedia.org] "bigit" to Wikipedia? It should say something like: "Term first coined on /. in order to be re-abbreviated as 'bit'. Used to make example of how 'qubit' might one day be called 'quit'. Bigit should rhyme with digit so as to not be confused with bigot."

Bill Cosby (4, Funny)

sconeu (64226) | more than 7 years ago | (#18024346)

Lord, what's a Qubit?

Re:BIGIT?? (0)

Anonymous Coward | more than 7 years ago | (#18024490)

I never heard of a "bigit" either, and I've been studying computers since 1982. Every book I read said (as you pointed out) that "bit" was short for "binary digit". I looked it up in both dictionary.com [reference.com] and Wikipedia [wikipedia.org] and found no results for "bigit" in either.

Without having a reference cited, I must come to the conclusion that kdawson is just making shit up. I urge him to clear this up for us, lest we all think he's a bigit (see below) trying to sound smart.

I fondly remember the "bit" character in Tron (Yes yes yesyesyesyes... nononono"). I was amazed that Disney would let the blatant drug references stay in; "tron", of course, being a BASIC command to turn something on, as well as the scene where they drink from the "energy pool" ("Man, we have SCORED!") with the programs (and Flynn) acting like they had just snorted cocaine.

Qubit reminded me of one of my favorite 80s computer games, "Q-Bert". Ah, the memories...

As (again) to "bigit", if there would have been such a character in Tron would he be a bigoted individual, or a big British git?

-mcgrew

Re:BIGIT?? (1)

aditi (707829) | more than 7 years ago | (#18024652)

Only till Mega qubits and Giga qubits come along.

obligatory (0, Redundant)

Anonymous Coward | more than 7 years ago | (#18023492)

Imagine a beowulf cluster of these running Linux!

Re:obligatory (0, Troll)

Eudial (590661) | more than 7 years ago | (#18023500)

Imagine a beowulf cluster of these running Linux!


But... does it run Linux?

Re:obligatory (0)

Anonymous Coward | more than 7 years ago | (#18023728)

The simple answer is yes.

Re:obligatory (1)

Hal_Porter (817932) | more than 7 years ago | (#18023790)

No, and it probably won't run any existing OS or language.

You can load an N bit register with all the possible values of that register at the same time, and then do operations on all the possible values in parallel. But the operations would presumably not be anything like the bitwise operations in a classical computer.

Here's an example

http://en.wikipedia.org/wiki/Shor's_algorithm#Quan tum_part:_Period-finding_subroutine [wikipedia.org]

Re:obligatory (0)

Anonymous Coward | more than 7 years ago | (#18024322)

Boy you uber-geeks can really ruin a joke, can't you? OK, how about this one: Two Trek dorks leave their parents' basements, and go to a bar...

Re:obligatory (2, Funny)

Undertaker43017 (586306) | more than 7 years ago | (#18023800)

Not yet, give it a week.

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 (5, Funny)

j00r0m4nc3r (959816) | more than 7 years ago | (#18023802)

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:obligatory (1)

StarfishOne (756076) | more than 7 years ago | (#18024432)

And if you're lucky, the cat is still alive! =^.^=

Re:obligatory (5, Funny)

GodInHell (258915) | more than 7 years ago | (#18024410)


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

My suggestion for new tasks (0)

PsyQo (1020321) | more than 7 years ago | (#18023502)

My suggestion for new tasks: Serve videos linked from the slashdot frontpage, serve videos linked from the slashdot frontpage and serve videos linked from the slashdot frontpage.

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

Farmer Tim (530755) | more than 7 years ago | (#18024400)

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

Yeah, but (0)

Anonymous Coward | more than 7 years ago | (#18023512)

Does it run Linux? In all seriousness, I'd like to see how quickly this thing could brute force SHA256 from a 65,000 word dictionary file.

qubit (1, Funny)

Anonymous Coward | more than 7 years ago | (#18023608)

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

I got dibs on "forever"

Curious (4, Interesting)

vlad_petric (94134) | more than 7 years ago | (#18023630)

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 (5, Funny)

paeanblack (191171) | more than 7 years ago | (#18023680)

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? (2, Interesting)

DurendalMac (736637) | more than 7 years ago | (#18023650)

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.

Re:For real? (5, Informative)

jason8 (917879) | more than 7 years ago | (#18023734)

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.

Ask the companies founder - here's his blog: (4, Informative)

RMH101 (636144) | more than 7 years ago | (#18024318)

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

Re:For real? (1)

geoffspear (692508) | more than 7 years ago | (#18024532)

A simple transistor uses "some quantum mechanics" too. I call BS.

Re:For real? (1)

LiquidCoooled (634315) | more than 7 years ago | (#18023744)

A quantum computer is really quick.
It can answer really advanced problems, like "given all these bricks what is the tallest structure you can build?"

A traditional computer program would get the dimensions of one brick and the quantity of bricks and calculate the height.

A quantum computer could tell you how tall the structure is, but in order that you can do it, you have to build the structure for it so it can measure it.

I see all this crap as smoke and mirrors and nothing has so far given me anything to change my mind.

Re:For real? (1)

timster (32400) | more than 7 years ago | (#18023874)

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:For real? (2, Funny)

paeanblack (191171) | more than 7 years ago | (#18024508)

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 Pwn upon the FPS world next year

Re:For real? (1)

rbarreira (836272) | more than 7 years ago | (#18024426)

And if I'm not mistaken, a 16 qubit computer would be faster than any single computer.

Yes, you are mistaken [slashdot.org] .

This isn't fair! (5, Funny)

neo (4625) | more than 7 years ago | (#18023710)

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.

The Amazing Thing Is... (1, Funny)

Anonymous Coward | more than 7 years ago | (#18023716)

...somewhere in the universe there is a computer just like it
unsolving the Sodoku puzzle at the exact same time.

FTLQTDC ... Faster Than Light Quantum Tunneling Disinformation .. like this post.

Doesn't make much sense (0)

Anonymous Coward | more than 7 years ago | (#18023786)

IANAQP, but isn't Sudoku (the general case, not the trivial 9x9 sized problems that humans usually solve) NP-complete, and it is known that quantum computers cannot efficiently solve NP-complete problems, but only slightly "easier" ones like integer factorization, which are in a complexity class called BQP?

I know this is just a small proof of concept, but why not attempt to solve a problem that QC is actually useful for?

Or rather... (3, Funny)

null etc. (524767) | more than 7 years ago | (#18023796)

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:Or rather... (2, Interesting)

kabocox (199019) | more than 7 years ago | (#18023886)

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! (5, Funny)

GodInHell (258915) | more than 7 years ago | (#18023836)

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

Re:Here me son of man! (3, Funny)

Apocalypse111 (597674) | more than 7 years ago | (#18024220)

Damn! You beat me to it! I was gonna post something like this myself, but the flood-protection was telling me to wait.

I'm sorry but... (1)

rice_web (604109) | more than 7 years ago | (#18023882)

But quantum physics allows particles like atoms, electrons and photons to be in two places at once--meaning they can represent 0 and 1 simultaneously, allowing more complex calculations.
How is this different from ternary logic?

Re:I'm sorry but... (1)

rice_web (604109) | more than 7 years ago | (#18023950)

Ah... nevermind. Wikipedia has a pretty good article [wikipedia.org] on it.

Re:I'm sorry but... (0)

Anonymous Coward | more than 7 years ago | (#18024048)

Grandparent is wrong. They are not 0 and 1 at the same time but are 0 with some probability p and 1 with some probability q where p+q=1. At the point of measurement the probabilities collapse and we get either 0 or 1 as the state of the qubit.

Re:I'm sorry but... (1)

ambrosen (176977) | more than 7 years ago | (#18024090)

A 16 qubit machine will calculate the results for all 65536 states that the qubits can be in simultaneously. Make a 1024 qubit machine, and you can factorise a 1024 bit number in constant time. Essentially it will meant that all NP-complete problems of a small enough size will be solvable in (low order) polynomial time.

Re:I'm sorry but... (1)

jfengel (409917) | more than 7 years ago | (#18024272)

As long as the number of qubits required is proportional to N and not to something bigger, it still counts as polynomial time, no matter the size. It just adds an extra factor of N to the polynomial.

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, that didn't go much of anywhere. It was really O(2^N) rather than O(1).

Re:I'm sorry but... (1)

Dr. Eggman (932300) | more than 7 years ago | (#18024274)

Ternary logic represents 3 values, in a balanced ternary system -1, 0, +1. It is similar in that 0 represents both + and - like a superpositioned qubit. The difference is the entanglement of the qubits. A qubits that is entangled with another, even if separated, must measure the same as the one it is entangled with, allowing for multiple calculations to occure at once; something that ternary logic doesn't do, though someone correct me if I'm wrong. Interesting to note there's a 'qubit' for ternary logic as well called the qutrit.

Re:How is this different from ternary logic? (1)

roguegramma (982660) | more than 7 years ago | (#18024608)

This is different from ternary logic in that if you take N qubits, you get 2^N combinations to which the computation will be applied simultaneously, while if you had N ternary digits, you would have a fixed single state for each digit, even if it was 3 states instead of just 2 states as with bits.

The hard part about making qubits work is to keep them shielded from random outside influence while all of them stay qubits not bits. It is so hard that I wonder whether the company mentioned isnt selling vapourware.

breaking cryptopgraphy with Quantum computing (3, Interesting)

Danathar (267989) | more than 7 years ago | (#18023988)

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.

A what? (1)

Seraphim_72 (622457) | more than 7 years ago | (#18024006)

Anyone want to guess how long before "qubit" gets compressed to "quit" (as "bigit" became "bit" in the last century)?
Qubits? How many is that in Quatloos [wikipedia.org] ?

Common misconceptions (5, Informative)

rbarreira (836272) | more than 7 years ago | (#18024018)

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 [wikipedia.org] 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.

Re:Common misconceptions (-1, Redundant)

Anonymous Coward | more than 7 years ago | (#18024164)

Um, quadratic is n^2, not 2^(n/2). The later is still exponential, the division by two have little effect on growth. That alone leads me not to believe the rest of your BS.

Re:Common misconceptions (1)

rbarreira (836272) | more than 7 years ago | (#18024206)

I said quadratic 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 (2, Funny)

rbarreira (836272) | more than 7 years ago | (#18024246)

As you probably have learned, sqrt(2^n) is sqrt(2^(n/2)).

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

Re:Ahhhh... But this is Analog (1)

DumbSwede (521261) | more than 7 years ago | (#18024482)

This would all be true for a Quantum Computer based on Binary, but this is an "Analog" computer. Back in the 40's and 50's Analog computers could run rings around digital computers in their domains, but they where only approximations, but for plotting flight plans and trajectories a few digits of precision where often enough.

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 the optimal solution, just a very, very, very good one quickly.

Re:Ahhhh... But this is Analog (1)

rbarreira (836272) | more than 7 years ago | (#18024528)

Since I'm not very familiar with the things you mentioned there, I'll ask: how better would the analog QC solutions be, compared to the current approximation algorithms for NP-complete problems? References/links welcome :)

creates a complicated seating plan, plays sudoku (1)

Joe Snipe (224958) | more than 7 years ago | (#18024110)

Big deal, I can do that already by myself.

QUBIT vs BIGIT (1)

Efialtis (777851) | more than 7 years ago | (#18024118)

BIGIT became BIT, but QUBIT won't become QUIT... it most likely will become QUT (pronounced CUTE)...

Re:QUBIT vs BIGIT (0)

Anonymous Coward | more than 7 years ago | (#18024488)

It won't shrink to "quit" or "qut" - it will shrink to "qbit."

A bold leap forward in computing (5, Funny)

Rob T Firefly (844560) | more than 7 years ago | (#18024180)

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

Re:A bold leap forward in computing (1)

Jsprat23 (148634) | more than 7 years ago | (#18024466)

Oh Boy

Let's ask corporations (1)

A beautiful mind (821714) | more than 7 years ago | (#18024192)

Anyone want to guess how long before "qubit" gets compressed to "quit" (as "bigit" became "bit" in the last century)?
Let's ask corporations, after all they were the wants that exchanged "rabbit" meat for "rat"...

mod 0p (-1, Troll)

Anonymous Coward | more than 7 years ago | (#18024296)

more grandIose

More info... (4, Informative)

Panaflex (13191) | more than 7 years ago | (#18024316)

Some more videos...
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.

Sudoku? (0)

Anonymous Coward | more than 7 years ago | (#18024486)

I wrote a perl program that will solve Sudoku programs and it doesn't need a quantum computer. Perhaps, can we demo something that requires a bit more processing power?

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

Coco Lopez (886067) | more than 7 years ago | (#18024572)

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.

Quantum leap (1)

Impy the Impiuos Imp (442658) | more than 7 years ago | (#18024584)

> Quantum Computer Demoed, Plays Sudoku

Meh. I'll believe it when I'm simulated by it.

Details needed (1)

J.R. Random (801334) | more than 7 years ago | (#18024634)

One problem with a demo of this sort is that it isn't possible to know how much was actually done by the quantum computer and how much was done by the classical front end computer. Typical Sudoku puzzles can be solved essentially instantaneously by classical computers. 16 qubits isn't a heck of a lot of quantum parellelism, so I do wonder how much of the real work they were doing.
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...