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

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

[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

[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

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

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

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.

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

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