量子图灵机

此词条暂由彩云小译翻译，翻译字数共319，未经人工整理和审校，带来阅读不便，请见谅。

基础定义

A quantum Turing machine (QTM) or universal quantum computer is an abstract machine 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 is a more common model.

量子图灵机计算机(QTM)又称为通用量子计算机是一种用来模拟量子计算机效果的抽象机器。虽然它是一个简单的模型，但它能展现出量子计算的所有威力，因为任何量子算法都可以被形式化地表示为一个特定的量子图灵机。尽管说提供等效计算能力的量子电路是一种更常用的模型。

与经典计算的关系

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.

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.

通过过渡矩阵，量子图灵机可以与经典图灵机和概率图灵机相关联。兰斯 · 福特诺（Lance Fortnow）证明，量子图灵机的量子概率矩阵可以被拆解成是指定矩阵与经典或概率图灵机的矩阵的乘积。

通俗定义

A way of understanding the quantum Turing machine (QTM) is that it generalizes the classical Turing machine (TM) in the same way that the quantum finite automaton (QFA) generalizes the deterministic finite automaton (DFA). In essence, the internal states of a classical TM are replaced by pure 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.

我们可以通过类比确定有限自动机（deterministic finite automaton）到量子有限自动机（quantum finite automaton）的转化来理解经典图灵机到量子图灵机的转化。 他们的差异在于，经典图灵机讨论的状态被推广到了希尔伯特空间（Hilbert space）中。希尔伯特空间是完备的内积空间，是有限维欧几里得空间的一个推广。它不局限于实数的情形和有限的维数，但又不失完备性。转换函数被一组映射 Hilbert 空间到自身的酉矩阵取代。

That is, a classical Turing machine is described by a 7-tuple [math]\displaystyle{ M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle }[/math].

经典图灵机可以被一个七元有序组所描述，[math]\displaystyle{ M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle }[/math]。

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.

Iriyama、 Ohya 和 Volovich 开发了一个线性量子图灵机模型(LQTM)。这是一个具有混合状态并允许不可逆转换函数的经典 QTM 的推广。这使得量子测量可以在没有经典结果的情况下进行表示。

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):

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.

一个具有后选择的量子图灵机由 Scott Aaronson 定义，他证明了这样一个机器上的多项式时间类(PostBQP)等于经典的复杂性类 PP。

• The set of states [math]\displaystyle{ Q }[/math] is replaced by a Hilbert space.

• The tape alphabet symbols [math]\displaystyle{ \Gamma }[/math] are likewise replaced by a Hilbert space (usually a different Hilbert space than the set of states).

• The blank symbol [math]\displaystyle{ b \in \Gamma }[/math] corresponds to the zero-vector.

• The input and output symbols [math]\displaystyle{ \Sigma }[/math] 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 [math]\displaystyle{ \delta : \Sigma \times Q \otimes \Gamma \rightarrow \Sigma \times Q \otimes \Gamma \times \{L,R\} }[/math] is a generalization of a transition monoid, and is understood to be a collection of unitary matrices that are automorphisms of the Hilbert space [math]\displaystyle{ Q }[/math].

• The initial state [math]\displaystyle{ q_0 \in Q }[/math] may be either a mixed state or a pure state.

• The set [math]\displaystyle{ F }[/math] of final or accepting states is a subspace of the Hilbert space [math]\displaystyle{ Q }[/math].

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 published papers that first described a quantum mechanical model of Turing machines. A 1985 article written by Oxford University physicist David Deutsch further developed the idea of quantum computers by suggesting quantum gates could function in a similar fashion to traditional digital computing binary logic gates.

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.

See also

Category:Turing machine

类别: 图灵机

• Quantum simulator § Solving physics problems

Category:Quantum complexity theory

范畴: 量子复杂性理论

This page was moved from wikipedia:en:Quantum Turing machine. Its edit history can be viewed at 量子图灵机/edithistory