BetaBenj sent us the latest update from
TechWeb concerning the latest advances in solid quantum computing. Recently, there have been a couple key advances bringing us closer-but we're still a ways out. Still, the ramifications of it are
almost as staggering as nanotech. Almost.
Slashdot Mirror
the technical details described in the article, but I do have (imho ;) a decent understanding of the computational principle behind quantum computing. I've seen some pretty wrong (or just confused) things in the comments...and /. discussions of encryption/complexity related issues frequently get mired in BS ;)
Quantum computers do not really translate to higher FPS in Quake3 or more realistic flightsims. You don't get quantum computers that have amazing SPECfp numbers.
Quantum computers do operations that normally take one order of magnitude in a much lower order time. Example: searching a list of items for a value on von Neumann machine is O(n) (length of the list), since you have to look at each element till you find the one you want. You can do this in O(1) on a parallel machine. This is a significant improvement. IIRC there was a quantum computer that could search a 4-element list in O(1).
Obviously, that's a pretty trivial problem. Even for very long lists, O(n) isn't bad, and you can do it in parallel.
What about fundamentally much more complex problems, such as factoring, or better, something NP-complete such as circuit-sat or Hamilton paths (that's what the article was talking about, I think. Those guys think their quantum computer is a Hamilton oracle, if I'm right. So you have to pose questions in the form of graphs...not a serious problem since all NP is orthogonal). A parallel machine doesn't help there. But a quantum computer can take NP problems from exponential to polynomial time.
All of a sudden factoring (not NP, just decently hard) goes from taking 100 trillion years to taking hours.
Yes, all encryption that uses factoring as a trapdoor (one-way function) would be toast.
No, it wouldn't necessarily be any better at running first person shooters.
Still, an NP oracle machine IMHO would be much more significant than some bloody nanotech robots.