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

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

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

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.

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

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