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]

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.