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

Comments

if a quantum computer takes the same time

[xercist]

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

[tomstdenis]

Well for starters the time will not be the same. Also the complexity of factoring a 256 bit number is amazingly higher than factoring a 4-bit number.

Tom

Re:if a quantum computer takes the same time

[Anonymous Coward]

The NSA probably already has a tie with quantum computer developers. Maybe our use of crypto algorithms have already been broken...

Re:if a quantum computer takes the same time

[Anml4ixoye]

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

[SethV1]

Moin!

-ironic- Damn does this mean i have to use numbers greater than 5 as p,q in my implementation of RSA? Damn, even encoding my files with a 8-Bit key will mean milliseconds of waiting in front of my K7. I can't stand waiting -/ironic-

No, to be onest i do not think the coherence length will be raised to those needed for a 256-QBit QC within a decade. Until then we will use longer keys. I think that - if ever - the race Keylength vs. QC will be going on 20 years at least.

CU Seth

Re:if a quantum computer takes the same time

[stevelinton]

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.

Re:if a quantum computer takes the same time

[anothergene]

Its the old battle of cryptogropher vs. code breaker. Once they use a new tech to break existing codes, it kinda pushes the coders to come up with something new to keep the breakers busy and confsued.

There was an article a while back about a single photon LED . This makes quantum encrytion a reality. Once we've gotton to something that is mathmaticly unbreakable, what happens next? New math I guess.

Frightening implications

[krackbebe]

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

[actappan]

Good science projects only get the shaft if they have nothing to do with:

• Killing the other guy in new and interesting ways.
  
• Reading the other guy's mail.
  
• Stealing from the other guy.
  
• Reading your own guys' mail.
  
• Stealing from your own guys.
  
• Killing your own guys in new and interesting ways.
  

Re:Frightening implications

[El_Nofx]

1. The us government does not have an unlimited budget.

2. Most meaningful research comes from the private sector (bell labs and the like) with a few exceptions (Darpa)

3. Even if the government had quantum computer level encription it couldn't get it's self organized enough to use it for more then maybe presidential level communication.

Re:Frightening implications

[jamesmartinluther]

Who would you rather have the cutting edge technology - a republic with the US constitution as its kernel and thousands of checks and balances, or a corporation who's primary interest (for good reason) is profit for its shareholders?

It is not as if we cannot possibly keep an eye on our own government. Information communities such as this one are a powerful counterbalance to government power, not to mention a multitude of technologies and legal remedies which are available to all US citizens.

Powerlessness and paranoia are a state of mind.

Re:Frightening implications

[Anonymous Coward]

Yeah and you probably still think they can't crack DES, either...

The NSA's budget is classified. They recruit top people in research fields (and not only U.S. citizens). The estimate I've heard is that they are more like TWENTY years ahead of civilian cryptographers. Don't be fooled by the government's outward appearance of being inept. They do get things done in certain areas where it counts.

Re:Frightening implications

[Ybrog]

My guess is not very far. The Govt has been shelling out grants to some independent researchers for a few years now. I've gone to a few of these researchers' lectures where they practice begging for money and all of them keep saying they expect ~50-100 years before they'll have something useful.

Re:Frightening implications

[Anonymous Coward]

It is not as if we cannot possibly keep an eye on our own government. Information communities such as this one are a powerful counterbalance to government power, not to mention a multitude of technologies and legal remedies which are available to all US citizens.

Oh please. Despite the protesting against the DMCA and other proposed laws here on /., do you think the government really cares? Do you honestly believe we will keep our eyes on our own government when so many people are willing to say the government shouldn't reveal all their activities, for the sake of defending America? The only real counterbalance is when the ruled is willing to challenge the rulers.

Re:Frightening implications

[internic]

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.

Re:Frightening implications

[rtaylor]

Considering what the constitution has bought the US in the last few years I think I'm going to place my bets behind IBM.

Their visible* track records over the last decade show my bet is likley to win.

* Many things both entities have done are not a part of my knowledge as that is what they wish -- atleast I assume I don't know everything.

Re:Frightening implications

[digitalunity]

You weren't paying attention. Shor's(sic) algorithm was discovered by AT&T's engineer by the same name in 1994!

Re:Frightening implications

[internic]

Sorry, I was thinking of Feynman's seminal paper on the topic (more or less the begining of the whole thing), which was published on '83 or 84'.

Re:Frightening implications

[forii]

It has been widely acknowledged that such agencies as the NSA have been at least a decade or more ahead of the private sector.

Schneier's Applied Cryptography has a discussion of this with regard to DES. Here's my description of it (I'm doing this off the top of my head, and I'm not an expert, so please excuse any mistakes):

In the early 1970s, IBM was contracted by the US Government to create a standard encryption algorithm that companies could use to secure their communications.

IBM was given free reign to design what they wanted, with one exception: Any algorithm that they developed would have to be given to the government (NSA) to look at, and the government would have final approval. So, after some work, IBM came up with the algorithm that we now know as DES, although what they came up with is slightly different than what is in use today...

The important part of DES, the part that does the actual encrypting, is a part of the algorithm where the incoming bits are mixed. The actual mixing can be described as a matrix of numbers. The makeup of this matrix is important, as it determines whether the bits are properly encrypted. If this block of numbers has the wrong configuration, then the numbers may not be mixed in a truly secure manner.

The question then, of course, is how to determine whether a block of numbers is "secure" or not. IBM had developed a test that would check this particular property, came up with a set of numbers that they had decided would make the algorithm properly secure, and gave it all to the NSA to check.

The NSA approved the algorithm, but with one exception: They supplied a new set of numbers for the mixing block! IBM checked these new numbers, found that they satisfied their requirements for security, and, so, that is what we are using today.

So What? About 10 years later a new method of attacking ciphers was developed, called Differential Analysis. This method was brand new, nobody had ever heard about it before, and turned out to be very powerful. Of course, DES was checked to see how secure it was against this new attack, and it turns out that the security of DES depends entirely on what numbers are picked for the mixing block.

Here's the interesting part: It turns out that the numbers used in DES, the ones that the NSA itself had generated and given to IBM, were in the 2% worst of all possible blocks to be used!

Coincidence? Perhaps...although it does seem to indicate that the NSA was aware of Differential Analysis many years before the rest of the world was, and purposely sabotaged DES to make it easier to crack. Remember that the NSA is the world's largest employer of mathematicians!

Re:Frightening implications

[lfourrier]

Please explain me how quantum computer can decrypt random one time pads.
It is not public key crypto, and it is used by many states.
The pad management and diffusion is the weak point, but I don't see how quantum computers can help break them.

Re:Frightening implications

[sql*kitten]

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?

IBM is no ordinary corporation - it's practically a country in its own right. Remember that two of the largest revolutions in computing (desktop PCs and relational databases) were things that IBM created, then couldn't exploit commercially, and they not only survived but thrived after two disasters like that. If anyone can do it, Intergalactic Battle Machines can...

Re:Frightening implications

[KjetilK]

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?

Re:Frightening implications

[sphealey]

It is not as if we cannot possibly keep an eye on our own government. Information communities such as this one are a powerful counterbalance to government power, not to mention a multitude of technologies and legal remedies which are available to all US citizens.

Well, back in the 1970's (as documented in The Puzzle Palace) the director of the NSA testified before Congress that he didn't believe that the Constitution or the Bill of Rights applied to the activities of the NSA.

They seem to have changed their tune a bit lately, what with the Crypto Musuem, releasing a Linux distro, and generally being more citizen-friendly. But my friends who went to work there in the 1980s (some of them _very_ smart guys) never reappeared in public, so who knows what really goes on behind closed doors?

sPh

Re:Frightening implications

[sphealey]

, the NSA is full mostly of mathematicians and computer scientsts, not physicists, so they really don't have the right staff for that.

The NSA run their own chip fab, and now that they are no longer able to buy all the equipment they need from US suppliers, they reverse engineer and rebuild the fab equipment they get from foreign sources, so I imagine they have a few physicists around some somewhere.

sPh

Re:Frightening implications

[jstott]

2. Most meaningful research comes from the private sector (bell labs and the like) with a few exceptions (Darpa)

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

Re:Frightening implications

[Angst Badger]

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.

Certainly. On the other hand, if you had looked at the thermionic-valve computers of the 1940's, it would have been hard to imagine the Atari 2600, much less a Beowulf cluster of quad-Xeons.

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.

Nor should you. However, given the way the NSA has largely backed off any serious efforts to outlaw public-key cryptography, it is likely that they have either the brute force computing power or classified algorithms to crack it, so it's not necessary to imagine exotic computing technology. Besides, if an agency like the NSA really wants information from you badly enough, you'll end up giving it to them, Winston.

Shouldn't there be a +1 Deeply Paranoid moderation option?

Re:Frightening implications

[KjetilK]

However, given the way the NSA has largely backed off any serious efforts to outlaw public-key cryptography, it is likely that they have either the brute force computing power or classified algorithms to crack it

I think it is more probable that they realized it is much easier to attack the passphrase or find some other way of breaking into the computer, install a keystroke logger and so on, than try to decipher a message by brute force.

Or it could just be that somebody actually realized that a country where strong cryptography is readily available to everyone is actually safer for everyone.

Almost There

[Renraku]

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.

Re:Almost There

[kesuki]

20-30 years is about right. AT&T proved the posibility of optical computing I can't remember the exact year but It was somewhere between 1980 and 1997. How long after that did it take for galium-arsenide optical processors to get put into DVD-rom drives. Anyways, I full well expect the Playstation 7 or the Xbox 5 to be using quantum-computers so that those 3-d games can be played with some kinda full immersion system with real physics. At the rate we're going now we won't need encryption, since noone outside the NSA or the FBI or the military will be allowed to use it. In fact it will probably be illegal to choose an operating system or modify any hardware device purchased.

Re:Almost There

[descil]

It's possible that this technology could take 20-30 years to develop. But unlikely.

Watch the development of technology. It comes faster and faster as our population grows and our tools become more precise and more accurate.

We have better methods of communication now. Better organization in our companies. Resources are more readily available. More minds are put to the task of computing, even idly (slashdot itself). More minds pour over textbooks of theory and new technology. Advancement is not considered the realm of the geeks, but the realm of the populous, or more so than it used to be.

If this sort of thing started in the 50's with major electronics, no wonder it took 50 years to get this far! We hadn't done anything like this ever before. The sheer number of scientists working on electrical engineering back then was a pebble compared to the mountain working on quantum computing now, with better resources, a more solid foundation, and a clear goal.

20 to 30 years? Don't fool yourself.

similar has been done before

[Phork]

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.

Re:similar has been done before

[MisterBlister]

7?? I can factor the largest prime known to man down to itself and 1 in MY HEAD!!!

NSA must be filled with IDIOTS !!!

OS

[geekoid]

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!

Re:OS

[mj01nir]

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

Write your own? Who the hell would do that? Just buy someone else's, slap your label on it, and then start bundling everything under the sun along with it.

So you want 1,000 copies of the Quantumsoft Ion OS? OK, we'll give you a great deal if you also buy 1,000 copies of Quantumsoft Cubix office suite and 1,000 copies of Quantumsoft Visual Q++.

Sounds dangerous...

[seebs]

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

Re:Sounds dangerous...

[charon_on_acheron]

What are the two factors of the number 7?

Re:Sounds dangerous...

[selectspec]

It explodes. Sort of like Michael Jackson standing in a room full of asian women.

Re:Just wait until it gets more complex

[krackbebe]

Imagine having to install yet another kernel patch 3.4.2.48-pre71-ac to fix the latest VM problems with an NMR machine.

Could quantum computing ever become general purpos

[khym]

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

[dummkopf]

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

Re:still a long way to go...

[bentini]

O(10^3)?!?! Being big o to a constant means any number. That's meaningless expression. Not to mention, I think it's understand that factoring 15 is still far away from useful application. Basically, what this poster says is, there are problems, because there are problems.
Insightful?

Re:still a long way to go...

[Decimal]

What about a hybrid of conventional computers and quantumn computers such as this one? The quantum computers could do relatively small tasks that would take a conventional computer some time to do, and pass that information back to the conventional computer to speed processing times.

Re:still a long way to go...

[autopr0n]

only O(10^3) computations can be performed before the system is decoherent

O(10^3)? Wtf? If you wanted to say "a thousand" you should have just said that. That way, people wouldn't have thought you a moron. O(1000) == O(1), btw.

Re:still a long way to go...

[dummkopf]

in physics we usually say O(10^x), x integer when we want to express that we have about 10^x of something. of course, in the purist sense of the O notation, that would be a constant, but hey, cut scientists some slack....

Re:still a long way to go...

[dummkopf]

well, as i explained before: physicists use the O notation to express orders of magnitude as well as asymptotic behaviors. what this means is that one can say O(log(N)) if you talk about an algorithm or O(10^23) if you address a macroscopic object. btw: at this moment, all physicists might consider you a moron. good night.

Re:still a long way to go...

[krazyninja]

I am a novice in this field, but I remember reading about the fact that, it is not the capability of a single "computational unit" like the one portrayed, but the combined capability of computational units that make the difference. Though we have only O(10^3) per unit, surely we must be able to utilise N of these units where N is a rather large number, so that N*O(0^3) is quite large?

Re:still a long way to go...

[dummkopf]

oh i am not saying we did not "rape" that expression. i agree with you in that it is a misuse of that expression. BUT it is widely used in physics circles as i explained above.

Assuming that everyone would understand the O-notation from physics was my fault. But being narrow minded and expecting that all functions called O(x) are for the O-notation is dumb. If we would have distinct names for all the functions and constant we have on the wolrd of science, we would soon run out of simple names...

Re:still a long way to go...

[roguerez]

But being narrow minded and expecting that all functions called O(x) are for the O-notation is dumb.

On a weblog that frequented by mainly computer scientists, it is.. :) But I disgress, I get your point as well.

anyone got a patch...

[merlyn]

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

but...

[klocwerk]

What kind of tea did they use????

Re:But...

[internic]

Yes, and maybe they're all puppets of the alien race that lives on the far side of the moon and secretly took over the NSA after we faked the moon landing.

In short, the point is I have no personal knowledge of what goes on in the classified projects of the US government, but there's no good reason to think that this technology was developed earlier or has been developed faster. In fact, in view of issues covered in my original post, it seems rather unlikely. We could think up all sorts of crazy ideas that none of us can prove false, but I would suggest we follow Occam's Razor and choose the simplest explaination to fit the known facts.

IBM's largest computer ever

[charon_on_acheron]

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

[Hank Reardon]

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

Big fucking atoms...

Re:IBM's largest computer ever

[charon_on_acheron]

This computer has only five atoms. There are three atoms of the element holyshitbatmanium, with a nuclear number of 150, and atomic weight of 19803289048221043893710.83221943. And the other two are of the element startrek:wtfcjsmalobtium, which has the nuclear number 151, and atomic weight of 351789544628017086650.3015785.

Re:IBM's largest computer ever

[Decimal]

> Big fucking atoms...

They're Bigons!

(What, you don't get it?)

Re:IBM's largest computer ever

[iabervon]

Those were based on only five atoms. The 2 tons were for the case, the power supply, the monitor, the fans, those sturdy IBM keyboards, the user manual, and so forth. But all of the really clever design was in those five atoms.

An Introduction...

[GFish4]

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

Re:An Introduction...

[jsse]

An Introduction to to Quantum Computing for Non-Physicists [lanl.gov] - Available in PDF, PostScript, and others.

Thank you for the great article, merely by reading the title it's definitely for me.

However, there's still far too many mathematics symbols in there which I don't understand. Do you have other articles for non-Physicists and non-Mathematics?

Re:An Introduction...

[GFish4]

Nope, sorry, this is the only one I know of. But as someone else suggested, you might try looking around http://xxx.lanl.gov/. They may have something there. Good luck!

--GFish4

Re:An Introduction...

[Soluxx]

If you want to read some good, non-technical articles on quantum computing, search for these (IEEE might have them, but the Xplore site is down right now):

Andrew Glassner, "Quantum Computing, Part 1," IEEE Computer Graphics and Applications, July/August 2001, pp. 84 - 92.
A. Glassner, "Quantum Computing, Part 2," IEEE Computer Graphics and Applications, September/October 2001, pp. 86 - 95.
A. Sheane and E. Rieffel, "Beyond Bits: The Future of Quantum Information Processing," Computer, January 2000, pp. 38 - 45.

If you want more of a technical paper, check this out (its still an intro, but not for laymen):
V. Vedral and M. B. Plenio, "Basics of Quantum Computation," quant-ph/9802065, 1998. http://xxx.lanl.gov/format/quant-ph/9802065

As for IBM building the 7 qubit computer, Los Alamos did it a while back...
http://www.lanl.gov/worldview/news/releases/archiv e/00-041.shtml

Crud!

[Pathos78]

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

Re:Crud!

[Alsee]

And I thought my 4-bit key's were safe!

The standard cryptographic solution to this kind of problem is to double your key length.

-

Re: Crud!

[glgraca]

Youll still be safe from 99.99% of humanity.

Re:Crud!

[Shade, The]

4-bit? You mean I'm not safe with 2?!

Re:Could quantum computing ever become general pur

[Logic Bomb]

I don't think the point was that this molecule could only factor 15 (well, maybe, but read on). The point is that they needed to make a molecule with 7 atoms that could interact in a certain way. To do bigger problems, they will need to design a molecular structure that fits many more atoms together. However, that structure will be able to solve *any* problems possible within its capacity.

Nonsense!

[Anonymous Coward]

Just send in Robert Redford and his team of lovable misfits to get the black box out of the answering machine!

Re:Nonsense!

[Hormonal]

Actually, in that movie (Sneakers, not Misfits of Science, like the AC said (and wasn't that a TV show?)), the big breakthrough wasn't Quantum computing per se. The guy was a Mathemetician (sp?), who figured out a shortcut to factoring large numbers.

I guess it was never stated what exactly the chip did, so it could have been a quantum computer, although how this guy would get a Quantum computer into a chip, I dunno. It's not like the movie was really great on the details, anyway.

"Computer, zoom in and enhance. Indefinitely. I wanna see if that guy's got dandruff."

Re:XP

[aka-ed]

"many people thought quantum computing was just a theoretical curiosity and Shor's algorithm could never be implemented in practice."

Who exactly thought this?

Me. It's about time I got some recognition!

Re:Flame war

[coolgeek]

I believe the UI on this thing is more of the "Switches and Lamps" variety.

My boss says ...

[benedict]

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

explain

[cyberbob2010]

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?

Re:explain

[mkarpinski]

Start here: http://www.qubit.org/

Question

[stapedium]

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?

Re:Question

[Dwonis]

IDEA

It probably suffers from the same problems.

or even Xoring with a big chunk of random data?

This is known as a one-time pad (where the key is the same length as the message), and it's unbreakable (not just hard to break). Of course, it's also difficult to exchange these keys.

Unfortunately NMR quantum computing has limits

[Spooky Possum]

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

[nihilogos]

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.

Re:Unfortunately NMR quantum computing has limits

[wass]

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

Offtopic, but you've got it backwards. NMR (Nuclear Magnetic Resonance) was developed by physicsts, and later applied to medicine by biophysicists. At the advice of some marketing genius, they changed the acronym to MRI, knowing that most of the public wouldn't go into a giant machine with the word "Nuclear" in it's title. It's actually the same physics processes in action for NMR and MRI, though.

So, the basics didn't come from the medical industry, but vice versa.

Re:Unfortunately NMR quantum computing has limits

[Spooky Possum]

Well if you can't make the state then not being able to measure it isn't the problem :).

It's the same problem either way, writing or reading, you still want good signal to noise (although, arguably, since Shor's algorithm is probabilistic then a bit more noise on the output isn't as bad as a bit more noise on the input, but when they're both exponentially bad, who cares).

Re:Unfortunately NMR quantum computing has limits

[Sayjack]

Perhaps these limits imply that the computer of the future involves interaction between many specialized quantum computers. Perhaps becoming a part comprising the whole.

Los Alamos and "federal researchers"

[Anonymous Coward]

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.

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,3512 1, 00.html

Meow

[KarmaBlackballed]

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

Re:Meow

[automatic_jack]

I don't get it.

Re:Meow

[TheOnlyCoolTim]

Do a Google search on Schrodinger's Cat. Basically it is a situation where under the theories of quantum physics you could have a cat that is both alive and dead at the same time. It is theoretically possible but as I understand it practically impossible, because you would need a container (commonly called the Cat Box) which *NOTHING* could penetrate...

Tim

Re:Meow

[rtscts]

Only if you don't open it and let it out. Or beat the crap out of it with the builtin hammer.

Re:Meow

[DrSpin]

There's only a 50% chance you'll ever find out!

Osama Win Modem: All your quantum are us!

Someones gotta say it!

[beretboy]

Could you imagine a beowulf cluster of these things!

Re:Someones gotta say it!

[DigitalEntropy]

Could you imagine a beowulf cluster of these things!

I think that's called an abacus. I'm not sure though...

Re:Someones gotta say it!

[Dyolf Knip]

Wouldn't do much. Hooking up a bunch of 7-qubit computers gives you an additive increase in computational power while just adding another qubit gives an exponential increase. That is, it takes two 7-qubit computers to do the same job as an 8-qubit, four to equal 9 qubits, etc, etc.

However, if and when this takes off, there'll be a sweet spot where it is easier to build the extra weaker computers than the more powerful larger one. Ie, $20 for a 7 qubit processor but $50 for one with 8 qubits; you'd be better off with the weaker ones.

Re:Someones gotta say it!

[ErikZ]

Yeah, that's why you see so many computers today that are really a bunch of 4 bit processors running in parallel. Cause it's so much cheaper.

Re:Someones gotta say it!

[rtaylor]

Thats precisely what you have. In somecases a thousand 32bit processors running in parallel rather than a single 32000 bit processor.

I even have a dual celeron under my desk as it was (and continues to be) cheaper than a Sparc or Alpha (and many others) but is (for what I do with it) close enough is speed to the other that I don't notice.

That's easy!

[MicroBerto]

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

Re:That's easy!

[MisterBlister]

I can factor 100000 digit primes in MY HEAD!

Truly I am the ELITEST MOTHERFUCKER EVER!

Re:That's easy!

[rtaylor]

So can I, but I cannot communicate those values to anyone as my nervous system (controllings hands, mouth, etc) cannot handle the load and crashes.

Too bad really. Having the answers to all the questions and not being able to share.

Re:That's easy!

[Debillitatus]

Maybe I'm "The One"!!

And maybe you're not.

Re:That's easy!

[digitalunity]

Often times, my brain throws a General Protection Fault in module Hypothalamus.

Another article at News.com

[A Commentor]

It's also discussed at news.com .

You Heard It Here First...

[cybrpnk]

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

[Anonymous Coward]

Even more interesting is that the progression was 2, 3, 5, 7... all primes. Next will be 11...?

Re:You Heard It Here First...

[tunah]

And how many qubits did it take you to factor 7=2*4?

Re:You Heard It Here First...

[Traa]

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

Re:You Heard It Here First...

[squaretorus]

Does anyone know of a 'not for physicists' guide to what can usefully be done with different numbers of qbits?

7 qbits factors 15 to 3 and 5

How many do we need to factor a 50 digit number?
How many to do some maths we just don't have time to do with Binary?

Re:You Heard It Here First...

[Ionized]

uh... look again, smart guy.

now a 7 qbit computer in December 2001....they've still got another couple of months to get the 8th qbit....

(emphasis mine)

Almost there!

[Black Parrot]

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

Re:Almost there!

[smack_attack]

Thank you CmdrObvious

Re:Almost there!

[Alsee]

No one should ever need more than 640 Qbits.

According to cybrpnk's law we should hit 640 Qbits in just under 10 years!

-

In other news...

[millette]

... builds an unlimited quantum computer.

Time to call the DMCA

[Anonymous Coward]

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

[Muerte23]

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

Re:The End of Asymmetric Key Distribution

[glwtta]

Seems to me that it only breaks encyption schemes that rely on factorization of 15.

Re:The End of Asymmetric Key Distribution

[zCyl]

I think that most current crypto algorithms are based on factoring primes

When you factor your first prime, I recommend publishing the result...

Re:The End of Asymmetric Key Distribution

[zCyl]

a crypto key that is totally unbreakable. Untappable, unbreakable, impervious.

And how exactly is it that quantum key distribution is supposed to protect us from the classic and proven man-in-the-middle attack?

Re:The End of Asymmetric Key Distribution

[frankie]

The whole point of quantum encryption (which is completely a different process than quantum computing) is that observing the quantum causes the quantum to change. Therefore, the man in the middle will disrupt the transmission and be detected instantly.

Quantum encryption, when used correctly, is really truly mathematically proven to be unbreakable by any means.

Re:The End of Asymmetric Key Distribution

[zCyl]

The whole point of quantum encryption (which is completely a different process than quantum computing) is that observing the quantum causes the quantum to change. Therefore, the man in the middle will disrupt the transmission and be detected instantly.

I suggest checking the literature a little more closely. A man in the middle will not disrupt the transmission, because a man in the middle is not an eavesdropper, he's pretending to be both ends of the link at once. Person A tries to communicate with person B, and establishes a secure link, but really, the secure uncrackable link is with person C standing in the middle, and person C then establishes a secure uncrackable link with person B. The problem then becomes, how does person A know that it's REALLY person B that a secure communication has been established with, and vice versa.

Preventing a man-in-the-middle attack requires authentication, not secure communication. And when it comes down to it, encryption without authentication is almost useless, because man-in-the-middle attacks are not really that difficult to pull off. Classically, authentication is typically done with the existence of some sort of one-way hash function. I don't know if any hash functions are going to survive the dawn of the quantum computing age.

In other news...

[millette]

builds the first unlimited quantum computer.

Downsides....

[dh003i]

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

[ZigMonty]

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

Re:Downsides....

[Dwonis]

The only thing that's secure against quantum computers is one-time pads, which are impractical over the internet.

Re:Downsides....

[mlk]

I don't think so.

It'll prob involve have a Quatum computer at home, but some one very bloody clever will think of something.

But I'd give that 5yrs before it's out dated, (repeate)

Re:Downsides....

[zbuffered]

I'm sure it'll be quite a while before you see PQCs at Best Buy, but if that ever happens, we're in more trouble than just needing a new encryption scheme. I could start capturing secured traffic now, wait for this thing to get big, and decrypt it then. I could capture most everything that's been encrypted with current schemes, and decrypt it in the future.
It's kinda scary when you think about it like that.

Re:Downsides....

[dh003i]

Ok, maybe I was misaken about PGP. I've heard about an encryption system which encrypts something using an unsolvable mathematical puzzle. PGP, apparently, simply multiplies things a lot such that its impossible for current computers to factor them.

Well, if we did have quantum computers, we coudld just encrypt with quantum computers, and encrypt that much more, such that even a quantum computer couldn't decrypt.

Re:Downsides....

[castlan]

Or, you could just capture the traffic now, and run a modern cracker against it. By the time quantum-computing technology becomes consumer-level technology, it is likely that anything you have a significant interest in will have been cracked. Just don't ever turn off your computer.

-castlan

Re:Downsides....

[castlan]

That sounds like you are taling about the standard UNIX encryption library, which is visibly used for the standard UNIX passwd command. You cannot determine what the password is by performing matematical transformations on the /etc/passwd contents.

Instead, we use passwd to perform the transormations on what we suspect the user used for the password. If the output is the same as the previously encypted password in /etc/passwd, then there is a match.

To exploit this, you passwd-encrypt a dictionary of words, and then see if any of the output matches an entry in /etc/passwd.

not true

[phr1]

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.

Re:not true

[Miriku chan]

this is incorrect. a quantum computer can take a task thats usually O(c^n) into a O(n). this is a HUGE HUGE difference.

Re:not true

[sh_mmer]

okay, each poster is more full of shit than the last one (well, not me though).

to the most recent poster: a quantum computer can do some very special things exponentially faster than it would take a classical computer to do the exact same thing which is not necessarily to say exponentially faster than a classical computer could come up with the same answer. in particular, there are plenty of encryption schemes (the previous poster was right) for which a quantum computer can't do it any faster than the classical one.

to the previous poster: private-key cryptography isn't nearly as useful as public-key, since key exchange cannot be done over an insecure medium (such as the internet). also 'obsolete' is not a verb.

to the first poster: there is still at least one public-key encryption system that is unbroken by quantum algorithms. it is the McEliece cryptosystem, based on an error-correcting code. it is not currently used, however, since the key length is O(10^7) bits.

cheers,

jeremy

Old news

[sharkey]

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?

Re:Old news

[Captain Nitpick]

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?

Seeing as Noah could still only count to two using the Ark, using 7 qubits to do basic math is impressive.

(Captain Nitpick is more than aware of the difference between a cubit and a qubit. Cubits have the remarkable property that one can use them to calculate =3)

Re:Old news

[jaavaaguru]

Maybe Renault was wrong. Who says size matters ;-P

Re:Old news

[sharkey]

using 7 qubits to do basic math is impressive.

Perhaps he brought in 7 of each sex of each animal. Then he found the one of each sex of each animal that could do the most amusing trick, and took that one into the Ark.

Uh

[autopr0n]

The behavior of divide by zero is user defined on most computers. You can have the computer say whatever you want it to say. You've just got to mess with the interrupt vector table.

Btw, the limit of 1/x as x approaches zero is infinity. but 1/x isn't infinity. If it were you could do things like

1/x = inf
2/x = inf
so 1 == 2

Re:Uh

[sh_mmer]

so by your logic, we can just let x go to infinity, then:

1*x = inf
2*x = inf
=>
1 = 2

of course, your conclusion is right, but your logic is wrong. that's because infinity is not a number, but rather the concept of unboundedness. (it's obvious that two unbounded quantities do not have to be equal to each other.)

Re:Uh

[Kwikymart]

Actually, the limit as x approaches 0 of f(x)=1/x is NOT infinity. The part of the definition of a limit says that the left and right hand limits (x -> 0- and x -> 0+) have to be equal to each other.

lim f(x) = +inf
x->0+

lim f(x) = -inf
x->0-

The limits do not match, therefor there is no limit x -> 0 of f(x) (approaching from both sides)

Re:Uh

[Kwikymart]

Oh, by the way

f(x) = 1/x

lim f(x) = +/- inf
x->0

Is NOT correct (any calculus book that says so is wrong)

Re:Uh

[Kwikymart]

No shit sherlock, I was providing something I left out of my explanation in the parent post to the post you replied to.

Re:Uh

[Ionized]

no. please reread his post. he was assigning the value of zero to x. the result was infinity. your argument does not even apply.

p.s.:

(it's obvious that two unbounded quantities do not have to be equal to each other.)

unbounded quantities = oxymoron. if something is unbounded, it cannot be quantified.

Re:Uh

[sh_mmer]

"unbounded quantity" is not an oxymoron. for example, how many natural numbers are there?

a. the question is undefined.
b. infinity, but that's not an unbounded quantity.
c. an unbounded quantity, but not infinity.
d. infinity, an unbounded quantity.

if you don't like 'unbounded quantity' in my previous argument, substitute 'unbounded sequence'

cheers,

Re:Uh

[Ionized]

unbounded quantity is most certainly an oxymoron.

definition of quantity

see?

on the same note, infinity is not a quantity. unbounded, sure, by definition. but its a concept, not a quantity.

unbounded sequence works.

Re:Uh

[sh_mmer]

what are you talking about? here is the entire list of definitions (all 5) that you pointed me to, and not one of them says anything about being finite. all you have are two possible synonyms: number, ammount. what did you think, that i wouldn't even look at your reference?

anyway, i'm not wrong that "infinte quantity" in fact makes sense, but the original point was that everybody knows that

a = inf
b = inf

does not imply a = b. which is also right. alright, that's it for me.

cheers,

A specified or indefinite number or amount.
A considerable amount or number: sells drugs wholesale and in quantity.
An exact amount or number.
The measurable, countable, or comparable property or aspect of a thing.
Mathematics. Something that serves as the object of an operation.

Re:Uh

[Ionized]

well, sorry, i thought it would be blatantly obvious to anyone looking at the link what i was getting at. since it apparently wasn't, i'll do a line-by-line of each definition.

A specified or indefinite number or amount.
infinity is certainly not specified, and it is not a number or an amount. therefore, this definition does not apply.

A considerable amount or number: sells drugs wholesale and in quantity.
same as above.

An exact amount or number.
same as above.

The measurable, countable, or comparable property or aspect of a thing.
can you measure infinity? can you count it? can you compare it? no? well, then this definition doesn't apply.

Mathematics. Something that serves as the object of an operation.
as any good calculus course will teach you, you do not perform operations with infinity. you yourself mentioned so earlier. therefore this definition does not apply.

it returns one and the number

[autopr0n]

dumbass.

What this really means

[mcrbids]

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.

Re:What this really means

[Anonymous Coward]

Ya, I'm terrified that all those people out there are going after me with quantum computers. :-)

Quantum computing research itself, interestingly enough, has provided at least a replacement for secure communication, if not secure storage, and as far as we know, it's unbreakable (if not currently feasible). You can a stream of information encoded as quantum bits. Any attempt to access them might succeed, yes, but the intended recipient will know, because the stream has been destroyed.

How long?

[billyjoeray]

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

Uhm...

[autopr0n]

Yeah, that's why you see so many big computers today that are really a bunch of 32 bit processors running in parallel. Cause it's so much cheaper.

xxx.lanl.gov

[autopr0n]

Available in PDF, PostScript, and others.

That is, as long as you're not on a machine with a porn blocker...

that's not much of an upshot then...

[Anonymous Coward]

...since all NP-complete problems are currently possible to solve. You can solve any NP-complete problem on a deterministic computer, just not in polynomial time.

More generally (and more interestingly), there is absolutely NOTHING that a quantum computer, or any mythical non-deterministic computer, can do that a deterministic one can't. DTM's are just a bit slow is all.

Re:that's not much of an upshot then...

[tomstdenis]

Which gets back to the original point. Quantum computing is just a way to sieve multiple solutions in parallel. Much akin to the idea of DNA Computing.

Think of a beowolf cluster of 1,000,000 athlons at 1.4ghz compared to a single 486 60mhz. The time per solution is hugely different even if the exact same binary program is used to solve the problem.

Also QC does not break any barriers related to NP != P. If a QC computer works this does not change. It just means some NP problems become faster to solve.

Tom

So like..

[i_am_nitrogen]

Yeah, with a cluster of those I can find out that 15 is 5*3 in less time than ever!

On the other hand, theoretically speaking, if you could create even a single general purpose quantum computer, that doesn't degrade after so many calculations, and can interface quickly and easily to other systems, you could do some serious damage (or good) with that. Cure any disease, crack any encryption (DNA or "God's encryption" included), design a virus to wipe out a particular race, family, or even person, ...

The possibilities are both frightening and exciting at once.

Stockpiling emails

[shimmin]

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?

Re:Stockpiling emails

[ErikTheRed]

Yeah, but the decrypted e-mails would be of more use to divorce lawyers than anyone else. Let's hope the American Bar Association never gets ahold of a quantum computer....

Re:You make me sick!

[Anonymous Coward]

then either browse at 2+
or goto a better site.

Stuff like this makes me wonder...

[Oswald]

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

Re:Stuff like this makes me wonder...

[delong]

Well... I don't know anything about the details of the science but it seems to me economically generating a permanent containment field for a plasma hot as the sun is a wee bit trickier than measuring the spin on an atom.

But what do I know. I have a liberal arts degree.

;P
Derek

Re:not in general

[phr1]

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.

Re:not in general

[Elwood P Dowd]

Ok, I'm not educated on the matter. Please tell me how RSA is not a factoring problem. Iduno about other public key systems, but I was pretty sure that fast factoring of large numbers breaks RSA.

Re:not in general

[Elwood P Dowd]

Oh. Sorry. Reread top level post. Ignore please.

Actually it is true

[Anonymous Coward]

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:)

Correction Re:Actually it is true

[Anonymous Coward]

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

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

Very impressive

[Animats]

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.

You're exactly right and wrong!

[HiredMan]

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

[forii]

Well... You're exactly right. That's what I get for writing off the top of my head! You induced me to search through all my boxed-up books (I moved recently), and sure enough... I have mistaken the susceptibility of DES to Linear Cryptanalysis with Differential Analysis.

Diff Analysis was part of the design criteria, but not explicitly stated at the time, but Linear Analysis wasn't, and the S-Boxes in DES are among the 9 to 16 percent weakest against that attack.

Thanks for the correction.

Re:You're exactly right and wrong!

[HiredMan]

All in all DES is a pretty good algorithm but it does reveal what the NSA knew THEN (1970s) and it seems equal or better than the public knowledge now.

DES is NOT a group (proved 1992), the number of permutations (16) also makes it hardened against DiffCrypt where 8 is not enough. It wasn't until difcrypt came along that the need for 16 perms was finally revealed. (More proof that the NSA knew about DC then if we needed it.)

The permutations are also needed against linear crypt - 8 permutations are 2^21 plaintext breakable and 16 is 2^43. You're right - linear is the most effective (as far as we know ;) attack against DES as of now.

The shift from a theoritical 2^47 to a real life 2^43 isn't THAT bad - seems to be a good general compromise between being hardened against a broad range of attacks. If the NSA had allowed uniform Sboxes the difficulty would fall as low as 2^26.

I do wonder in coming years if we'll learn of an NSA technique against DES we never thought of... but I have to think that if they assumed that foreign govs knew (or would come to know what the NSA knew - remember the Russian are very good at math and codes) that they really did want an all-around secure algorithm.

As I heard someone once suggest though - given that the NSA measures it's computing power in "acres" and has for years... what if they just dedicated older super computers to brute force attacks like searching for, factoring and cataloging very large prime numbers and mapping/cataloging every possible text-block in to out-put out of every major alogrithm? Couldn't they have an amazing pre-computed brute force hammer to apply when needed? If you think your RSA is safe because of the difficulty involved in factoring very large primes - what if someone had been working on it for 30+ years with ever increasing computer power?

=tkk

I want me one of these

[ResQuad]

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

Yea!!!!

Effect on Magnetism?

[Trinition]

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

[cyberatz]

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

Re:factors

[Tekgno]

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.

Quantum computers mean double symmetric key length

[shalunov]

Your assertion that quantum computers would be the end of conventional cryptography is incorrect. While it's true that Shor's algorithm would enable you to break RSA and other public key cryptosystems such as DSS and ElGamal, the impact of quantum computers on conventional symmetric cyphers (such as, e.g., AES) is understood and limited.

Namely, Grover's algorithm would enable you to brute force a symmetric key of size N in O(exp(N/2)) time rather than the current O(exp(N)) time.

In other words, if quantum computers (even with very large number of qubits) are built, today's public key cryptosystems would no longer be secure, but today's symmetric cyphers would simply need to have their key length doubled to keep the same rough level of security.

Fool!

[Jebediah21]

You should have used 5-bit keys like me.

Imagine...

[riggwelter]

...a beowulf cluster of these ;)

(Sorry, someone had to say it!)

Re:Imagine...

[CCIEwannabe]

your email is riggwelter@I.DO.NOT.WANT.SPAM.rubberturnip.org.uk

If you dont want spam I suggest you stop making those beowolf cluster jokes!

4-bit RSA is broken!

[mgedmin]

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

[Andy.T.BOFH]

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

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

[ketilf]

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

[3seas]

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?

old new idea (Re:The End of Asymmetric Key Distrib

[e7]

To get around the death-of-PKI problem, I'm currently writing openSSH support for the St. Cyr algorithm. Security through obscurity isn't always a bad thing.

1. Disclosures:
2. The St. Cyr system is hundreds of years old, and thus literally a textbook case for intelligence people.
3. Even if I could write a patch for openSSH, do you think they'd accept it? :-P

Super Quantum Computer

[Salsaman]

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 ?

No, because quantum CRYPTO is closer to reality

[gilgongo]

Don't forget that quantum physics is also being applied by cryptographers and successfully encrypted packts have been sent using such means over quite long distances (over 1KM I believe).

Even if we see a huge surge in the power of quantum computing, it will NEVER be able to crack quantum cryptography. If it did, then the very laws of physics on which these principles are based would be wrong.

G

Achtung! Halt!

[Kasreyn]

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

[StressGuy]

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

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

[Lazaru5]

The first mechanical computer only did elementary math also.

What do you freaking expect? A holodeck? The first electronic computer couldn't render immersive 3D scenes, so don't expect miracles from the first quantom computers.

The breakthrough here is that quantom computing is no longer just theory. It's the birth of an entirely new type of computing.

You're just too used to being pampered by your Athlon XPs and Geforce3s.

Re:You make me sick!

[liquidsin]

Well then if you're so sick of beowulf cluster jokes, maybe we need a new one. How about some sort of poll on quantum computing, along the lines of this:

How long will it take IBM's new quantum computer to crack the new Advanced Encryption Standard?

• 1 year
• 5 years
• They'll never do it
• F(a) = x^a mod [cowboyne(a)l]

now THAT would be funny!

NMR vs. MRI

[d5w]

NMR (Nuclear Magnetic Resonance) was developed by physicsts, and later applied to medicine by biophysicists. At the advice of some marketing genius, they changed the acronym to MRI, knowing that most of the public wouldn't go into a giant machine with the word "Nuclear" in it's title.

I'd heard this renaming story for years, and it's been frequently retold, but [Warning: vague sources follow, filtered through memory] in the past year or so I was listening to an NPR program (possibly "Talk of the Nation") and a caller who claimed to have been around for the renaming said that while "NMR" became "MRI" for PR reasons it was for internal rather than external PR -- basically an academic turf war: in terms of funding and/or department responsibility it was very strongly ingrained practice that anything with "nuclear" in the title was the responsibility of the faculties of radiology, rather than medicine, and the faculties of medicine didn't want to let go of it, so they renamed it.

Obsolete is a verb

[Defiler]

Scroll down:
Obsolete

Re:Obsolete is a verb

[sh_mmer]

aa, whatever. i just wanted to say that. leave it to slashdotters to comment only on the most trivial of points. anyway, strunk and white agree with me, even if you can find it in the dictionary, so ptttht.

Robert Pike on qc:

[mvw]

A nice audio cast by Unix guru Rob Pike can be found here:

http://www.technetcast.com/tnc_play_stream.html?st ream_id=310

Check the slides too at:

http://cm.bell-labs.com/who/rob/qcintro.pdf

Regards,
Marc

Re:No artificial intelligence yet...

[Oswald]

Yeah, that's true. I knew there was a good example I was forgetting; I just couldn't think of it when I was posting. Oh well, forget I mentioned it.

Oh, I see

[autopr0n]

How stupid.

So will it be possible...

[llama1911]

...to overclock it?

Um, you disproved yourself :P

[autopr0n]

According the very definition you linked:

1.a: A specified or indefinite number or amount.
Is infinity not an indefinite number?

Re:Um, you disproved yourself :P

[Ionized]

no, infinity is not a number at all. you should have learned that in any intro calculus type course, if not beforehand.

IBM's next Quantum Computer

[Nathan Brazil]

I predict they'll set up the next Quantum Computer to factor 42... and come up with 6*9, despite the fact neither of those numbers are prime.

Re:Fine.

[Dwonis]

I never did learn AWK. (/me reads awk(1)). Hmm... An interesting tool. And lighter-weight than Perl. Might use this for bootdisks or base system scripts or something... Interesting... Thanks.

Re:Fine.

[Dwonis]

How is this a troll? I'm *serious*. People try to do too much with perl (as they do in VB), when the jobs would be much better done in other languages:

• A perl module for developing internet servers in perl
• Highly modularized GTK+ mail client written in Perl
• High-resolution time manipulation in perl
• Sliding-blocks puzzle (glotski written in perl)

Need I go on?

Re:Fine.

[mlk]

any time :)
awk is great, even better than perl when no-one (or even better, someone you hate) needs to read the code ;)

Literal response to joke

[castlan]

To venture out on a limb and make a statement that I should not make, being that I am crytographically challenged:
Why not just use a 1 bit key? Anybody that knows how to crack your message can get the job done anyway, but it would still keep your content private to the general public, with minimal CPU expenditure. I an ignorantly guessing that XORing your data qualifies?

Actually, all of the above is bullshit. I just wanted to be a nudge and point out some possible exceptions to the statements made in your signature.

It is very probable that somebody got fired at SGI for choosing Microsoft, probably each time it happened (NT4-MIPS with ARC booting, SGI Visual Workstations using NT4-x86 with ARC booting...) It's likely the decision to base the AOL web-brower on IE wasn't highly rewarded either.

I'm also sure that many fools have been exposed by trying to run a Linux based OS on a Token ring network. Those involved in the OpenBSD project would probably mave some interesting alternatives to praise ready for any who would suggest that they host their web site on RedHat Boxen.

I must really be itching for some negative mod points here... Perhaps I should have encrypted this message before posting.

-castlan

Re:Literal response to joke

[Jebediah21]

1 bit encyption is every bit as hard for users as 4, 16, 512, or any other encryption is. Just slower on the computer really. If you are going to encrypt something you might as well make it a pain to decipher. I know you said it's bullshit; I just wanted to clarify.

I'm fully aware my sig can be taken as a joke or intereperated literally. Make what you will of it.

Re:XP

[aka-ed]

It may be a hellhole but it's my hellhole.