Slashdot Mirror
A Working Quantum Computer in 3 Years?
prostoalex writes "Vancouver, BC-based D-Wave Systems got $17.5 mln from Draper Fisher Jurvetson to work on a preliminary version of a quantum computer, Technology Review reports. Delivery date? Within three years: 'It won't be a fully functional quantum computer of the sort long envisioned; but D-Wave is on track to produce a special-purpose, "noisy" piece of quantum hardware that could solve many of the physical-simulation problems that stump today's computers, says David Meyer, a mathematician working on quantum algorithms at the University of California, San Diego.'"
Yeah, but will it play Duke Nukem Forever??
The truth shall always be free: Boris Floricic is Tron.
There's already one out there...
http://darwinia.co.uk/
All your possible answers are belong to us!
The whole mania behind this technology is that somehow we will be able to pull correct data out of thin air using the magical properties of quantum units. Somehow eigenvalues will just instantaneously pop into existence by the careful selection of input parameters.
Too bad that's not how it works. These computers will still have to process data the same as any other processor and all the threat behind magically decoding 128-bit encryption is pure fluff. We are talking about another way of computing, for sure, but it is just another step in the evolution of computing systems rather than a brand new magic bullet for encryption maniacs.
It is also unclear why people want to build a "quantum computer" when it seems that simply putting it on a peripheral board and using it as a separate calculation machine seems to be a much more straightforward application of the device than trying to cram a whole computer with these chips.
__
Funny Adult Vido Clips
Why didn't Steve Jobs hold out for this? Just imagine, we could have been using qMacs in three years time...
Hate to burst your little american-centric bubble, 'educated' as you know doubt are by dubya's propaganda machine, but having a damned powerful computer in no way makes it easier for someone to design a bomb, as me having XCode makes it easy for me to write a program, as I can't actually program. Unless they're already a dems expert, it won't mean shit unless these things ship with a BuildMeANuke.app running on them. And of course there is the little fact that it's fairly easy to build bombs bug enough to take out 100% of the US. Not that 100% of the US is actually worth targeting. You'd hit the major cities and military bases and go on to targeting your real enemies, which since I'm guessing you're using Bush's definition of terrorist (aka Arab), would probably be Tel Aviv.
The truth shall always be free: Boris Floricic is Tron.
Someone please alert the parents of this 12-year-old, he clearly snuck out to the computer while he was supposed to be sleeping.
DOS v6.22 flies...
Resident of Skara Brae since 1985
The 2006, 2007, 2008 Vaporware Award goes to D-Wave Systems.
Wow, a Quantum Computer that only exist in a "Powerpoint Universe ©".
Grundgesetz * 23. Mai 1949 - 30. November 2007 - http://www.vorratsdatenspeicherung.de/
On a more serious note... a fully operational quantum computing device in 3 years? Did they borrow their marketing/timeline departments from the Longhorn division of Micro$oft?
The Peanut Gallery, Ubergeek, Biblically Sober
NCAAbbs.com: Thousands of fans, Hundreds of teams, Just one place
I could be wrong here, but isnt quantum computing where CPUs are atoms and not electronic circuits. So that means you can have differnt levels of atoms as they are so small, and as they are so small can fit many many (thats my word for a fuck load) of atoms on a cpu surface so if each atom can pass on 'message' and you have many levels each filled with (i have no number so we call it 1^100) atoms on each level you would be hitting speeds close to the human brain. I could be totally wrong here I am using infomation i was told about, about 2 years ago now.
Visit My Blog at http://spaces.msn.com/members/chrisharries
... but it's not a proper quantum computer. It's based on tunneling, not entanglement. The latter is what everyone understands by the term 'quantum computer'. Their computer just requires knowledge of quantum theory to build it. Well, so do conventional computers...
Having a private super-computer in your garage would give you the power to decrypt standard government encryption (still at 56bit?).
It's similar to having a cache of firearms in your garage; expect a visit from the government who wants to know what you're doing with it.
Mod Parent up! it is so much funnier than that stupid Duke Nukem forever cliche. Now the Beo cluster cliche fits perfectly. sorry for the disturbance.
This is quite a piece of vapor news though - and may be the most blatant to date. It uses both 'special-purpose' and 'could' in the description of the kit.
It is even remarkably specifically non-specific about what it _could_ achieve. Nice. I like.
Will it run Longhorn?
No matter how fast or slow those computers (or better specific algorithm executers) will be is unclear, but forget thinking in Ghz or something for Quantum Computers.
HI O WISE PRINCE. WHT TOOK U SO DAM LONG?
Better to clarify: http://en.wikipedia.org/wiki/Quantum_computing
Is that no one will be able to tell accurately if one will exist or not in three years until it is actually observed.
That's what we're missing these days - noisy computers! We need whirring, and clanking, and popping, and probably a steam-powered whistle. Forget these silent PCs - I want to really know when it's doing some calculations!
Get your own free personal location tracker
I had a computer with a Quantum hard drive 15 years ago,
Fascinating, the article is even dated July 2005, obviously a quantum effect.
Their site says
Quantum computers can be used to get approximate solutions to large NP-complete optimization problems much more quickly than the best known methods running on any supercomputer.
Did someone invent a quantum algorithm that makes a dent in NP-complete? News to me.
Sure, I mean it could be vaporware and a nice way to seperate 18 mill (US or Canidan?) from some VCs...
However, given that they have narrowed their focus (from a general purpose machine) to a special purpose machine using (they say) todays level of technology, they have a good chance..
Known and working tech + narrow problem = Engineering + Marketing = A working product
http://www.hawknest.com/
Personally I think taking out 96% of the US, would do the rest of the world a favour.
Thats my opinion anyway, y'all.
People have been building quantum computers for years now. The biggest ones these days (around 14-qubits) are NMR quantum computers, although that technique appears to have scalability issues.
Seems to me that this is only news since they plan on selling quantum-CPU time.
Known and working tech + narrow problem + Engineering = A working product
A working product + Marketing = A selling product
This is somewhat offtopic, but I ran across it a few months ago and it's really interesting. QCL allows you to write and run quantum algorithms. Runs on Linux and OS X with some tweaking.
The documentation that comes with it is really interesting, and gives some good insights into how quantum computing works and how to write programs for a quantum computer.
Famous Last Words: "hmm...wikipedia says it's edible"
" Having a private super-computer in your garage would give you the power to decrypt standard government encryption (still at 56bit?)"
Is your gov not 'protecting' you adequately?
Or is it itself(your gov) a stealing/lying/plundering villan ??
I think the 'world' needs 'protection' from your gov, so anything to 'break' them is welcomed by me!!!
We'd better start learning Q++; or better yet preparing the port to .quant platform.
..
..
Start to code those void Byte2Qbyte(QBYTE* pOut, const BYTE *pIn) NOW!!
We should start building an open source STL extension around template class QAlgo<..>, QBit<..>,
It's going to be too late when they hit us with US patent #1.232.322.999
OR when they start outsorcing the Q++ development to India once more..
This time, we gotta be ready!!!
Quantum PVP may be built before that...
Yow...
I realize modern tech support doesn't need to know much to anything about electronics or computer hardware's innerworkings... but I wonder if quantum computers will change that... and how many years of school will quantum tech support need?
===
It doesn't seem likely, but it'd be neat to have the title "Quantum Mechanic" EHEH!
MoM++ - A Classic Expanded - [Master of Magic 1.5]
http://mompp.sourceforge.net/
Can anyone tell me what this has to do with the real world? This "article" looks more like a repackaged press release to me. What real-world problems could be solved "in seconds", rather than "centuries" as the article states, IIRC?
Where do people come up with these? Is it really so hard to type out "million?" Who abbreviates "million" as "mln?" This is worse than "$.4M" from a little while ago.
Huh...that abbreviation appears all over the net. I still say it's stupid, but I suppose that's pretty much just because I never heard of it. No, it's just plain stupid. Do we really need to save 4 bytes?
Honest to God, I think those anti-ware hippies can tie in the fact that war is bad into anything, including posts on quantum computing. Next up, PETA passes message through nanomachines.
It's not like Windows is a viable option, and would Linux "scale" to one of these things?
"Consider how lucky you are that life has been good to you so far. Alternatively, if life hasn't been good to you so far
It won't be a fully functional quantum computer of the sort long envisioned...
(We'll have Quantum Pong(R) running on it.)
/^([Ss]ame [Bb]at (time, |channel.)){2}$/
but having a damned powerful computer in no way makes it easier for someone to design a bomb
Unless they know how to build a bomb, and their job would be easier (or produce more horrific results) with better tools.
Unless they're already a dems expert, it won't mean shit
You mean, like all sorts of ex-Soviet military scientists? Or some fairly-well-trained folks in Iran or North Korea?
And of course there is the little fact that it's fairly easy to build bombs bug enough to take out 100% of the US.
You must mean that it's possible to build enough bombs for that purpose. Or, that a handful of them, all in key cities, would be economically devastating enough to have that general effect.
which since I'm guessing you're using Bush's definition of terrorist (aka Arab)
Terrorists are as terrorists do. So far we're not running into a lot of Swedish or Japanese terrorists. The part of the world, culturally, that seems happy to blow up restaurants and buses because their religious leaders say that's what Allah wants them to do, seem to mostly be from the middle east. There are abberations (we've had a few domestic ones, and there's always the IRA, or those cultists in Japan a few years back), but it really makes the most sense to pay attention to places in the world where chanting "death to America" is part of every news broadcast, and where the more extreme margins of the cultures that support that attitude also have the time, money, and inclination to act on the urge (and have a demonstrated history of actually doing it). You didn't think that the people dead in Madrid were killed by unhappy Spaniards, did you?
Don't disappoint your bird dog. Go to the range.
Possibly, if it weren't for the fact that it'd prolly cause a sudden economic collapse
Please, for the good of Humanity, vote Obama.
Not sure about the ethics of that but it would certainly help solve the travelling salesmen problems.
SalesBoss: Salesman, use your sales skills and this new computer to visit all our target customers throughout the US as efficiently as you can.
SalesMan: Computer, provide me with the most efficient route to our customers in the US
Computer: Citizens in the US have been eliminated, your travel milage is Zero. Please stay where you are.
Provided that your measurement either of "working" or "3 years" is sufficiently imprecise.
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.
Not sure about the ethics of that but it would certainly help solve the travelling salesmen problems.
Yes, because at the quantum level, everywhere in the US is just one place.
But it's a big place.
You didn't think that the people dead in Madrid were killed by unhappy Spaniards, did you?
ETA were a possibility. They do fit the description "unhappy spaniards" rather well.
Longhorn's still got a chance.
Raise your children as if you were teaching them to raise your grandchildren, because you are.
They've been spending years allready with these quantum theories, en plans to make quantum computers... Millions and millions of dollars (or euro's, or whatever) are spent allready...
And in 3 years we'll have a small beginning..
All this... just to find out the answer is 42 ????
It's largely a matter of words here.
... it is NOT guaranteed to produce the same results as QC, in the general case. Collapsing composite magnetic fields can easily fall into a local minimum energy state, so the concept of "collapse path" becomes relevant as a result of the transition not being instantaneous.
;-)
Their qubits actually *are* entangled, as the various magnetic fields interact --- that's the whole point. Furthermore, the composite magnetic field collapses into its nearest low energy state in constant time. That's actually identical to the zero-time collapse of wave functions as far as complexity theory is concerned.
So although their implementation is somewhat unorthodox for a quantum system, it actually performs a very similar function. However
A very interesting subject. Microwave engineers are going to be in high demand if this takes off.
Forget building bombs. Filesharing is destroying the economy and will soon be classified as cyberterrorism. Just imagine what would happen if the pirates got their hands on a quantum computer. They'd suddenly be able to bittorrent all movies simultaneously. Such powerful technology could destroy civilization as we know it.
Badass Resumes
I don't think they understand the concept of the device. It can't be noisy if no one is there to hear it.
Try following some of these links
Application 1: Optimization
http://www.dwavesys.com/optimization.php
Quantum computers can be used to get approximate solutions to large NP-complete optimization problems much more quickly than the best known methods running on any supercomputer.
Application 2: Quantum Simulation
http://www.dwavesys.com/quantumsimulation.php
Simulation has always been an important part of what conventional computers do. For engineers and scientists, simulation is about asking "what if?" questions without having to actually do it. Today's engineering marvels would not be possible were it not for computer modeling. Everything from the car you drive, to the plane you last flew in, to the building in which you sit, to the computer chip in your PC, are made possible by simulation.
There is an implicit assumption that the tactics used in engineering today will apply to engineering at the nanoscale. The promise of nanotechnology is based on the premise that since everything is built of atoms, if we can manipulate matter on the level of atoms, we can build anything that is physically possible.
Building, however, is only a part of engineering. Just being able to build any given assembly of atoms does not mean that we can predict how it behaves before we build it.
Unfortunately, conventional (non-quantum) computers, no matter how powerful, are very bad at predicting the behaviour of nature at the nanoscale. The quantum properties of matter and energy that make nanotechnology so interesting wreak havok with conventional simulation methods.
Quantum computers are the only known solution to this problem. They are able to directly solve the fundamental equations of quantum mechanics for any physical system. Sufficiently robust quantum computers will be able to create the ultimate virtual reality environment, where products and processes at the level of atoms and molecules can be exactly and effortlessly probed.
ETA were a possibility. They do fit the description "unhappy spaniards" rather well.
Well, they were a possibility (and they certainly are unhappy Spaniards), but you'll recall that the then-president of Spain also made that statement, which immediately turned out to be wrong, and he lost his office because of how wrong he was. There's a little more to it than that (in terms of Spanish politics in general), but there's certainly no question that it was Jihadists trying to change Spain's policy about supporting the take-down of Saddam's regime and the new form of government in Iraq. They made numerous arrests from the cell in Madrid, and a couple of the guys involved killed themselves (with another unused bomb) in their apartment rather than get arrested.
So, there's certainly a wide range of cranky bomb-using organizations out there (including ETA), but that's not who we're most worried about. ETA, by the way, tends to use bombings in more of symbolic way, or as an assasination tool. They're not as big into blowing up people in restaurants, not that that's any excuse for blowing up anything. Regardless, we're more worried about the ones who actually come out and say that their objective is the downfall of western democracy. People willing to "martyr" themselves in the pursuit of a new, globe-spanning caliphate, and who have lots of money to work with... they're a lot more of a threat than Basque separatists, however murderous they may be in their own back yard. ETA, for example, hasn't yet blown up anything in the US because the US has supported Spain's people in combatting them. If they did (attack in the US in an attempt to poison US relations with a European government), they'd be more on the same page with Al Queda. For now, though, that medieval-minded bunch of punks is sort of in a class by itself, and Spain knows that, too. Mind you, Al Queda's train bombings in Madrid were horrible enough (200+ dead later), but they actually botched it. Their intention was for all of the train bombs to go off at the same time in the train station, with the hope of bringing down the station structure on top of everyone inside it. If they'd been a little more careful/lucky, they'd have killed thousands, not hundreds. The Spaniards dodged a bigger bullet on that one.
Don't disappoint your bird dog. Go to the range.
This paper conjectures a new device called a Quantum Chaos Amplifier that magically pull an expremely small signal out of a superpositon. There is also a bit about it not being unitary which is a requirment for quantum circuits. I'm not sure this paper is anything but speculation.
How long before Apple drops x86 and moves to QC architecture?
Ban Engadget - moderators censor comments!
"D-Wave is on track to produce a special-purpose, "noisy" piece of quantum hardware that could solve many of the physical-simulation problems that stump today's computers
All this for Doom 3 and The latest GTA? I mean, they stump my nvdia 5700 graphics card, but I am not about to go over the top.
I think it will be the same, except, instead of mimesweeper, there will be a grid of boxes, complete with cyanide gas canisters and cats, and you have to somehow work out which are alive.
Does this mean that Doom 5 will be called "Doom - the uncertainty principle"
Cue lots of cheesey names like the past: VR this, and 3D that, and Virtua the other.
Quantum Pool
Quantum Golf
Quantum Solitaire.
Oh dear.
Windows or linux first on quantum computing? I mean, it requires a whole new kernel I guess, with module names like 'schroedinger' (for predicting pipeline management in a super-modal setting?) and 'uncertainty' for the RNG.
#hostfile 0.0.0.0 primidi.com 0.0.0.0 www.primidi.com 0.0.0.0 radio.weblogs.com
Look shitcock, it's not hard; the word you're looking for is NO. Heaven save us from self-appointed geniuses who can't even spell beyond the level of a sixth-grader.
Every time you operate quantum computer, Schrödinger kills a kitten. Please think of the kittens.
People who like this sort of sig will find this the sort of sig they like.
It will, however, be ideally suited to solving problems like the infamous traveling-salesman problem . . . D-Wave's chip performs exactly this type of calculation automatically, in seconds.
How many seconds?
Are they claiming that the travelling salesmen problem can be solved in polynomial time? This would be the biggest news to come out of the computer industry since the invention of the transistor. As far as I know, no quantum algorithms exist for solving NP complete problems such as the travelling salesmen problem. Can anyone here enlighten me?
"Or how about being able to solve the hardest math problems we have ever been able to think up as a species in mere seconds?"
The hardest problems are the family of non-computable "Busy Beaver" functions. Rather than being merely very hard, or intractable, they are actually non-computable. Indeed they measure the very boundaries of computation itself, so it's no surprise that they're larger than any other problem. (n) = 4, 6, 13, 4098* and then just keeps accelerating. [* subject to further discoveries]
"PKE is based on the idea that some math problems are harder to solve than to verify. Given a large enough quantum computer, that really is no longer the case."
There is no reason to believe that for any _finite_ Quantum computer, even the fiercest scientific proponents of quantum computing do no more than "suppose" that it might be true, mainstream thought in this area is that BQP is clearly smaller than NP, and therefore some problems which are worse than polynomial time problems on a classical computer are also worse than polynomial time on a quantum computer, despite the fact that they can be verified in polynomial time on both machines.
Grants are often written to cover 3 years. The promises of results in 3 years often reflect the length of the finances. We will probably never hear about this project again.
nothing to see here, move along.
There was this mathematician.
He didn't even work as a mathematician. He was a patent clerk or something.
Never was a very good mathematician.
Didn't do experiments.
I don't believe that relativity garbage either.
ETA were a possibility. They do fit the description "unhappy spaniards" rather well.
That description would certainly make them unhappier still, since their entire reason for existence is the contention that they are not Spanish. They are in fact very unhappy Basques.
I'll believe it when I see it...
You know, that whole quantum thing...
+1 Insightful, -1 Troll. What can I say, I'm an Insightful Troll.
I can finally get an accurate weather forecast?
878659 - yep its prime.
same as the old boss.
gonna be just like what Liebermann Computers pulled.
Quantium Vaporware
Please don't feed the trolls.
But with quantum computers, you could just brute force a solution.
What do you mean by "not random enough?"
Once you start putting any criteria on the number that comes out, doesn't that make it not random anymore?
Exam 4/C again. Maybe I'll do better this time.
I wouldn't trust any page that says something like this:
One of the most interesting categories contains problems that are called NP-complete. These all have the feature that in order to solve the problem all possible solutions must be tried, and the number of possible solutions grows exponentially with the problem size.
"All possible solutions must be tried" is just wrong, and has nothing to do with NP-completeness.
I am not a Quantum Computing expert, but as far as I know there hasn't been much progress in making good quantum algorithms (even approximations) for NP-complete problems. Factoring and discrete log and "hidden subgroup" problems, yes. But these are not likely to be NP-complete.
I'd love to see a quantum computer! That'd be so cool. And it's the only way to implement my perfect chess program.
But even if they do get this thing to succeed, with all the technical issues solved, the business model won't work. They want to sell solutions, not hardware? So company X asks a question, but the answer is only worthwhile if competing company Y can't ask the same question. The resolution is simple, company X will patent the question! Imagine how innovation can be stiffled now -- an order of magnitude better than under the current system. It won't be long before company Y, to preempt other companies from gaining an advantage, will start to patent questions it has no intention of asking! With a little lobbying to conservative politicians, legistation will be passed to outlaw thinking entirely! Is this what we have to look forward to in three years?
Bt seriously, it's an old problem -- social systems can't keep up with technological advancements, and all attempts only make thing worse.
In theory, there's no difference between theory and practice. In practice, there is.
And where do they get the weapons-grade material? And if they can purchase the material, then they can probably afford the actual bombs as well.
...which since I'm guessing you're using Bush's definition of terrorist (aka Arab), would probably be Tel Aviv. oh yeah, Israel rules with an iron fist over there. I think if you were surrounded by a bunch of countries teeming with raving lunatics who have munitions strapped to themselves ready to blow up your grandma, you would want your gov't to be a little heavy handed in dealing with them. -- I slam Islam
It will have six qubits and will be able to simulate an elevator and a traffic light.
I don't know how fast quantum computers are, but if they are faster than classical computers, one could just bute force it.
Also, others have pointed out that quantum computers can do better approximation of approximation problems.
One or two bit at a time quantum computers - sure, we can build those. My hunch, however, is that to build an N bit quantum computer is exp(N) hard. I expect we will eventually have non-trivial quantum computers, but unfortunately the amount of effort to make them will be as much as the effort to build a classical machine that can simulate them. This isn't just nay-saying, unlike the claims that driving at over 30mph would kill humans, my claims are backed up by many physicists, in particular those that don't have a financial interest in quantum computers.
On the other hand, quantum computer science is very interesting as a branch of mathematics and Shor's algorithm for factoring, for example, is a thing of beauty. So I don't blame people bluffing in order to get grant money. And I suppose I don't really hold it against researchers trying to get money out of venture capitalists this way either. Just as long as that money isn't coming out of any funds I'm investing in...
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
We'll, it's kinda cheating. The algorithm is STILL NP, but in quantum computing we can run all paths in parallel so we solve all possible combinaisons at once, which becomes polynomial. However, we have no way of finding the good answer at 100%.
See, the problem in quantum computing is that you can have multiple states in parallel, but you can only 'read' one and lose all other states. This is like having a book with 400 pages, but when you open it, it selects (with a certain probability) a specific page and the whole book becomes that page, you lose all other pages.
We need to make the system converge/interfere in a meaningful way to the correct solution, and in its own way, this is the challenge of QC. In the end, if our algorithm works, we will be able to get the answer to the travelling salesman problem with a probability (depending how good our convergence is). Just like our book above, we need to increase the chance of opening the book on the page with the correct solution. This is non-trivial.
The thing is, the 'weight' of that convergence/meaningful interference, in problems like the travelling salesman, is usually as high as the time it takes to run the normal algorithm in classical computing. We end up not having much gains, it's not that fast. So, yes, if they are that good, we can solve the travelling salesman dilema in seconds... with a certain, probably very low %. Probably even a meaningless %.
However, in problems like finding if a function is unanimous(f(x)=0 or f(x)=1 for all x) or balanced (f(x)=0 for exactly half of x and f(x)=1 for exactly the other half of x) could be done in quantum computer with no errors and very fast, while in classical computing you'd have to try each value of x. If you however allow a certain % of error, the classical way with a stochastic computer would work best (test only a certain pool of value).
Yes, the brute force method may complete faster on a quantum computer (or a 5ghz machine that comes out in a couple of years,) but the question is whether or not we can solve the travelling salesman problem in a non-exponential way. This means that the execution time will not increase exponentially with the size of the input.
I've already had a quantum computer for a while. Of course, it only works one bit at a time and needs a lot of cats. Here's a picture of it: http://www.math.sunysb.edu/~scott/Quantum/schrodin ger.png
quantum computers will be able to find a cure for AIDS, fold all possible protien folds at once to cure cancer, prove the non-existence of God, and bring world peace.
the new era of humanity is upon us
What if i overclock that computer! Is there a chance it will time warp?
--Quantum leap possiblities--
... it will play Duke Nukem Forever. The only caveat being that you will be able to see where you are and how fast you are getting there but not both at the same time.
...oh yes, also OS X will feel much snappier :-)
A cynic is what an idealist calls a realist...
It was announced that this technology would be the muscle behind Infinitium Labs new console codenamed "Give me your money you dumb suckers!".
When questioned over the length of the name, Tim said "Piss off and give me your investment money!"
[[[[Taken from the "I'll believe it when I see it" file]]]]
*END TRANSMISSION*
They'd suddenly be able to bittorrent all movies simultaneously.
Yeah, until someone tries to watch one, and then suddenly everybody has only that movie...
I believe posters are recognized by their sig. So I made one.
and, as far as I know, you will have to pay the rights for EACH, and the royalties for all the 5MB-sequences already deposed.
but in quantum computing we can run all paths in parallel so we solve all possible combinaisons at once, which becomes polynomial.
This is parially true, and is exploited in Shor's factoring algorithm. But note that Shor's algorithm would not work if it relied only on doing brute force calculations in parallel. Shor's algorithm works because it reduces the problem of factorization to a series of steps that can be done in parallel, then passed through the QFT to yeild the correct result with high probability. You could not, on a quantum computer, factor a large number by trying all combinations of numbers in parallel, because you would have no way (at least no way that is known) to arrive at the answer with high probability...you would just get some random answer as you described in your book analogy.
The point here is that no one has been able to reduce an NP problem to a series of steps that can be run in parallel on a quantum computer to yield an answer with high probability. If you can do this, you will be very rich and famous
In 3.5 years Apple will announce their switch to quantum processor. Steve Jobs will claim that this will again place Apple at the top of the performance heap.
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
I liked the idea of them using this as a tool for designing other computers...
As far as i'm aware it's applied mathematicians and theoretical physicists that will drive QC. Not because the technology is not there but because there is no usefull things to do on a quantum computer appart from some cryptography and large database search algorythms.
These are not a large market (say $100m a year international for this kind of thing) and so the main thrust has been in therotical physics to make algorythyms that actually work on QC's to better effect then standard sillicon.
This has been the case since about 2001.
Who else thinks this story should be here
I will believe this when it comes from an engineer.
But if you're only solving Travelling salesman problems of a certain size, then that isn't a concern.
Yes, the plans for a lawsuit were rather revolting. I don't think it was ever carried out though and I sincerely hope that Google didn't settle out of court. Obviously there's too much being contested over ridiculous rights these days.
Will it play Ogg?
Lets say that the certain size is on the order of 10 ^ 10000000000000000000000000000000000.
If we are merely concerning ourselves with travelling salesman problems of a small, trivial size, then we wouldn't be having this discussion.
Well if it can be used to accurately fold proteins, it'll definitely be worth it.
---If you can't trust a nerd, who can you trust?
A quantum computer is probably our best bet to create artificial intelligence. I see AI as simply computing where 2 + 2 doesn't always equal 4. With the expected computing inconsistencies that such computer will produce, we could see the emergence of AI. Or maybe we should simply call it artificial consciousness, as capable of making stupid decisions as its organic creators.
I'm a sci-fi vegan: I don't want the aliens to think we have as much right to live as the fried chickens we eat.
Were's the f*cking http://web.mit.edu/adorai/timetraveler/party??
:'(
Hmmm...seems my QCPod misunderstood the date (May 7, 2005, 10:00pm EDT (08 May 2005 02:00:00 UTC) Hell!! Posting in slashdot from inside a PentiumIII... Arghhhhhhhhhh
The exact solution can only be guaranteed in general by enumeration for NP-complete problems. This means that worst case all possible solutions must be tried. Can you explain why you think this is incorrect?
Would 1,000 cities be a small, trivial size? It would take less than 10^300 attempts.
You are missing the boat on this one. The point isn't whether or not we can solve a small trivial problem. The point is if it is possible to solve, in polynomial time, a problem in which the complexity of the best known algorithm increases exponentially with the size of the input.
Instead of just cities, lets use network nodes between cities. Lets say I wanted to know the fastest (in terms of bandwith or distance or whatever, assume some cost of each link,) way to route packets through every major city in the world. Think about all of the combinations of routers you could potentially use. (Do a traceroute for some short distance like 20 miles and see how many routers your packets hit.) This real world problem could take a lifetime (or much longer) to solve on today's computers.
But the most important implication is that since the travelling salesman problem is known to be NP complete, Then a polynomial time solution would mean a polynomial time solution to ALL of the problems known to be NP complete (This set of problems is large and includes many interesting problems, Google NP complete to get an idea of what could be accomplished here.)
Enumeration is not the most efficient way to solve, e.g., SAT, which is NP-complete.
For example, if there is a certain clause (x1 OR x2 OR x3) in a SAT instance, I have no need to "try" any assignment that sets x1=x2=x3=false. There are exponentially many such assignments; I can skip them all.
This algorithm remains exponential-time, but it skips over one-eighth of all assignments.
Quantum computers do not run regular apps- which is why we need the algorithms. they also need a regular computer to be able to feed in the apps. you also need an NMR machine or something similar to actually see what's going on- which will make it decohere. and all this is assuming it doesn't decohere by itself- which so much as a passing photon can make it do. unless D Wave have managed to solve al of this and more, 3 years is awfully optimistic. try 15, and maybe they will be able to factor the number 20. and even then, it will still give 8, 12 and 16 as answers.
Kids! Bringing about Armageddon can be dangerous. Do not attempt it in your home!
Whose point? To get a problem of the size that you gave [10^(10^34)] would require 10^32 nodes. What kind of problem would require this? And yes, I've heard of NP Completeness.
You may have heard of NP completeness, but you obviously have no idea what it is.
Why would you want to route packets through every city? Why not just do it for each pair of cities?
Actually, that is not the Traveling-Salesman problem, but the shortest (fastest) path problem, which is polynomial. Even solving for every pair of nodes, it's still polynomial.
I do know what it is. I just don't kneel down before it.