Slashdot Mirror
IBM Builds A Limited Quantum Computer
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."
My brother found this for me not too long ago. The math involved can get rather intense, but I think it 's worth pointing out:
An Introduction to to Quantum Computing for Non-Physicists - Available in PDF, PostScript, and others.
If you do a google search, you probably can find it elsewhere, also.
--GFish4
Los Alamos built a three-qubit quantum computer a while back. I don't have references, except a few mentions in other news articles. Sorry.
2 1, 00.html
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
It's also discussed at news.com .
Looking for any old 8-bit Heathkit/Zenith software/hardware - http://heathkit.garlanger.com
Start here: http://www.qubit.org/
As below, so above and beyond, I imagine drawn beyond the lines of reason. Push the envelope. Watch it bend.
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.
"You call it a new way of thinking; I call it regression to ignorance!" -- Operation Ivy
Quantum computing could conceivably obsolete public key (asymmetric) cryptography. However it doesn't break conventional cryptography. A sufficiently strong quantum computer can turn an O(f(n)) computation into O(f(sqrt(n)) but that's all. For example, it could break a 56-bit key in 2**28 steps instead of 2**56 steps. That means 128-bit keys could conceivably be broken by quantum computers (in 2**64 steps). However, by doubling the key length (say to 256 bits) you get the security against quantum computers that you now get against conventional computers.
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.
Actually one of the flaws in NMR quantum computation is that the signal strength used for measurement decreases exponetially with the addition of more qubits. That's pretty fundamental.
:wq
You weren't paying attention. Shor's(sic) algorithm was discovered by AT&T's engineer by the same name in 1994!
You can't legislate goodness. Let each to his own destiny, by will of his freely made choices.
then either browse at 2+
or goto a better site.
Just some specific problems like factoring.
For GENERAL brute force search type problems
the speedup is as I described. See the articles
at qubit.org for more info.
Actually, Shor's algorithm takes a O(e^N) algorithm on a classical computer (factoring into primes) and reduces it to a O(N^2)algorithm, so not only does it reduce an exponetial order algorithm to a polynomial algorithm, which is already achieving the holy grail of computing computationally hard problems, but does so in spades. Essentially, if QC's can scale to the number of bits required and operate at any decent clock speed (more on this in a bit) then RSA will go the way of the dodo. So will every other encryption scheme that I know of that is based on a computationally hard to compute key that a QC algorithm can be written for. (BTW, Shor also created an effcient O(N^4) algorithm for the discreet log, which is also used in some encryption schemes, or so I am told).
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:)
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
The big whoha is that factoring numbers is computationally difficult. Public Key encryption
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.
It doesn't. The thing about Shor's algorithm is that, as initially written up, it factors an L bit number on a 3L q-bit quantum computer in polynomial time (O(L^3), I think). Obviously IBM have tweaked it a bit to get down from 12 (3*4) to 7 qbits, but even so, going from 4 bits to say 1024 would require 256 times as many qbits (the hard part) and 256^3= 16 million times as much time (not a big problem).
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.
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
Vanity of vanities, all is vanity...