IBM reports quantum computing advance
According to a press release (19 December 2001), researchers at IBM's Almaden Research Center have performed the world's most complicated quantum-computer calculation to date. They used a container full of billions of custom-designed molecules to create a seven-qubit quantum computer that solved a simple version of the numerical factoring problem at the heart of many of today's data-security cryptographic systems. Reporting their work in the 20 December 2001 issue of Nature, the team says they have provided the first demonstration of "Shor's Algorithm" — a method developed in 1994 by AT&T scientist Peter Shor for using a quantum computer to find a number's factors. Today, factoring a large number is so difficult for conventional computers — yet so simple to verify — that it is used by many cryptographic methods to protect data.\
The simplest meaningful instance of Shor's Algorithm is finding the factors of the number 15, which requires a seven-qubit quantum computer. IBM chemists designed and made a new molecule that has seven nuclear spins — the nuclei of five fluorine and two carbon atoms — which can interact with each other as qubits, be programmed by radio frequency pulses and be detected by nuclear magnetic resonance (NMR) instruments similar to those commonly used in hospitals and chemistry labs. The IBM scientists controlled a vial of a billion billion (1018) of these molecules so they executed Shor's algorithm and correctly identified 3 and 5 as the factors of 15. "Although the answer may appear to be trivial, the unprecedented control required over the seven spins during the calculation made this the most complex quantum computation performed to date," a member of the research team said.
Additional coverage of the research can be found in the New York Times and an article from the San Francisco Chronicle reprinted on the Small Times website.
December 20th, 2001 at 9:35 AM
Quantum Computing vs. Quantum Cryptography
They say a forty atom quantum computer can rival the power of our biggest supercomputers. And a thousand qubit quantum computer can quickly solve all the problems currently considered intractible by computer science. Cryptograpy based on factoring huge numbers appears doomed.
Or is it? Researchers in Cambridge, UK are working on quantum cryptography which may thwart QC's ability to break codes based on factoring.
December 21st, 2001 at 12:31 AM
Maybe it's not as good or bad as all that
As I understand it (and I'm prepared to admit that my understanding may be a bit shakey), what quantum computation buys you is (effectively) a reduction in the order of computational complexity of certain algorithms (say, a reduction from O(e^N) to O(N), though I don't know that that's the particular reduction we're talking about). For those of us who eat CPU cycles like candy, that can only be good news. However, the last I heard, this reduction was only applicable to certain classes of algorithms and not to algorithms in general. It may be, for example, that factoring falls to QC but other problems do not. Further, the ability to compute at a higher order of complexity is potentially a sword that cuts both ways — e.g., it may be feasible to develop new encryption algorithms that are O(e^N) given a quantum CPU to encrypt with.
The so-called quantum cryptography stuff is not encryption in the mathematical sense but rather a physical technique for constructing a perfectly tamper-evident communications medium. This may be valid and important technology in its own right, but I don't know that it addresses the computational issues introduced by quantum computation. (I'm also curious how one might actually use quantum cryptography in real communications systems. Essentially what they are constructing is a channel so delicate that anything that could perceive the signal will destroy the signal. However, traditional transmission media suffer signal loss all the time anyhow — that's why we put in error correction. It strikes me that any kind of error correction techniques applied to a quantum cryptographic channel will eliminate its security, but if you don't have error correction you won't be able to communicate reliably. Maybe those guys have an answer to this; goodness knows they've thought about it more than I have, but I've never heard this issue raised before.)