Originally Posted by
dadev
I'm not a physicist by trade, but do know a thing or two about qed and some things about quantum computing. With how we understand quantum mechanics today, explaining how quantum computer works "in a nutshell" is completely out of the scope for anyone who's asking such question (even without grammar mistakes). That is the harsh truth. Heck, most people wouldn't understand how normal computer works, let alone a quantum one.
Quantum computers are not like classic computers, and their output doesn't look like one of classical computer. They can solve certain problems faster than a classical computer, but with caveats. You never get a straight answer out of it, but a probabilistic one. It's not a real issue in an ideal world, but there are complication in implementation. Also, every problem a classical computer can solve fast, so can a quantum computer, but again in an ideal world where implementation doesn't stand in the way.
With regards to quantum mechanics (qm), it's probably the most exact branch of physics we currently know right after special relativity (but sr is also very simplistic and doesn't try to shoot very far). The set of rules is in fact defined quite well, surprisingly well. The problem is of course intuition, or rather lack of for the uninitiated. I cannot think of any non-statistical physics branch other than sr which has been through more rigor than qm. And no, faster than light local communication is impossible, or otherwise everything we know about physics is incorrect and just an illusion of correctness. Non local communication is a tricky question, and it depends on how qm will integrate with general relativity (gr).
Neither there's a known quantum algorithm that can solve traveling salesman in a reasonable amount of time. It is not known whether such algorithm exists (likely not), but pretty much the same can be said about classical computers. Most computer scientists in the field believe that quantum computers will not allow to solve NPC problems in polynomial time. They can solve those problems faster, but not significantly so when the problem at hand is of exponential complexity.
Where quantum computers can help? Searching in unordered sets is one good example. A quantum computer doesn't need to traverse all elements of the set to find a specific one, this has great application to computer graphics. Quantum computers can also factor integers quickly and do some more number theoretical stuff, but that's mostly for cryptographic use. And it's still not known whether a classical algorithm exists to solve these number problems efficiently, it's just suspected to be so.