IBM Builds A Limited Quantum Computer 317
phr1 writes "IBM has announced and Yahoo has noted that the first working implementation of Shor's
factoring algorithm. Using NMR techniques they built a seven-qubit
quantum computer and factored the number 15 into the factors 3 and 5.
This is by far the most complicated quantum computation ever done.
It's quite an amazing feat--many people thought quantum computing
was just a theoretical curiosity and Shor's algorithm could never
be implemented in practice."
An Introduction... (Score:5, Informative)
An Introduction to to Quantum Computing for Non-Physicists [lanl.gov] - Available in PDF, PostScript, and others.
If you do a google search, you probably can find it elsewhere, also.
--GFish4
Los Alamos and "federal researchers" (Score:3, Informative)
But in March of 2000, a group claimed to have built a 7-qubit quantum computer. It's based on some different techniques than previously used, but the researcher said that the techniques can't go past 15 qubits. Check it out at:
http://www.wired.com/news/technology/0,1282,351
Another article at News.com (Score:4, Informative)
Re:explain (Score:2, Informative)
Start here: http://www.qubit.org/
Re:Frightening implications (Score:5, Informative)
While I have also often heard stories of the NSA having much more advanced equipment and techniques than the private sector, or at least than the non-classified private sector, in the case of quantum computing this is unlikely. First, it's a relatively new subject. Shore's algorithm, for example, was only discovered in the 80's. There really hasn't been enough time for them to get so far ahead. Second, the NSA is full mostly of mathematicians and computer scientsts, not physicists, so they really don't have the right staff for that. Third, most of the academic research is funded by the NSA.
Finally, though it's hard to say exactly how far this technology is from being useful (or alternately the probability that it will EVER be useful), it is probably safe to say it will be quite a while from now. Moreover, it is probably also safe to say that it only gets harder from here. Larger computations will involve the same problems as these only on larger scales plus a whole new, tougher, slew of problems that these avoid. These are chiefly quantum decoherence and entangling large numbers of quantum states.
Quantum decoherence is the loss of the special quantum information (quantum phase relations) that allows quantum computers to do their funky magic. This happens over time in any system that has any interaction with the outside world. I think these small calculations largely avoid this problem because they are reasonably fast. Larger ones involve more steps and thus will run up against these problems. Some error correcting quantum codes have been developed, but these involve even more qubits, which exaserbates the other problems, and are still largely in the formative stages.
The other big hurdle is entangling much larger numbers of particles in one state. These take advantage of the interactions between different nuclei in the same molecule. Once you need many more qubits, you will need to come up with a more general scheme for entangling the quantum states, because it's unlikely that you'll be able to engineer a molicule for the purpose. Also, the bigger you make your system, the more strongly it interacts with the outside world and the worse decoherence becomes....Life's a bitch, ain't it?
So, I think this is really exciting and quantum computers have great promise, but I don't expect to have a quantum co-processor in my PC any time soon, nor do I really think it's likely that the NSA has a quantum supercomputer sitting in the back room decrypting my credit card information.
not true (Score:3, Informative)
Re:Downsides.... (Score:4, Informative)
If we don't get a more secure encryption system out before the real quantum big guns come out, e-commerce etc is basically stuffed.
Re:Unfortunately NMR quantum computing has limits (Score:4, Informative)
Re:Frightening implications (Score:2, Informative)
Re:not true (Score:2, Informative)
Re:You make me sick! (Score:1, Informative)
or goto a better site.
Re:not in general (Score:3, Informative)
For GENERAL brute force search type problems
the speedup is as I described. See the articles
at qubit.org for more info.
Actually it is true (Score:2, Informative)
Granted I am not a security/encrytion expert, so your statement about this only being effective for assymetric encrytion schemes may be correct if conventially encryption is not based on a hard key, but I thought that all encryption was based on hard keys (BTW, isn't cryptography the creation of a code to hide/diguise the data, as opposed to encrypting it with a function?).
With regard to "clock" speed (There is no fundamental reason a QC needs to be clocked, but for the sake of simplicity let's say it is), NMR states are, I think, stable on the order of milliseconds, so maybe the computer could "clock" several hundred computations per second. It would still take awhile to do several million comps, or about how many comps will be required to factor something on the order of 10^25 with Shor's algorithm, but timewise that's on the order of months, not the known age of the universe like it would be for a regular computer (figures are from memory, and are meant to illustrate the orders of magnitude involved, not necessarily be completely accurate).
Granted this is all a guesstimate, but I think a pretty conservative one.
Someone else quoted rate of ~ O(10^3) computations before decoherence. A QC is probablistic, which means that you run it over and over under an interation produces the correct result. The chance of getting an incorrect answer decreases with each iteration. Shor's algorithm takes either 3 or 4 computations (defined in a QC as a evolution of the wave state) per iteration. I may be a little off here, it's been awhile, but it's definitely around that so if that quote is acurrate, decoherence is no problem, at least for the quoted setup. It also, assuming a decoherence time on the order of ms, appears to be faster than my above guess.
Essentially, even if QC's can't crack various keys in realtime, they could make key generation/distribution a real pain in the ass and essentially end the era of uncrackable encryption (unless of course it is quantum encryption which is in theory uncrackable, but I know alot less about that)
Does anyone have any data on how many comps/sec various qubit models can handle? I'd like to see if my guess was close:)
Correction Re:Actually it is true (Score:1, Informative)
In fact, this is wrong (and yes, I wrote the original post, login not working, to late to correct, etc.). There are many comps in Shor's algorithm, and the wave function does need to remain coherent through them all. However, these comps are based on quantum logic, and do not address the underlying physicall system directly, and there you may be able to make things even faster. For example, in Shor's algorithm, randomizing the state is O(N) time, where in the real world you would zap your system with the right radiation to get the same step in a singel transformation of state.
Sorry about that, it's been awhile
Re:factors (Score:2, Informative)
is based upon the fact that it is very easy to randomly pick some prime numbers and multiply them together to get an answer. The number that is produced can only be produced by multiplication of those two numbers, so there is only one pair of numbers that can be deduced by factorisation. Now, there is no easy way to determine the factors of a number, the only way is to use a brute force approach. That takes time, due to the large amount of time needed, it makes this ideal for implementation in a cryptographic system, and guess what? That's what most public key systems use. So it makes it possible for somebody to totally undermine all the existing e-commerce infrastructure and grep all of your passwords and credit card numbers and al-Queda arms shipments.
Re:if a quantum computer takes the same time (Score:4, Informative)
In contrast existing non-quantum techniques take O(e((log L)^(2/3)*(L)^(1/3))) time on a computer of fixed word size. To go from 4 bits to 1024 increases the run time by a factor of something like 10^18.
More to the point, on quantum computers, the race between prime finding, and so key pair generation, and factoring and so code-breaking is much less uneven.
Re:Frightening implications (Score:2, Informative)
Most meaningful reasearch, by any standard you care to name (dollars spent, papers written, patents granted, etc), comes from Universities. In the US, almost all industrial basic research (IBM being a notable exception) has been eliminated in the names of quarterly profits. The problem is that the return on basic research doesn't arrive for 5-10 years and most companies don't look beyond next quarters balance sheet.
And, since you brought it up, Bell Labs no longer exists. When AT&T split itself up, the old Bell Labs became Lucent Corporation. The research parts of Lucent pretty much ceased to exist as of the recent restructuring where research was split up between Lucent, Agere, and Avaya.
And, as someone else pointed out, DARPA is only for the U.S. military and is a primarily funding agency, not a research lab. U.S. civilian research is funded largely by DOE, NSF, and NIH.
-JS