In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "became the first machine ever to perform non-trivial computations that no Turing machine could perform".
My question: Do we really know that quantum computing is powerful enough to solve problems that not even Turing machines can solve? (Or is this just a personal belief of David Deutsch?)
While it is true that the computation of a quantum Turing machine is vastly different from that of a classical one, nevertheless quantum Turing machines can be simulated on a classical Turing machine, albeit with exponential slowdown. In particular, everything that can be computed on a quantum Turing machine can also be computed on a classical Turing machine.
The main advantage of quantum Turing machines is that they appear to solve some problems much faster than classical Turing machines. As Sasho comments, at the moment we can't quite prove this, yet this advantage is believed to hold by most researchers.
For more, check out this talk by Ashley Montanaro.
There's no difference in terms of computability. Classical computers can simulate quantum computers. A Turing machine can compute anything that a quantum computer can compute.
This isn't some hypothetical point, we simulate quantum computations all the time. You can do it with pen and paper! It's a lot more convenient using one of the many software simulators that already exist, though. There's even toy ones that run in your browser.
To me, your David Deutsch quote is referring to the style of computation that was used, as opposed to some inaccessible aspect of the problem. He managed to phrase it terribly.
All that being said, be aware that there is a difference in efficiency. Although a Turing machine can simulate applying Shor's algorithm to a thousand digit number, doing so would take too long to be practical. The universe would die out before you finished.
(There are also other practical uses for quantum computers, like improving the resolution of sensors, but I think mostly people are interested because of the existence of a few key takes-too-long-to-simulate problems and algorithms.)
In terms of computability, quantum computers provide no advantage -- anything which can be computed by a quantum computer may be computed by a classical computer, because as Yuval pointed out, classical computers can simulate quantum computers.
In terms of complexity, there are advantages for some problems. For example, the Deutsch-Josza algorithm is (provably) exponentially faster than any classical algorithm. Grover's algorithm provides a quadratic speedup compared to any classical computer, again this has been proved. However, the precise complexity relationship between classical and quantum computing is not known.
As far as we believe, a quantum Turing machine is able to simulate any quantum computer, and it is also equivalent to classical deterministic Turing machine in terms of computability. In other words, as far as we know the space of problems solvable by quantum computers is the same as space of problems solvable by classical computers.
However, if we consider practical computability, things may look a bit different. Imagine a problem where we have a classical solution which runs with $O(2^n)$ complexity. It is definitely solvable, but for any reasonable data size it will require massive amounts of operations. In practice, it will run for thousands of years, even on the fastest computers. Now imagine we have a quantum algorithm solving the same problem, but with $O(n)$ complexity. Out of a sudden, exact same problem can be solved in minutes, which is very reasonable (especially compared to thousands of years).
I think the original quote could be extended by adding "in any reasonable time", and we get a fair statement.
In the generality that your question is asked, the answer is YES. Quantum computation is a very wide concept. Even in non-quantum computation there are many models that go beyond Turing computability. The field is sometimes called hypercomputation. A (in my opinion) nice model are red-green Turing machines by J. van Leeuwen and J. Wiedermann. With them you can climb up several steps in the arithmetical hierarchy. A more classical model are oracle machines.
You can define the same approches with Quantum Turing Machines, and then they compute more than a Turing machine. So again, the answer is YES, but also non-quantum models can do that.
If you only want to compare TMs to quantum TMs (which both compute only the Turing-computabel) or some other model of quantum computation, then you should refer to that model explicitly.
