Quantum Turing machine
Encyclopedia
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 gate
s 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
.
Abstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
used to model the effect of a quantum computer
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm
Quantum algorithm
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a...
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
David Deutsch
David Elieser Deutsch, FRS is an Israeli-British physicist at the University of Oxford. He is a non-stipendiary Visiting Professor in the Department of Atomic and Laser Physics at the Centre for Quantum Computation in the Clarendon Laboratory of the University of Oxford...
suggesting quantum gate
Quantum gate
In quantum computing and specifically the quantum circuit model of computation, a quantum gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.Unlike many classical...
s could function in a similar fashion to traditional digital computing binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
logic gates.
Quantum Turing machines are not always used for analyzing quantum computation; the quantum circuit
Quantum circuit
In quantum information theory, a quantum circuit is a model for quantum computation in which a computation is a sequence of quantum gates, which are reversible transformations on a quantum mechanical analog of an n-bit register...
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
Lance Fortnow
Lance Jeremy Fortnow is a computer scientist in the field of computational complexity and its applications, notable for producing major results on interactive proof systems.-Biography:...
.
Iriyama, Ohya
Masanori Ohya
is a Japanese mathematician.After he revieved a Ph.D. in Mathematical Physics and Information Science and Dr.Sc., he continuously worked on operator algebra, Quantum Entropy, quantum information theory and bio-information. He achieved results in the fields of Quantum Information and mathematical...
, 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
Postselection
In probability theory, to postselect is to condition a probability space upon the occurrence of a given event. In symbols, once we postselect for an event E, the probability of some other event F changes from Pr[F] to the conditional probability Pr[F|E].For a discrete probability space, Pr[F|E] =...
was defined by Scott Aaronson
Scott Aaronson
Scott Joel Aaronson is a theoretical computer scientist and faculty member in the Electrical Engineering and Computer Science department at the Massachusetts Institute of Technology.-Education:...
, who showed that the class of polynomial time on such a machine (PostBQP
PostBQP
PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error ....
) is equal to the classical complexity class PP
PP (complexity)
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
.