QUANTUM COMPUTER PERFORMS FIRST SUCCESSFUL FACTORING

[ciphergoth]

QUANTUM COMPUTER PERFORMS FIRST SUCCESSFUL FACTORING

IBM SCIENTISTS BUILD MACHINE THAT SOLVES MATHEMATICAL PROBLEMS WITH QUANTUM MECHANICS

NUMBER 15 FACTORED

FACTORS ARE 3 AND 5

http://www.research.ibm.com/resources/news/20011219_quantum.shtml

Comments

[aegidian]

Well, well.
As I recall, doesn't that mean that cryptography based on the difficulty of factoring is now pretty much pooched?

Gulp.

[babysimon]

Wow! Cool. I think.

But they appear to need a specific design of molecule to get 7 qubits - so this isn't going to scale. I like the quote "The first quantum computing applications would likely to be co-processors" -- as if people were thinking the market was about to be flooded with 1Gqb SIMMs.

But if they do manage to build a 16kqb machine (or however large a box one would need to brute-force RSA), this would lead to some serious asymmetry. We keep hearing about quantum crypto, but AFAIK that requires a special link between computers, and can only be done at the transport layer. Hardly something you can run over IP. Am I right? If so, I would like to wish everyone a happy goldfish bowl, like at the end of the Asimov story...

[bootpunk.livejournal.com]

Well, as soon as they manage to build a very large qubit machine, yep (as per the article). Thats a ways off tho', barring any big breakthrus.

Of course, if you're the really paranoid type, you should maybe assume that the NSA already has one of these ... ;o)

[ciphergoth.livejournal.com]

Not yet. The technology used for this demonstration - armies of NMR qubits moving in synchrony - is impossible to scale up to many qubits on a very fundamental level. This demonstration looks good but doesn't tell us anything we didn't already know - in particular, it doesn't tell us anything about whether many-qubit quantum computing will ever be possible.

[babysimon]

Paul's the expert here, but I think it's in fact all (non-quantum) crypto, all NP-complete problems, and probably a bunch of other stuff.

[babysimon]

Wow. I post and find two others have posted first. Busy night. Shouldn't we be out shagging or something?

[bootpunk.livejournal.com]

Remember the time differential, dear boy. I'm off for fondue then a fetish club, but its only just early atm here ...

:o)

Re: Gulp.

[bootpunk.livejournal.com]

As per above, mibby I should leave a response to the expert in our midst, but afaik, it's the transmission of single photons twixt points - so an opto-connection would suffice. I'm sure ciphergoth will correct me if I'm wrong.

Re: Gulp.

[babysimon]

"an opto-connection would suffice"]

Last mile?

Re: Gulp.

[bootpunk.livejournal.com]

Again, IANAC(ryptofreak), but I seem to recall even our own BT saying that they could see thousand metre connections shortly/now, and much further soonish. The connections aren't the major issue, iirc. But I'm out of me depth here, and I can't remember the details clearly, so I'll STFU.

Re: Gulp.

[ciphergoth.livejournal.com]

Symmetric crypto keeps working. Grover's algorithm means we have to double our key lengths, but that's no hardship, and really something we should be doing anyway; 256-bit keys are the Right Thing for a variety of reasons. So no need to use that impractical quantum crypto stuff.

But I think Shor has shown QC algorithms for pretty much all the important problems that lie at the heart of public-key stuff. We've got quite used to having public key crypto, it would be sort of weird to lose it again.

Despite this news, I would still be surprised if anyone ever gets, say, a 50-qubit machine going. The equivalent of Moore's Law for quantum computing at the moment seems to be that the machines grow by 1 qubit a year...

Re: Gulp.

[bootpunk.livejournal.com]

> Despite this news, I would still be surprised if anyone ever> gets, say, a 50-qubit machine going.
[my emphasis]

Don't you mean "in the near future"? Or do you think that quantum computing will prove to be too expensive or surpassed by a different technology before it ever becomes scaled sufficeintly?

[ciphergoth.livejournal.com]

Actually it's not quite that devastating. We don't have algorithms for solving any NP-complete problems in polynomial time on a quantum computer. What we have are algorithms for factoring and discrete log, which are basically the two problems at the heart of public key cryptography, and Grover's algorithm which halves effective key lengths for symmetric cryptography.

Re: Gulp.

[ciphergoth.livejournal.com]

For the record, I think quantum cryptography is silly. For provable security, you have to exchange secret keys in advance to get the authentication working, and if you're going to do that then I don't think the massive inconvenience buys you much over perfectly ordinary symmetric techniques.

[babysimon]

Sorry, I was assuming (but not stating) a fully-quantum computer, which would effectively be the nondeterministic turing machine of lectures past, and hence solve NP-complete problems in polynomial time trivially.

Re: Gulp.

[ciphergoth.livejournal.com]

It's already surpassed by conventional techniques, and if both conventional and quantum techniques stick to their current rates of improvement then it always will be.

Also, it may turn out to be fundamentally impossible to run a 50-qubit machine without decoherence killing it...

[ciphergoth.livejournal.com]

My excuse is that I'm not very well. I actually asked coracaskia to go stay with another lover last night because I'm not really well enough to enjoy her company properly...

[ciphergoth.livejournal.com]

No, it doesn't work that way, because you can't combine all the histories at the end in a way which will tell you whether one of them found a solution. The only combining operator you have in the quantum universe is the "complex sum over histories" which determines the probability of a final observation going a particular way based on a sum of "amplitudes", which are probabilities represented as complex numbers. If you could use this to implement the "OR" operator, you could ask if any of the histories found a solution, thus breaking any problem in NP. But no-one's found a way to do that.

Er, does that make any sense?

[babysimon]

The first sentence does. The rest is probably too quantum for me ;-)

But damn, you've really disillusioned me. I thought all that talk of NDTMs might one day have some real-world meaning.

Fucking academics.

[jhg.livejournal.com]

NUMBER 15 FACTORED

FACTORS ARE 3 AND 5

Um, so what? I can do that in my head, really quickly.

Shouldn't a quantum computer be inventing FTL travel, and making people's undergarments disappear and reappear at the far side of the unverse, and that sort of thing?


J

[ajva.livejournal.com]

You can only do it in your head because you already know the answer.

As well you know...

[ciphergoth.livejournal.com]

Cool! While you're at it, what are the factors of 18819881292060796383869723946165043980716356337941
73827007633564229888597152346654853190606065047430
45317388011303396716199692321205734031879550656996
221305168759307650257059?

[alienspacebat.livejournal.com]

What we really want is to make undergarments dissapear with the power of the mind. Now that would be a cool pub trick!

[jhg.livejournal.com]

Actually, I did have a vague idea that Von Neumann computers couldn't do 'factors' - but surely saying 'The Factors Of 15 are 5 and 3' is surely an ill-thought out headline.

'Sides, Quantum Computer sounds exciting. Like Quantum Leap, or something.


J

[ciphergoth.livejournal.com]

Various factoring algorithms exist. The simplest is "trial division" - try dividing by every odd number up to the square root until you find one that works. The fastest known for large numbers is called the General Number Field Sieve, and is frankly beyond my understanding at the moment. But we know of no way of factoring, say, 600-digit numbers even if we combined the entire computing resources of the world. If we could build a quantum computer with many thousands of qubits, that could do it.

There's a $10,000 prize for factoring the number I quoted, though, so I thouhgt it was worth a go...

http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html

[bootpunk.livejournal.com]

Far more humourous to make them jump three feet to the right of whoever was wearing them.

[tips hat to Douglas Admas]