更改

此词条由tueryeye翻译审校，未经专家审核，带来阅读不便，请见谅。{{Short description|Model of quantum computation}}

{{#seo:

 

|keywords=量子计算机，量子算法，抽象机器

{{Turing}}

 

}}

== 基础定义 ==

== 基础定义 ==

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.<ref name="equivalence">{{cite conference|author=[[Andrew Yao]]|title=Quantum circuit complexity|conference=34th Annual Symposium on Foundations of Computer Science|pages=352–361|year=1993}}</ref><ref name="newequivalence">{{cite arXiv|eprint=1808.01701|author1=Abel Molina|author2=John Watrous|author-link2=John Watrous (computer scientist)|title=Revisiting the simulation of quantum Turing machines by quantum circuits|date=2018|class=cs.CC}}</ref>

'''量子图灵机 quantum Turing machine (QTM)''' 又称为'''通用量子计算机'''，是一种用来模拟量子计算机效果的抽象机器。尽管说提供等效计算能力的量子电路是一种更常用的模型，但是量子图灵机是一个简单但能展现出量子计算的所有威力的模型。就像经典图灵机可以模拟人类所能进行的任何计算过程一样，量子图灵机可以描述任何量子算法。<ref name="equivalence">{{cite conference|author=[[Andrew Yao]]|title=Quantum circuit complexity|conference=34th Annual Symposium on Foundations of Computer Science|pages=352–361|year=1993}}</ref><ref name="newequivalence">{{cite arXiv|eprint=1808.01701|author1=Abel Molina|author2=John Watrous|author-link2=John Watrous (computer scientist)|title=Revisiting the simulation of quantum Turing machines by quantum circuits|date=2018|class=cs.CC}}</ref>

 

 

== 与经典计算的关系 ==

== 与经典计算的关系 ==

Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on [[Stochastic matrix|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]].<ref name="transition">{{cite journal|author=Fortnow|first=Lance|author-link=Lance Fortnow|year=2003|title=One Complexity Theorist's View of Quantum Computing|url=|journal=Theoretical Computer Science|volume=292|issue=3|pages=597–610|doi=10.1016/S0304-3975(01)00377-2|via=|arxiv=quant-ph/0003035}}</ref>

通过[[过渡矩阵]]，量子图灵机可以与经典图灵机和概率图灵机相关联。Lance Fortnow证明，量子图灵机的量子概率矩阵可以被拆解成是指定矩阵与经典或概率图灵机的矩阵的乘积。<ref name="transition">{{cite journal|author=Fortnow|first=Lance|author-link=Lance Fortnow|year=2003|title=One Complexity Theorist's View of Quantum Computing|url=|journal=Theoretical Computer Science|volume=292|issue=3|pages=597–610|doi=10.1016/S0304-3975(01)00377-2|via=|arxiv=quant-ph/0003035}}</ref>

== 非正式草图定义 ==

== 非正式草图定义 ==

{{Unsolved|physics|Is a [[universal quantum computer]] sufficient to [[Algorithmic efficiency|efficiently]] [[Dynamical simulation|simulate]] an arbitrary physical system?}}

{{Unsolved|physics|通用量子计算机是否能够以高效模拟任意物理系统?}}

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 state|pure]] or [[mixed quantum state|mixed states]] in a Hilbert space; the transition function is replaced by a collection of [[unitary matrix|unitary matrices]] that map the Hilbert space to itself.<ref name="Deutsch1985" />

我们可以通过类比确定有限自动机[[deterministic finite automaton]]到量子有限自动机[[quantum finite automaton]]的转化来理解经典图灵机 Turing machine (TM)到量子图灵机的转化。 他们的差异在于，经典图灵机讨论的状态被推广到了Hilbert空间中。Hilbert空间是完备的内积空间，是有限维欧几里得空间的一个推广。它不局限于实数的情形和有限的维数，但又不失完备性。在量子图灵机中转换函数被一组映射Hilbert空间到自身的酉矩阵 unitary matrix取代。<ref name="Deutsch1985" />

经典图灵机的诞生是因为图灵想用机器来模拟用纸笔进行数学运算的过程，这样的过程可以被看作下列两种简单的动作：

经典图灵机的诞生是因为图灵想用机器来模拟用纸笔进行数学运算的过程，这样的过程可以被看作下列两种简单的动作：

* 在纸带上写上或删除某个符号；

* 在纸带上写上或删除某个符号；

* 把笔尖从纸的一处移动到另一处；

* 把笔尖从纸的一处移动到另一处；

现在我们假设有一条纸带无限长，并且被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。假设我们有一个执笔机器又称为读写头（'''HEAD），'''它本身也可以具有一个状态。就像人今天可能因为某件事心情很好，也可能因为另一件事情很抑郁一样，它的状态会随着它的遭遇所改变。更重要的是执笔机器当前关注的纸上的某个位置的符号和当前的状态决定了下一步的动作。在遇到停止状态<math>F</math>之前执笔机器可以

 

现在我们假设有一条纸带无限长，并且被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。假设我们有一个执笔机器又称为读写头（'''HEAD'''），它本身也可以具有一个状态。就像人今天可能因为某件事心情很好，也可能因为另一件事情很抑郁一样，它的状态会随着它的遭遇所改变。更重要的是执笔机器当前关注的纸上的某个位置的符号和当前的状态决定了下一步的动作。在遇到停止状态<math>F</math>之前执笔机器可以

 

* 1. 写入（替换）或擦除当前符号；

* 1. 写入（替换）或擦除当前符号；

* 3. 保持当前状态或者转到另一状态。

* 3. 保持当前状态或者转到另一状态。

总的来说，经典图灵机可以被一个七元有序组所描述，<math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math>。

总的来说，经典图灵机可以被一个七元有序组所描述，<math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math>。

* <math>Q</math> 为被推广到了Hilbert空间的状态集；

* <math>Q</math> 为被推广到了Hilbert空间的状态集；

* <math>b \in \Gamma</math> 为''空白符''，也是唯一允许出现无限次的字符；

* <math>b \in \Gamma</math> 为''空白符''，也是唯一允许出现无限次的字符；

* 输入和输出符号 <math>\Sigma</math>通常是一个离散集。和经典图灵机的输入输出符号一样，它们不需要是一个量子系统。

* 输入和输出符号 <math>\Sigma</math>通常是一个离散集。和经典图灵机的输入输出符号一样，它们不需要是一个量子系统。

* <math>\delta : \Sigma \times Q  \otimes \Gamma \rightarrow \Sigma \times Q \otimes \Gamma \times \{L,R\}</math>是被推广到了Hilbert空间的转移函数[[State transition system|transition function]]。我们也可以理解它们为一些在Hilbert空间中自同构的酉矩阵[[unitary matrix|unitary matrices]] 。

* <math>\delta : \Sigma \times Q  \otimes \Gamma \rightarrow \Sigma \times Q \otimes \Gamma \times \{L,R\}</math>是被推广到了Hilbert空间的转移函数。我们也可以理解它们为一些在Hilbert空间中自同构的酉矩阵。

* <math>q_0 \in Q</math>是起始状态，它可以是几种状态的混合也可以是一种状态；

* <math>q_0 \in Q</math>是起始状态，它可以是几种状态的混合也可以是一种状态；

* 停止状态<math>F</math>是<math>Q</math>的子集。

* 停止状态<math>F</math>是<math>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 [[quantum measurement|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.

以上只是一个量子图灵机的草图，而不是它的正式定义，因为它的一些重要细节仍然定义模糊：例如，我们以什么样的频率执行对于状态的观测；什么是一次观测量子有限自动机 measure-once和多次观测量子有限自动机 measure-many QFA之间的区别。这些观测问题会影响我们如何定义写入和输出纸带的方式。

==历史==

==历史==

物理学家 Paul Benioff 在1980 年和 1982 年发表的论文中，首次描述了图灵机的量子力学模型。<ref name=":0" /><ref name=":1" /> 牛津大学物理学家 David Deutsch 在 1985 年撰写的一篇文章中进一步推广了量子计算机的概念，他提议量子门[[quantum gate]]应该以类似于传统数字计算二进制逻辑门的方式运行。<ref name="Deutsch1985" />

Scott Aaronson 定义了具有后选择功能的量子图灵机，他证明了这种机器上的时间复杂度类 (PostBQP) 等于经典复杂度 PP。<ref name=":3">{{cite journal|last=Aaronson|first=Scott|year=2005|title=Quantum computing, postselection, and probabilistic polynomial-time|journal=[[Proceedings of the Royal Society A]]|volume=461|issue=2063|pages=3473–3482|doi=10.1098/rspa.2005.1546|bibcode = 2005RSPSA.461.3473A |arxiv=quant-ph/0412187}}  Preprint available at [https://arxiv.org/abs/quant-ph/0412187]</ref>

Iriyama, [[Masanori Ohya|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.<ref name=":2">{{cite journal|title=Classically-Controlled Quantum Computation|date=2007-04-04|pages=601–620|author1=Simon Perdrix|author2=Philippe Jorrand|volume=16|journal=Math. Struct. In Comp. Science|arxiv=quant-ph/0407008|doi=10.1017/S096012950600538X|issue=4}} also {{cite journal|title=Classically-Controlled Quantum Computation|author=Simon Perdrix and Philippe Jorrand|url=http://dcm-workshop.org.uk./2005/dcm-draft-proceedings.pdf|year=2006|pages=601–620|journal=Math. Struct. In Comp. Science|volume=16|doi=10.1017/S096012950600538X|issue=4|citeseerx=10.1.1.252.1823}}</ref>

==编者推荐==

类别: 图灵机

本中文词条由tueryeye翻译，[[用户:薄荷|薄荷]]编辑，如有问题，欢迎在讨论页面留言。

[[Category:待整理页面]]

[[Category:图灵机]]

[[Category:量子复杂性理论]]