A quantum Turing machine (QTM), also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a particular quantum Turing machine. Such Turing machines were first proposed in a 1985 paper written by Oxford University physicist David Deutsch suggesting quantum gates could function in a similar fashion to traditional digital computing binary logic gates.
Quantum Turing machines are not always used for analyzing quantum computation; the quantum circuit is a more common model; these models are computationally equivalent.
Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on transition matrices, shown by Lance Fortnow.
Iriyama, Ohya, and Volovich have developed a model of a Linear 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.
A quantum Turing machine with postselection was defined by Scott Aaronson, who showed that the class of polynomial time on such a machine (PostBQP) is equal to the classical complexity class PP.
Famous quotes containing the words quantum and/or machine:
“But how is one to make a scientist understand that there is something unalterably deranged about differential calculus, quantum theory, or the obscene and so inanely liturgical ordeals of the precession of the equinoxes.”
—Antonin Artaud (1896–1948)
“The white man regards the universe as a gigantic machine hurtling through time and space to its final destruction: individuals in it are but tiny organisms with private lives that lead to private deaths: personal power, success and fame are the absolute measures of values, the things to live for. This outlook on life divides the universe into a host of individual little entities which cannot help being in constant conflict thereby hastening the approach of the hour of their final destruction.”
—Policy statement, 1944, of the Youth League of the African National Congress. pt. 2, ch. 4, Fatima Meer, Higher than Hope (1988)