A quantum computer (or quantum Turing machine or quantum circuit) cannot solve any problem that a classical computer could not, because one can simulate the other
Initially in a comment I had proposed that Deutsch was "engaged in hyperbole". Truth-be-told, I think that, in all likelihood, Deutsch and Feynman and others certainly knew that their quantum computers were more powerful than classical computers, but didn't have the language to describe the particular power afforded by them. Hence they defaulted with statements that could be read as saying that quantum computers are more powerful in the Turing-sense of the word. But I don't think Deutsch (or Feynman) intended to exaggerate their quantum simulators in the manner suggesting that they were broader than classical computers insofar as being able to solve the Halting problem.
Secondly I'm not sure if Deutsch really had much of a distinction between his quantum Turing machine and a "universal quantum computer". Certainly he described a quantum Turing machine as having the tape be held in superposition, and also constructively programmed a (universal) quantum computer by giving Algol-pseudocode to run the EPR experiment. But, just as no one programs a classical computer with a Turing machine (except as a bit of a sport), no one would program a quantum computer with a quantum Turing machine.
Also, Deutsch and Feynman worked for a while in the circuit model (while Bernstein and Vazirani initially used the quantum Turing model). But there is a small catch in the circuit model - both classical and quantum! - where we have to be careful not to embed an uncomputable problem into our definition of the circuit. This is the "uniformity condition" that Andrew Yao glossed over but that was corrected later after Shor's algorithm.
But using your definitions, at least we have that the following are equivalent:
- $RE$, the class of all problems solvable with a classical computer
- $QTM$, the class of all problems solvable with a (universal) quantum Turing machine
- $QUC$, the class of all problems solvable with a universal quantum computer
- $QC$, the class of all problems solvable with a quantum circuit
To show that two classes $A$ and $B$ are equivalent, it suffices to show that $A$ can be simulated by $B$, and that $B$ can be simulated by $A$.
I would broadly prove this as follows:
- Yao showed that a quantum circuit is equivalent to a quantum Turing machine by patiently showing how one could simulate the other;
- Feynman showed that a quantum circuit can simulate a classical circuit, at least because of the unitarity of, and classical universality of, the CCNOT (Toffoli) gate and/or the CSWAP (Fredkin) gate; and
- Schrodinger initially showed that we can classically simulate a quantum circuit just by keeping track of the wavefunction, while Feynman improved this to show that it suffices to look at the Feynman path integral.
Because a quantum circuit can be simulated by a classical computer, just by updating the wavefunction after each gate, we cannot use the quantum circuit to solve the Halting problem. For, if we did, then we could use the classical computer to simulate the quantum circuit to solve the Halting problem, in violation of Turing's theorem.