A quantum Turing machine (QTM) or universal quantum computer is an
abstract machine
An abstract machine is a computer science theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is analogous to a mathematical function in that it receives inputs and produces outputs based on pr ...
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 particular quantum Turing machine. However, the computationally equivalent
quantum circuit
In quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence of quantum gates, measurements, initializations of qubits to known values, and possibly o ...
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. This was shown by
Lance Fortnow.
Informal sketch
A way of understanding the quantum Turing machine (QTM) is that it generalizes the classical
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
(TM) in the same way that the
quantum finite automaton
In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of a ...
(QFA) generalizes the
deterministic finite automaton
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state autom ...
(DFA). In essence, the internal states of a classical TM are replaced by
pure
Pure may refer to:
Computing
* A pure function
* A pure virtual function
* PureSystems, a family of computer systems introduced by IBM in 2012
* Pure Software, a company founded in 1991 by Reed Hastings to support the Purify tool
* Pure-FTPd, F ...
or
mixed states in a
Hilbert space; the transition function is replaced by a collection of
unitary matrices that map the Hilbert space to itself.
That is, a classical Turing machine is described by a 7-
tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
.
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
is replaced by a
Hilbert space.
* The tape alphabet symbols
are likewise replaced by a Hilbert space (usually a different Hilbert space than the set of states).
* The blank symbol
is an element of the Hilbert space.
* The input and output symbols
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.
* The
transition function is a generalization of a
transition monoid In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output. It consists of a set ''Q'' of states, a set Σ called the input alphabet, and a function ''T'': ''Q'' × Σ → ''Q'' ...
and is understood to be a collection of
unitary matrices that are
automorphisms of the Hilbert space
.
* The initial state
may be either a
mixed state or a
pure state
In quantum physics, a quantum state is a mathematical entity that provides a probability distribution for the outcomes of each possible measurement on a system. Knowledge of the quantum state together with the rules for the system's evolution in t ...
.
* The set
of ''final'' or ''accepting states'' is a subspace of the Hilbert space
.
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 a
measurement 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.
History
In 1980 and 1982, physicist
Paul Benioff
Paul Anthony Benioff (May 1, 1930 – March 29, 2022) was an American physicist who helped pioneer the field of quantum computing. Benioff was best known for his research in quantum information theory during the 1970s and 80s that demo ...
published articles that first described a quantum mechanical model of
Turing machines
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algor ...
. A 1985 article written by Oxford University physicist
David Deutsch
David Elieser Deutsch ( ; born 18 May 1953) is a British physicist at the University of Oxford. He is a Visiting Professor in the Department of Atomic and Laser Physics at the Centre for Quantum Computation (CQC) in the Clarendon Laboratory of ...
further developed the idea of quantum computers by suggesting that
quantum gate
In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, lik ...
s could function in a similar fashion to traditional digital computing
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
logic gates
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate ...
.
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 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 \operatorname /math> to the conditional ...
'' was defined by
Scott Aaronson
Scott Joel Aaronson (born May 21, 1981) is an American theoretical computer scientist and David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin. His primary areas of research are quantum computing a ...
, who showed that the class of polynomial time on such a machine (
PostBQP) is equal to the classical complexity class
PP.
[ Preprint available a]
See also
*
Quantum simulator#Solving physics problems, Quantum simulator § Solving physics problems
References
Further reading
*
*
*
External links
The quantum computer – history
{{quantum computing
Turing machine
Quantum complexity theory