A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algorithm can be expressed formally as a [1] particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model.

Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on transition matrices. That is, a matrix can be specified whose product with the matrix representing a classical or probabilistic machine provides the quantum probability matrix representing the quantum machine.

A machine or programming language is called Turing complete, if it can simulate all Turing machines. Thus, non-deterministic Turing machines are Turing complete, because they can simulate a Turing [2] machine by simply not using non-determinism. Interestingly enough, a deterministic Turing can simulate a non-deterministic one, simply by trying all possible outcomes of non-deterministic results sequentially. This is a brute force approach and not very efficient. It is unclear if there is an efficient way to do it. BTW, most computer scientist do not think that it can be done.

As for your own answer to this - Turing machines are supposed to halt. In this context it means that the computation is finished and has a result. You might think it means that the machine gets frozen. But it is the other way round. A frozen machine did not halt, when it was supposed to and know you are waiting forever figure 1 shown below and cannot do anything (but reboot). Non-determinism has no effect on a machine halting or not.

Figure1: Turning Machine

The standard popular-news account of quantum computing is that a quantum computer (QC) would work by splitting into exponentially many noninteracting parallel copies of itself in different universes and having each one attempt to verify a different certificate, then at the end of the calculation, the single copy that found a valid certificate "announces" its solution and the other branches magically vanish.

People who know anything about theoretical quantum computation know that this story is absolute nonsense, and that the rough idea described above more closely corresponds to a nondeterministic Turing machine (NTM) than to a quantum computer. Moreover, the compexity class of problems efficiently solvable by NTMs is NP and by QCs is BQP, and these classes are not believed to be equal.

But I've never seen anyone explicitly point out that there is another way in which the popular characterization is wrong, which goes in the other direction. BQP is believed to be not a strict subset of NP, but instead [3] incomparable to it. There exist problems like Fourier checking which are believed to not only lie outside of NP, but in fact outside of the entire polynomial hierarchy PH. So with respect to problems like these, the popular narrative actually understates rather than overstates the power of QCs.

My naive intuition is that if we could "choose what to measure", then the popular narrative would be more or less correct, which would imply that these super-quantum-computers would be able to efficiently solve exactly the class NP. But we believe that this is wrong; in fact PostBQP=PP, which we believe to be a strict superset of NP.

Is there any intuition for what's going on behind the scenes that allows a quantum computer to be (in some respects) more powerful than a nondeterministic Turing machine? Presumably this "inherently quantum" power, when combined with postselection (which in a sense NTMs already have) is what makes a super-QC so much more powerful than a NTM. (Note that I'm looking for some intuition that directly contrasts NTMs and QCs with postselection, without "passing through" the classical complexity class PP.)

References:

1. https://en.wikipedia.org/wiki/Quantum_Turing_machine
2. https://softwareengineering.stackexchange.com/questions/150332/quantum-computers-and-turing-machine
3. https://quantumcomputing.stackexchange.com/questions/1359/why-is-a-quantum-computer-in-some-ways-more-powerful-than-a-nondeterministic-tur

Cite this article:

S. Nandhinidwaraka (2021) Quantum Turing Machine-Uses and Benefits, AnaTechmaz, pp.9