Question: are quantum computers a type of Turing machine or something else?

Question

I read that in quantum computations you can not examine the internal state of the computation while it is happening. This is something I thought is always possible with Turing machines. Does this mean that quantum computers are not Turing machines? Also as an extra question: If not then what languages do they recognize in the sense of the hierarchy of language grammars?

Answer 1

Quantum computers are a distinct computation model from Turing machines. However, they have the same "ultimate" power: the languages accepted/recognized by the two coincide (respectively: computable and computably enumerable). This is basically Church's thesis, that no "actual" model of computation can be stronger than Turing machines. (Technically this isn't exactly what CT says, although in my opinion it's ultimately equivalent. The point stands, though.)

Note that this is a very coarse equivalence: for example, each model has a notion of "computation time," and if I look at what languages are accepted/recognized in some bounded amount of time the two models may behave very differently. In general the complexity theories (as opposed to computability theories) of the two models can be extremely different. But that's a separate issue.

Meanwhile, the claim of "unexaminability" of internal states of a quantum computation is an informal gloss on the nature of quantum computation and shouldn't be taken too literally. I'm not an expert so I don't want to get into the details here, but there's nothing magical about the definition of an (abstract) quantum computer.

Answer 2

The Quantum Turing Machine (see, https://en.wikipedia.org/wiki/Quantum_Turing_machine) is indeed a universal model of Quantum Computing. However, the Quantum Circuit model is the more commonly used model.

We cannot ascertain the state of our quantum computation until we measure the state. However, the action of taking a measurement may impact the state. So when analyzing quantum algorithms, we are interested in the probabilities of ending up in certain states upon measurement. In the circuit model, the updated values percolate through the circuit as gates are applied. Measurement operators are treated as gates in the circuit model. For these reasons, the circuit model tends to be a more natural starting point than the Quantum TM.