Stories
Slash Boxes
Comments
typodupeerror delete not in
  • Preferences

Comments: 1 +-   The Limits of Quantum Computing on Monday February 18 2008, @01:01PM The Narrative Fallacy

Submitted by The Narrative Fallacy on Monday February 18 2008, @01:01PM
supercomputing
The Narrative Fallacy writes "Scott Aaronson has posted a draft of his article from this month's Scientific American on the limitations of quantum computers (pdf) discussing the question: Will quantum computers let us transcend the human condition and become as powerful as gods or are they a physical absurdity destined to be exposed as the twenty-first century's perpetual-motion machine? Aaronson says that while a quantum computer could quickly factor large numbers, and thereby break most of the cryptographic codes used on the Internet today, there's reason to think that not even a quantum computer could solve the crucial class of NP-complete problems efficiently. Aaronson contends that any method for solving NP-complete problems in polynomial time may violate the laws of physics and that this may be a fundamental limitation on technology no different than the second law of thermodynamics or the impossibility of faster-than-light communication."
submission
This discussion was created for logged-in users only, but now has been archived. No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

The Limits of Quantum Computing 1 Comment More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.
  • It seems as if most of the readers of Slashdot think quantum computers are the same as nondeterministic computers. Well, they are not. Nondeterministic Turing Machines (NTMs) are those that follow every computational path simultaneously and accepts if any path accepts. Quantum computers are more like Probabilistic TMs, which take a random branch at every step. The problems solvable in polynomial time by NTMs define NP, and RTMs define RP. The classes x-complete are the "hardest" of the problems in the
Search
In this world some people are going to like me and some are not. So, I may as well be me. Then I know if someone likes me, they like me.

All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.