Aquantum Turing machine (QTM) oruniversal quantum computer is anabstract machine used tomodel the effects of aquantum computer. It provides a simple model that captures all of the power of quantum computation—that is, anyquantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalentquantum circuit is a more common model.^[1][2]: 2

Quantum Turing machines can be related to classical andprobabilistic Turing machines in a framework based ontransition matrices. That is, a matrix can be specified whose product with the matrix representing a classical or probabilistic machine provides the quantumprobability matrix representing the quantum machine. This was shown byLance Fortnow.^[3]

A way of understanding the quantum Turing machine (QTM) is that it generalizes the classicalTuring machine (TM) in the same way that thequantum finite automaton (QFA) generalizes thedeterministic finite automaton (DFA). In essence, the internal states of a classical TM are replaced bypure ormixed states in aHilbert space; the transition function is replaced by a collection ofunitary matrices that map the Hilbert space to itself.^[4]

That is, a classical Turing machine is described by a 7-tuple${\displaystyle M=⟨Q,\mathrm{\Gamma },b,\mathrm{\Sigma },\delta ,q_0,F⟩}$. Seethe formal definition of a Turing Machine for a more in-depth understanding of each of the elements in this tuple.

For a three-tape quantum Turing machine (one tape holding the input, a second tape holding intermediate calculation results, and a third tape holding output):

• The set of states${\displaystyle Q}$ is replaced by aHilbert space.
• The tape alphabet symbols${\displaystyle \mathrm{\Gamma }}$ are likewise replaced by a Hilbert space (usually a different Hilbert space than the set of states).
• The blank symbol${\displaystyle b\in \mathrm{\Gamma }}$ is an element of the Hilbert space.
• The input and output symbols${\displaystyle \mathrm{\Sigma }}$ are usually taken as a discrete set, as in the classical system; thus, neither the input nor output to a quantum machine need be a quantum system itself.
• Thetransition function${\displaystyle \delta :\mathrm{\Sigma }\times Q\otimes \mathrm{\Gamma }\to \mathrm{\Sigma }\times Q\otimes \mathrm{\Gamma }\times \{L,R\}}$ is a generalization of atransition monoid and is understood to be a collection ofunitary matrices that areautomorphisms of the Hilbert space${\displaystyle Q}$.
• The initial state${\displaystyle q_0\in Q}$ may be either amixed state or apure state.
• The set${\displaystyle F}$ offinal oraccepting states is a subspace of the Hilbert space${\displaystyle Q}$.

The above is merely a sketch of a quantum Turing machine, rather than its formal definition, as it leaves vague several important details: for example, how often ameasurement is performed; see for example, the difference between a measure-once and a measure-many QFA. This question of measurement affects the way in which writes to the output tape are defined.

In 1980 and 1982, physicistPaul Benioff published articles^[5][6] that first described a quantum mechanical model ofTuring machines. A 1985 article written by Oxford University physicistDavid Deutsch further developed the idea of quantum computers by suggesting thatquantum gates could function in a similar fashion to traditional digital computingbinarylogic gates.^[4]

Iriyama,Ohya, and Volovich have developed a model of alinear quantum Turing machine (LQTM). This is a generalization of a classical QTM that has mixed states and that allows irreversible transition functions. These allow the representation of quantum measurements without classical outcomes.^[7]

Aquantum Turing machine withpostselection was defined byScott Aaronson, who showed that the class of polynomial time on such a machine (PostBQP) is equal to the classical complexity classPP.^[8]

• Quantum simulator § Solving physics problems

• Molina, Abel; Watrous, John (2018)."Revisiting the simulation of quantum Turing machines by quantum circuits".Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences.475 (2226).arXiv:1808.01701.doi:10.1098/rspa.2018.0767.PMC 6598068.PMID 31293355.
• Iriyama, Satoshi; Ohya, Masanori; Volovich, Igor (2004). "Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm".arXiv:quant-ph/0405191.
• Deutsch, D. (1985). "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer".Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences.400 (1818):97–117.Bibcode:1985RSPSA.400...97D.CiteSeerX 10.1.1.41.2382.doi:10.1098/rspa.1985.0070.JSTOR 2397601.S2CID 1438116.

• The quantum computer – history

• Turing machine
• Quantum complexity theory

• Articles with short description
• Short description matches Wikidata