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)
“A multitude of little superfluous precautions engender here a population of deputies and sub-officials, each of whom acquits himself with an air of importance and a rigorous precision, which seemed to say, though everything is done with much silence, “Make way, I am one of the members of the grand machine of state.””
—Marquis De Custine (1790–1857)