The Limits of Quantum Computing

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

Comments

Re:Well......

[Thanshin]

It can fix the NP problem.... but u cant look into the PC case or else its ruined. I blamed the dead cat I found inside.

Re:As usual

[Yetihehe]

The truth is a superposition of this two, so thruth is quantum. So could quantum computer uncover the truth? A: Maybe.

Re:Okay Then.

[rucs_hack]

We don't need Quantum computing for a Star Trek futre.

We need a way to disregard or at least completely reinterpret the laws of physics, and do without money, and all get on, and find entire worlds whose populations all conform to some stereotype.

And are green.

Re:Seems to me...

[Anonymous Coward]

there is No Such Agency that can do this yet Are you sure?

Re:faster than light first post!

[Brian Gordon]

Just those pesky relativisic effects.

Re:Okay Then.

[Dutch_Cap]

Luckily, though, tight spandex is a reality today!

Re:The last question...

[z0idberg]

The obvious question would then be, that if all existence is cyclical, how many times has it been reset? And, what kicked it off to begin with?

I don't think there is sufficient data to give a meaningful answer to these questions.

Best metaphor ever

[douglips]

From TFA:

By the
time we reach 100 letters, there are already more possibilities than there are atoms in a
vat of 26^100 atoms.

Wow. Some less creative writers might say "there are more possibilities than there are atoms in the observable universe" or "more possibilities than there are protons in the known universe" or some other colorful metaphor. He goes straight for the "more possibilities than there are possibilities in a vat of 26^100 possibilities". Pure genius.