What are the differences between the model of computation that a quantum computer uses and Turing model?

The http://en.wikipedia.org/wiki/Quantum_Turing_machine is one of the models for quantum computation, and is probably the easiest way to understand the differences from the conventional http://en.wikipedia.org/wiki/Turing_machine. As is typically done in quantum computing, 0s and 1s are replaced by two-level quantum states, which collapse to one of those levels when measured. The hard part in working with quantum states is that multibit states (that generalize the conventional 00111) cannot be split into individual bits when they are entangled (which is typical). This is a "runtime" effect and does not correspond to any additional "wires" connecting the bits. In a quantum computer, you can only pass by reference because copying is not allowed (unless you copy into a 0-initialized scratchpad). You can modify a variable, or swap two values, but you can't just write an arbitrary value into a variable, unless you know the variable was 0-initialized. If two physically different variables are entangled, then changing one can automatically change the other. For example, if something happens to an intermediate variable you used a while back, this may corrupt the entire computation. The power of quantum computing can be traced to effect of quantum superposition - you can represent many conventional states at once (sort of) and operate on all of them with one instruction at a time. The problem is that you can't read all the results - you can only collect statistics (like the sum of the results). This is handy for a few problems. Say, in quantum number-factoring you can take a superposition of all 1000-bit numbers and do some arithmetic operations on them. At the end, you can produce about 1000 bits of information (which a lot smaller than one per possible number). Choosing those bits wisely leads to useful algorithms.

You should check out the wiki page on http://en.wikipedia.org/wiki/Quantum_algorithm , which says in part: All problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable using classical computers remain undecidable using quantum computers. What makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms.

There's two senses in which computer scientists talk about a computer being able "to do" something. The first describes physical operations a computer does -- copy this data over there, add these numbers together, and so on. In this sense, has a good overview of what a QTM is, and what operations it can do. The second, in the sense of http://en.wikipedia.org/wiki/Computability_theory, describes the problems a computer could solve, not in one step, but after some (finite) number of smaller operations. In this sense, is correct that a QTM can solve exactly the same problems that a classical TM can, no more or less. A related notion asks not just whether a computer is capable of solving problems at all, but whether it's capable of solving them (asymptotically) quickly. It is in this sense that algorithms are known that are believed (but not proved!) to separate the capabilities of quantum computers and classical ones. By and large, these speedups are derived from the ability to perform unitary operations on suitably prepared superpositions of states. Unfortunately, you can only extract the result of such a "computation" by entangling certain states and forcing probability amplitudes to cancel, so the resulting computation doesn't, as is often believed, resemble "doing lots of parallel computations" so much as a very different conceptual model of computation. Okay, that got very technical by the end. I'm sorry. A final, nontechnical note: You're right that it is not known whether or not there exists a classical polynomial-time algorithm for factoring, and this cannot be stressed enough. While no one's discovered one yet, the existence of one has not been demonstrated to be impossible, and in fact, there is no proof that quantum computers are capable of solving any problem faster than classical ones. Now, it is strongly suspected by the complexity-theory community that they are, but no one has yet demonstrated a problem where we can prove that there isn't a classical algorithm that's just as fast as our best quantum ones -- all we know so far is that it's easy to make quantum computers go fast.