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