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

if a quantum computer takes the same time

to factor 15 as it does the product of two 128 bit primes, what's stopping this computer from breaking current asymmetric crypto right now?

Re:if a quantum computer takes the same time

Mainly because of the number of molecules it takes to perform that feat. "IBM chemists designed and made a new molecule that has seven nuclear spins" - exactly enough to solve the simple factor. You need many more spins than that to perform complex calculations.

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.

Re:if a quantum computer takes the same time

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.

Frightening implications

If a private sector company has been able to climb the steep hill that is quantum computing, how far has the US govt been able to get with their nearly unlimited budget?

It has been widely acknowledged that such agencies as the NSA have been at least a decade or more ahead of the private sector. The first govt to get a working quantum computer not only has unbreakable encryption, they are able to read any code of foreign nations. The stakes are incredible!

Soon, they will be watching all of us. Better read 1984 quickly my fellow citizens!

Re:Frightening implications

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're exactly right and wrong!

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

Re:Frightening implications

This is an interesting point. We discussed this to some length at the International Conference for Physics Students this summer.

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?

Almost There

Assuming that during the 50's era, we were just getting electronics on a large scale to do the same thing, I give this tech about 20-30 years to really take off and become the norm.

similar has been done before

2 years back i heard someone(i belive it was bruse schneir), say that the NSA or los alamos had built a quanum computer, and it could factor the number 7, down to 1 and 7, not to hard. but still an impressive feat.

OS

Now all I need to do is write a proprietary OS for it, and convince IBM to let me keep the rights!

I'm thinking of calling my company "Quantumsoft"

And my software would be able to slow the quantum computer to a crawl!

Sounds dangerous...

So, what happens if you ask it to factor a prime? Does it explode? ;-)

Could quantum computing ever become general purpos

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,

If they had to hand-craft a molecule to factor the number 15, it would seem that quantum computing would have to be very specialized. Do they have any schemes for creating a general purpose quantum CPU?

still a long way to go...

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/ [lanl.gov]. just search for quantum+computing...

anyone got a patch...

... for GnuPG to have 100000 bit keys? Quickly?

but...

What kind of tea did they use????

IBM's largest computer ever

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? ;-)

Re:IBM's largest computer ever

So what about the 2 ton behemoths everyone's been buying for years? ;-)

Big fucking atoms...

An Introduction...

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 [lanl.gov] - Available in PDF, PostScript, and others.

If you do a google search, you probably can find it elsewhere, also.

--GFish4

Crud!

And I thought my 4-bit key's were safe!
Damn the relentless progress of computing!

My boss says ...

... "They should have asked me to do it. They could
have saved a lot of money."

explain

i read somethin' about this in wired
im pretty stupid though and allthough i understand the potential capabilities
i dont understand the process and theory
anyone explain?

Question

I'm not a computer scientist, so for us lay people interested in cryptography, which methods could this compromise?

I am guessing it would only be those which use factoring large numbers as their "hard" problem. Right? Obviously RSA style public key based encryption is in danger, but that just means I need to find a secure channel to exchange keys.

What implications does this have for things like IDEA or even Xoring with a big chunk of random data?

Unfortunately NMR quantum computing has limits

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.

Re:Unfortunately NMR quantum computing has limits

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.

Meow

If you put a cat inside this computer, will it die?

Someones gotta say it!

Could you imagine a beowulf cluster of these things!

That's easy!

Well shucks, I was able to factor 15 into 5 x 3 when I was in 3rd grade! Maybe I'm "The One"!!

Another article at News.com

It's also discussed at news.com [cnet.com].

You Heard It Here First...

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

Re:You Heard It Here First...

please tell us you heard some important dude at IBM claim this growth patern first....

because I'm not looking forward to calling it cybrpnk's law

Almost there!

7 Qbits already? That's great! No one should ever need more than 640 Qbits.

In other news...

... builds an unlimited quantum computer.

Time to call the DMCA

I based my personal encryption technology on mutiplying the two primes 3 and 5. Now that IBM has broken my encryption, I'm going to go Adobe on their asses!

The End of Asymmetric Key Distribution

As probably most people here realize, the advent of sufficiently strong quantum computers renders obsolete every encryption scheme. Except, of course, then Verdam cypher or One Time Pad.

At JPL, among, there is a group working on quantum key distribution. The aim is to have entanged photons distributed at the same rate (or almost the same rate) as the data, and to use this as a crypto key that is totally unbreakable. Untappable, unbreakable, impervious.

Doesn't it strike anyone as strange and cool that quantum computers and quantum key distribution are coming to fruition at almost exactly the same time?

muerte

In other news...

<insert big wig company name> builds the first unlimited quantum computer.

Downsides....

The downsides of the possible onset of quantum computers are:

(1) Any government agent could crack your encryption...after all, a quantum computer could crack a fifteen thousand letter password in like two seconds. (of course, not for PGP, since it is based on unsolvable algaebraic formuli)

(2) This means that programmers will take this as an excuse to write even sloppier code and put in even more unnecessary features that we don't want and don't need.

Re:Downsides....

(1) Any government agent could crack your encryption...after all, a quantum computer could crack a fifteen thousand letter password in like two seconds. (of course, not for PGP, since it is based on unsolvable algaebraic formuli)

How is it based on unsolvable algebra? It's based on HARD algebra. The only reason public key encryption is currently secure is that it is much easier to multiply than factor. It may take a few seconds to encypt something but, without the private key, it takes a long time to crack on *current computers*. It *can* be done given enought grunt, see distributed.net [distributed.net]. These Quantum computers (or their successors) can theoretically crack an encryptred message in about the same time as if you had the private key. It makes PGP, GPG, SSH, SSL etc (ie. all of them) about as secure as rot-13.

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.

Old news

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?

What this really means

We need to begin considering a form of cryptography that's relatively immune to quantum computing technology!

I dearly love SSH, but if it's based on inherently transparent (to quantum computers) mathematics, it's worthless - perhaps worse, since I trust it.

We need to begin considering this problem NOW, before the privacy of just about everybody is opened up to the whim of somebody with enough money to buy a quantum computer!

There will definitely be, as Quantum computing hits mainstream in the next 5-15 years, a co-existence period - like twilight, the period of greatest danger, when the world of computing is based neither entirely on binary or quantum systems - and we're heading for that with momumental speed.

How long?

Ok place your bets, how long until NetBSD is running on this thing?

Stockpiling emails

Let's assume that at some point in the next couple decades, an evesdropper with a sufficiently large budget can build a device that will efficiently crack factoring-based keys.

Unfortunately, that means people using factoring-based keys are in trouble today, because an adversary with a sufficiently large budget (and sufficent access to certain routers) could stockpile a rather large portion of Internet traffic for cracking at such time that it becomes feasible to do so.

Evidence and paranoia leads one to suspect certain parties do evesdrop on a certain fraction of email, particularly email sent across international cables. If such email is already being filtered for certain keywords, how much harder is it to filter it for apparently encrypted email and shelve it for later use?

Stuff like this makes me wonder...

...why some sciences seem to be so lucky and others so cursed. We've been spinning our wheels on fusion power seemingly forever, and storage battery technology inches along, and we're perpetually awaiting our personal jetpacks (well, I am). But every crazy idea that comes along in computers just works.

Very strange.

Very impressive

That's a very impressive result. IBM Almaden does some great physics.

A friend of mine there says their employee evaluation system has three ratings: "OK", "Not OK", and "Nobel Prize". He's only partly kidding; they have several Nobel laureates on staff.

I want me one of these

I want me one of thoes. Seti at Home, Beowulf cluster, hack on perl.

Yea!!!!

Effect on Magnetism?

I've kept a slight eye on quantum computing for a few years now, but only thought of this question until now. If an electron's spin determines it's magnetic moment (right?), and an electron can have its spin in superposition of up and down, then what does this do to the magnetic moment?

I would think it would be cancelled out, but can someon give me a more definitive answer?

factors

wht is the big whoha! avout factoring a number? I don't understand this.

Imagine...

...a beowulf cluster of these ;)

(Sorry, someone had to say it!)

4-bit RSA is broken!

This has been in my signature file for quite some time:

Well, there's a quantum computer that can factor 15, so those of you using 4-bit RSA should worry.

-- Bruce Schneier

A new logic

Does this mean we now have tha AND, OR, XOR, NOR and MABY gates?

It's not the end of the crypto world...

The advent of quantum technology allows us to encrypt stuff in newer and cooler and more secure ways. For instance, you can encrypt something that allows a reciever to read the message once and try to decrypt it, and if that didn't work, too bad! I don't remember the details well enough to get into a technical explanation here, but Simon Singh's "The Code Book" explains some of it at the end (that's where I read it). It has something to do with photons and spins :)

And I do realize that if "old fashioned" crypto is cracked, old messages can be read, but if you've sent something that was *that* secret, it *must* have been illegal ;)

Hacker at heart

IBM announcement - in history section:
"But in 1994, Peter Shor of AT&T Research described a specific quantum algorithm for factoring large numbers exponentially faster than conventional computers -- fast enough to defeat the security of many public-key cryptosystems. The potential of Shor's algorithm stimulated many scientists to work toward realizing the quantum computers' potential. Significant progress has been made in recent years by numerous research groups around the world."

Maybe Magic Lantern isn't needed, and maybe the feds should be more concerned about quantum scientist as the next great public threat? Lets' see now... Hacker used to be a positive connotation.....how to turn Quantum into a negitive connotation...or is ther another name by which these scientists go by?

Super Quantum Computer

Just out of interest, does anybody know:

given that a quantum computer could factorise a number N into factors a1, a2, a3,...etc in a defined time, we can therefore tell whether N is prime by seeing if it returns a1=1, a2=N.

Would it be possible to build a 'super' quantum computer which checks simultaneously all numbers from 0 -> 2^n (where n is the number of qbits) and returns only those which are prime.

In other words, you would be carrying out 2^n computations simultaneously, each of which is comprised of 2^n computations ?

Achtung! Halt!

"phr1 writes "IBM has announced and Yahoo has noted that the first working implementation of Shor's factoring algorithm."

[grammarnazi]

Apparently, phr1 does not need to use.

Complete sentences. =P

Either that or get rid of the "that".

[clicks jackboots, /grammarnazi]

-Kasreyn

Okay, I'm no expert on quantum anything but....

I've read IBM's articls and here is how I imagine a conversation between myself and IBM would go:

me: So, what does a quantum computer do?

IBM: Someday, we will be able to solve problems that are so complex that even the most powerful supercomputers working for millions of years can't calculate the answers.

me: Wow, what can you do so far?

IBM: We can show that 15 = 3 X 5

me: uh, I think you boys need to calm down a little.....