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

Seems to me...

[Smordnys s'regrepsA]

What does it matter if it is perfect or not? Seems to me that it is much better than what we're working with now.

If we want to start talking in that tone, well our "micro" processors and new fangled technologies didn't solve the mysteries of the universe, so we should have stuck with computers the size of buildings that have trouble doing more than adding, subtracting, and multiplying. Hell - they were good enough to design the atomic bomb and our space program, and that's good enough for me!


Besides, does anyone seriously think that we'll gain God-Like-Powers from quantum computing? The only God Mode I expect from the computer starts with the phrase 'iddqd'.

Nothing in between????

[syousef]

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?

No, they won't let us defy physical laws and become omnipotent. No, quantum mechanics, being a whole class of physical laws, isn't going to have absolutely no practical use. How about something in between that doesn't come from the over-used plot of a bad sci-fi show?

Re:Seems to me...

[mrbluze]

Besides, does anyone seriously think that we'll gain God-Like-Powers from quantum computing? The only God Mode I expect from the computer starts with the phrase 'iddqd'.

If I were offered a single magic power over the physical world it would be either invisibility or the ability to see behind walls. If quantum computing means whoever has it can bust all the crypto's in a realistic time (eg: a second or two), then we have a problem, because that group of people will have God Mode when it comes to money, intelligence, all that. Worse is if we don't know they have quantum computing, then all our shit is belong to them.

If quantum computing means they can break a crypto in a month whereas before it took them forever, there is hope in that quantum computing will become prevalent before anyone is able to totally compromise all communications. Of course I'm guessing there is no such agency that can do this yet.

Re:As usual

[Brian Gordon]

Aaronson contends that any method for solving NP-complete problems in polynomial time may violate the laws of physics

Is this supposed to be informative in any way? Yes, that's one of the angles on the P=NP problem. No, you still haven't made any progress on it so it doesn't matter what you "contend".

Re:The last question...

[sqrt(2)]

Not the first time I've read this, and I'm sure most people here are already familiar with it along with Asimov's other works.

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? The biblical tie in is a convenient reconciliation of science and (mostly Christian creation myth) religion, but it's a cheat. It doesn't actually answer any questions at all. It is something interesting to think about though.

Re:Protein's fold in real time.

[snkline]

You are confused as to what NP-complete means. It isn't that a protein folding is "NP-complete", but the algorithm for generally calculating protein folding is.

Re:NP-completeness

[Trivial_Zeros]

The input has a constant size, and the computation is bound by some constant time.

If you want to be technical like that, your current computer is a finite state machine (it doesn't even support true Turing algorithms as these in the general case require an infinite tape). Any input/output to computations is bounded by the size of your cache, memory and disk space. You could try and say that net access grants more storage, but this is still technically a) finite and b) bound by low seek times.

The first generation of computers had low storage / computation space. They grew as engineering progressed. It's the same deal with quantum computers. Five to seven qbits today may turn into 32, 64.. and larger. A quantum computer with "only" 512 qbits could be solving a problem that would normally require 2^512 = 10^154 work (which is more atoms in the universe) is amazing.

Re:NP complete is solved by nature

[somersault]

I .. fail to see how you can call it 'poor' until you have a better alternative? Electricity moves fast, is portable via batteries, can run at any scale from the power grid level down to the microprocessors.. there is no other mobile medium that we can control that would be better, other than light, other small particles, magnetism.. all would still require electricity in the system to control any mechanical parts or power whatever is generating the particles or forces involved. I'm trying to see your viewpoint but I just can't dismiss something a poor idea unless I know that there are better ways to do the same thing - unless perhaps the idea is life threatening or otherwise stupid, but in this case it's proven to be quite effective so far.

Re:Nothing in between????

[DarenN]

"Technology as magic" is a well explored theme - from quotes such as "any sufficiently advanced technology is indistinguishable from magic" to Babylon 5.

My favourite description of technology, though, is Strongbad's here: http://www.homestarrunner.com/sbemail143.html [homestarrunner.com]

Don't Panic!

[LrdDimwit]

Forty two.

Re:Having actually read the article, a question

[JTeutenberg]

In brief, the answer is yes, you can use a variation of fuzzy logic to emulate a quantum computer. Unfortunately no complexity gains can be made as the emulation cannot exploit a superposition to calculate in parallel.

While both a fuzzy bit and a qubit could have a state like 0(75%) 1(25%), having a computer perform a fuzzy operation requires two computations (one for each possible state) whereas a quantum computer can apply a single operation to the qubit and have it affect both states.

One difference however, is that for qubits the weights on each state are complex (as opposed to real-valued). This means that interference can occur when, for example, the weights on two qubits being combined have the same magnitude but opposite phase. The true awesome magic of Shor's algorithm is how the computation expands into a massive superposition (parallel computation) and then manages to exploit the interference to return to just a single possible answer before it comes time to measure.