The Limits of Quantum Computing 228
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."
Stupid much? (Score:1, Informative)
Re:Stupid much? (Score:5, Informative)
Re:Having actually read the article, a question (Score:4, Informative)
and lay off the trolling.
NP-Complete Problems (Score:4, Informative)
Re:Having actually read the article, a question (Score:5, Informative)
The (fundamental) difference is that the bits in the DRAM cells are in a well-defined state of either 0 or 1, but you just haven't measured them yet. In the quantum computer, the qubits are in a superposition of 0 and 1 at the same time.
To be more precise, the 'state space' of a classical bit is, well, 1 bit. Either 0 or 1. In the scenario that you describe, you don't know what the bits are until you measure them, but that is nothing special (imagine another example: tossing a coin with your eyes closed. You don't know the outcome until you open your eyes, but that doesn't mean that anything quantum-mechanical is going on!).
The 'state space' of a qubit, on the other hand, is an angle. Put the '0' result along the x axis and the '1' result along the y axis. Angle 0 corresponds to '0', 90 degrees corresponds to '1', and so on. But the possible physical state is anywhere on the unit circle, not just '0' and '1'. If the physical state of the system is 45 degrees then it really is a mixture of '0' and '1', and you can do interesting things with this state. For example, you can add it to some other state (at a different angle) and get wave-like interference effects.
Re:NP complete is solved by nature (Score:5, Informative)
Maybe you're thinking of the often repeated claim that one can find a Steiner tree (the determination of which is NP-complete) using soap and a physical setup. But that, too [scottaaronson.com], is false.
Kieu tried to find a way to make quantum trickery (in ordinary quantum computers) calculate NP-complete problems (and a lot more) in polynomial time, but his hypercomputation algorithm was later disproved. So just as P = NP in classical computing seems to be very hard to prove or disprove in the general case, so appears its quantum mechanical analog to be, as well. (But as the paper states, some computers using exotic physics could be able to solve NP-complete problems easily; for instance, a time-traveling computer could solve PSPACE-complete problems without much difficulty, and if loop quantum gravity is true, a computer making use of it might be able to solve NP-complete problems as well.)
Re:Seems to me... (Score:4, Informative)
If all else fails, it's back to the days of number stations and couriers, since symmetric crypto will resist quantum computers fairly well (just double the key size to thwart Grover's algorithm [wikipedia.org]).
Re:NP-completeness (Score:5, Informative)
What the fuck?! I would outraged when this was at +4, but +5?!
This is misleading. NP-completeness relates to how other problems can be reduced to it. Currently we can't say much about how NP-completeness and complexity relate. We know that if a problem is NP-complete, it must take at least polynomial time and at most exponential time (on a classical computer), but beyond that, we know nothing.
This is factually incorrect. So far we have not found a quantum algorithm to solve any NP-complete problem in less than exponential time.
Ha!
This is factually incorrect. Perhaps you're getting confused by the fact that quantum algorithms are often described in circuit notation. Classical algorithms are also sometimes described in circuit notation, but this is much less common. In any case, quantum algorithms do not bound the size of the input any more than classical computers do.
For instance, quicksort on a classical computer might be "bounded" in that you cannot sort an array of 50 billion petabytes. This is not inherent in the algorithm; it's inherent in our inability to construct a computer with 50 billion petabytes of memory. Similarly, we have not been able to use quantum computers to date to factor integers larger than 15. This limit is not inherent in the algorithm; it's inherent in the fact that engineers have not been able to construct a viable quantum computer to date with more than 5 (if I remember correctly) qubits.
Again, quantum algorithms to not bound the size of their input.
This is factually incorrect. Almost all of the research into quantum computation in the past 10 years has been in the area of quantum complexity. Perhaps you have heard of the BQP complexity class [wikipedia.org], which was mentioned in the article you were supposed to have read. By the way, BQP can in some way be thought of as quantum computers' "P"; i.e., the class of problems which can viably be computed on a quantum computer in polynomial time.
Quantum complexity very much uses big-O notation (as well as big- notation and any other complexity notation used in classical complexity theory).
Non sequitur. It's not clear at this point. If you could answer that question, you'd probably be drowning in money right now.
Re:NP complete is solved by nature (Score:5, Informative)
All you've done is parallelize the problem. Each string is its own highly limited computer. You'll note that to scale to larger graphs, you need to scale the number of strings. That is, you kept the running time the same but had to increase the power of the computer in proportion to the number of edges. Each bead, as a place where forces are summed, also represents a limited power computer. Diskstra's algorithm runs in roughly O(V^2) time when E is comparable to V^2, or O(E*log(V)) time when it's much lower. Not coincidentally, your physical computer's computational power grows at comparable rates.
Physics doesn't make a particularly more or less efficient computer than a Turing machine; there's no good comparison. What it does do is provide ways to massively parallelize some problems. The shortest path algorithm can be done in O(edges in path) time on a conventional computer with unlimited processors and no communications bottlenecks, which is very similar to what you have described.
Re:Not all encryptions are prime-based (Score:5, Informative)
I wondered the same thing. I've talked to several experts and have been told that, indeed, a quantum computer can break elliptic curve encryption efficiently. This [psu.edu] paper, for example, seems to cover adapting Shor's algorithm to breaking elliptic codes.
Re:As usual (Score:2, Informative)
From a mathematic point of view, solving an NP-complete problem in polynomial time is not a problem at all. The class NP is defined as the set of problems that a non-deterministic Turing machine can solve in polynomial time.
Background Info (Score:5, Informative)
These are very informal definitions. Look at
http://en.wikipedia.org/wiki/Nondeterministic_Turing_machine [wikipedia.org]
http://en.wikipedia.org/wiki/Probabilistic_Turing_machine [wikipedia.org]
http://en.wikipedia.org/wiki/Quantum_computer#Quantum_computing_in_computational_complexity_theory [wikipedia.org]
for more details.
And yes, I am a mathematician.
Re:Not all encryptions are prime-based (Score:2, Informative)
Re:Best metaphor ever (Score:2, Informative)