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."
But once the molecules are put together and they can control them properly, then nothing really stops it. That is why they say that a fundamental change in cryptography is on the horizon.
Random Musings
even though we can factor 15 == 3*5, we are still far away from useful quantum computer applications. the problem is that the coherence time of the atoms is fairly short and only O(10^3) computations can be performed before the system is decoherent. there are many interesting (but rather technical) papers about this subject and how to build quantum computers with quantum dots or any other solid state devices. you can get a glimpse of what is going on at the front of physics at http://xxx.lanl.gov/. just search for quantum+computing...
From the Yahoo article:
;-)
"Previously the largest computer IBM had built was based on five atoms."
So what about the 2 ton behemoths everyone's been buying for years?
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
And I thought my 4-bit key's were safe!
Damn the relentless progress of computing!
The technique used here (NMR) is probably the best understood way of doing quantum computing (a lot of the basics are dragged straight out of medical imaging technology). Unfortunately it has a very fundamental limitation: the initialisation phase scales exponentially. Everything else is practical, but for every qubit you add you need to add exponentially more molecules to your system. Since you start off with a "billion billion" molecules you get a good head start, but systems much beyond seven qubits become very difficult and anything practical is impossible.
Of course almost all current quantum computing schemes have fatal flaws and NMR is well ahead of everyone else (with the possible exception of ion trapping). However in most other schemes the flaws aren't fundamental (just really, really, difficult to fix).
Disclosure: I have worked on a competing quantum computing scheme (neutral atoms). It's crap too.
If you put a cat inside this computer, will it die?
--- -- - -
Give me LIBERTY, or give me a check.
It's also discussed at news.com .
Looking for any old 8-bit Heathkit/Zenith software/hardware - http://heathkit.garlanger.com
Looks like the number of qbits available in a quantum computer is doubling every 18 months. The article notes the 2 qbit computer was built in 1998, the 4 qbit unit in August 2000 and now a 7 qbit computer in December 2001....they've still got another couple of months to get the 8th qbit....
7 Qbits already? That's great! No one should ever need more than 640 Qbits.
Sheesh, evil *and* a jerk. -- Jade
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
7 qubits!?!? Sheesh, Noah's Ark was 300 qubits long, by 50 wide, by 30 high. And seven is supposed to be impressive thousands of years later?
--
"Outlook not so good." That magic 8-ball knows everything! I'll ask about Exchange Server next.
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.
You're right that the NSA knew about Differential Cryptanalysis years before anyone. I extrapolated this largely using the same facts - but if you read _AC_ carefully they openly acknowledge this.
But you're wrong in the fact that DES IS resistant to DC. The bit S-box design the NSA gave IBM are designed to make it STRONGER against DC NOT weaker.
"As in choosing the key length , another of the NSA'a design criteria was based on making the algorithm [DES] resistant to differential cryptanalysis..." _AC_ first edition Schneier page 238
If you want to bust the NSA's chops complain that they made the key length go from 128 to (effectively) 56 bits. Now that hurt...
=tkk
Bill Gates - Creationist?!?
The core question is: Can a real, working quantum computer be built in secrecy?
IMHO, it is very unlikely. It has to do with how science works. A few things can pop out straight from a brilliant idea, and can be implemented based on that idea alone. This is, however, very, very uncommon. Even the most brilliant minds needs feedback from their peers to get anywhere. You need critisism, even strong opposition, to fine-tune your ideas and your arguments. This is what the greater scientific community provides.
In closed projects, even if you hire the best minds, you'll get inbreed, you will not get the same level of critisism, and soon you will most probably paint yourself into a corner.
So, while there are examples of projects that have been developed in secrecy that actually work well, most real science has to be done in the open.
Arguably, the most advanced project that we know of that was conducted in secrecy is the Manhattan project. However, building a nuclear bomb wasn't really that difficult. All the basic science was well understood in 1941, it was just engineering left. The brilliant minds found it rather boring. It was completed, and it was kept secret because of the war, there existed very strong reasons for the people who developed it to keep it secret. Hardly any such reasons exist today. A quantum computer will be so important to science and technology, I don't think you can have a larger group of brilliant minds keep it secret for very long. They would want to have the advancement of science going, and beside, they want the nobel prize.
I'm not really frightened. I'd really like to see quantum computers. Yeah, it will make PKI as we know it obsolote, and it really needs adressing fast. I'm not aware of any algoritms that can make reasonably strong encryption on a classical computer that can withstand an attack from a quantum computer, but we'll need that to be reasonably safe while we're waiting for quantum computers to be widespread enough for everybody to use. Anybody know of efforts in this regard?
Employee of Inrupt, Project Release Manager and Community Manager for Solid
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.