“量子图灵机”的版本间的差异
跳到导航
跳到搜索
（Moved page from wikipedia:en:Quantum Turing machine (history)） |
小 （Moved page from wikipedia:en:Quantum Turing machine (history)） |
||
| 第1行： | 第1行： | ||
| − | + | 此词条暂由彩云小译翻译，翻译字数共303，未经人工整理和审校，带来阅读不便，请见谅。 | |
{{Short description|Model of quantum computation}} | {{Short description|Model of quantum computation}} | ||
| 第9行： | 第9行： | ||
<!-- Basic definition --> | <!-- Basic definition --> | ||
| − | ! -- 基本定义 -- | + | < ! -- 基本定义 -- > |
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>{{rp|2}} | 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>{{rp|2}} | ||
| 第15行： | 第15行： | ||
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. | 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) | + | 量子图灵机计算机(QTM)或者说通用量子计算机是一种用来模拟量子计算机效果的抽象机器。它提供了一个简单的模型，可以捕捉到量子计算的所有威力---- 也就是说，任何量子算法都可以形式化地表示为一个特定的量子图灵机。然而，计算等效量子电路是一种比较常用的模型。 |
| 第21行： | 第21行： | ||
<!-- Relation to classical computation --> | <!-- Relation to classical computation --> | ||
| − | + | That is, a classical Turing machine is described by a 7-tuple <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math>. | |
| − | + | 也就是说，一个经典的图灵机是由一个7元组来描述的。 | |
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> | 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> | ||
| − | |||
| − | |||
| + | 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): | ||
| + | 对于三带量子图灵机(一带保存输入，第二带保存中间计算结果，第三带保存输出) : | ||
== Informal sketch == | == Informal sketch == | ||
| 第38行： | 第38行： | ||
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" /> | 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" /> | ||
| − | |||
| − | |||
| − | |||
| − | |||
That is, a classical Turing machine is described by a 7-[[tuple]] <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math>. | That is, a classical Turing machine is described by a 7-[[tuple]] <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math>. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| 第55行： | 第47行： | ||
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): | 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 <math>Q</math> is replaced by a [[Hilbert space]]. | |
| − | + | * The tape alphabet symbols <math>\Gamma</math> are likewise replaced by a Hilbert space (usually a different Hilbert space than the set of states). | |
| − | + | 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. | |
| − | + | 以上只是一个量子图灵机的概述，而不是它的正式定义，因为它留下了一些模糊的重要细节: 例如，多久进行一次测量; 例如，区别一次测量和多次测量 QFA。这个度量问题影响定义写入输出磁带的方式。 | |
* The blank symbol <math>b \in \Gamma</math> corresponds to the zero-vector. | * The blank symbol <math>b \in \Gamma</math> corresponds to the zero-vector. | ||
| 第68行： | 第60行： | ||
* The [[State transition system|transition function]] <math>\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 matrix|unitary matrices]] that are [[automorphism]]s of the Hilbert space <math>Q</math>. | * The [[State transition system|transition function]] <math>\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 matrix|unitary matrices]] that are [[automorphism]]s of the Hilbert space <math>Q</math>. | ||
| + | |||
| + | 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. | ||
| + | |||
| + | 1980年和1982年，物理学家保罗 · 贝尼奥夫发表论文，首次描述了图灵机的量子力学模型。牛津大学物理学家大卫 · 多伊奇在1985年的一篇文章中进一步发展了量子计算机的概念，他提出量子门可以以类似于传统数字计算二进制逻辑门的方式运行。 | ||
* The initial state <math>q_0 \in Q</math> may be either a [[mixed quantum state|mixed state]] or a [[pure state]]. | * The initial state <math>q_0 \in Q</math> may be either a [[mixed quantum state|mixed state]] or a [[pure state]]. | ||
* The set <math>F</math> of ''final'' or ''accepting states'' is a subspace of the Hilbert space <math>Q</math>. | * The set <math>F</math> of ''final'' or ''accepting states'' is a subspace of the Hilbert space <math>Q</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 的推广。这使得量子测量可以在没有经典结果的情况下进行表示。 | ||
| 第77行： | 第77行： | ||
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. | 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. | ||
| − | + | 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。 | |
| 第86行： | 第86行： | ||
In 1980 and 1982, physicist [[Paul Benioff]] published papers<ref>{{cite journal |last1=Benioff | first1=Paul | title=The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines | journal=Journal of Statistical Physics |volume=22 | issue=5 | pages=563–591 | year=1980 | doi=10.1007/bf01011339|bibcode=1980JSP....22..563B }}</ref><ref>{{Cite journal | doi=10.1007/BF01342185 | last1=Benioff | first1=P. | title=Quantum mechanical hamiltonian models of turing machines | journal=Journal of Statistical Physics | volume=29 | issue=3 | pages=515–546 | year=1982|bibcode=1982JSP....29..515B }}</ref> 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 gate]]s could function in a similar fashion to traditional digital computing [[Binary numeral system|binary]] [[logic gates]].<ref name="Deutsch1985">{{cite journal|last=Deutsch|first=David|author-link=David Deutsch|date=July 1985|title=Quantum theory, the Church-Turing principle and the universal quantum computer|url=http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf|url-status=dead|journal=[[Proceedings of the Royal Society A]]|volume=400|issue=1818|pages=97–117|bibcode=1985RSPSA.400...97D|doi=10.1098/rspa.1985.0070|archiveurl=https://web.archive.org/web/20081123183419/http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf|archivedate=2008-11-23|citeseerx=10.1.1.41.2382}}</ref> | In 1980 and 1982, physicist [[Paul Benioff]] published papers<ref>{{cite journal |last1=Benioff | first1=Paul | title=The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines | journal=Journal of Statistical Physics |volume=22 | issue=5 | pages=563–591 | year=1980 | doi=10.1007/bf01011339|bibcode=1980JSP....22..563B }}</ref><ref>{{Cite journal | doi=10.1007/BF01342185 | last1=Benioff | first1=P. | title=Quantum mechanical hamiltonian models of turing machines | journal=Journal of Statistical Physics | volume=29 | issue=3 | pages=515–546 | year=1982|bibcode=1982JSP....29..515B }}</ref> 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 gate]]s could function in a similar fashion to traditional digital computing [[Binary numeral system|binary]] [[logic gates]].<ref name="Deutsch1985">{{cite journal|last=Deutsch|first=David|author-link=David Deutsch|date=July 1985|title=Quantum theory, the Church-Turing principle and the universal quantum computer|url=http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf|url-status=dead|journal=[[Proceedings of the Royal Society A]]|volume=400|issue=1818|pages=97–117|bibcode=1985RSPSA.400...97D|doi=10.1098/rspa.1985.0070|archiveurl=https://web.archive.org/web/20081123183419/http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf|archivedate=2008-11-23|citeseerx=10.1.1.41.2382}}</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>{{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> | 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>{{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> | ||
| − | |||
| − | |||
| − | |||
| − | |||
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 (complexity)|PP]].<ref>{{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> | 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 (complexity)|PP]].<ref>{{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> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| 第128行： | 第116行： | ||
* {{cite journal |jstor=2397601|title=Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer|journal=Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences|volume=400|issue=1818|pages=97–117|last1=Deutsch|first1=D.|year=1985|bibcode=1985RSPSA.400...97D|doi=10.1098/rspa.1985.0070|citeseerx=10.1.1.41.2382}} | * {{cite journal |jstor=2397601|title=Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer|journal=Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences|volume=400|issue=1818|pages=97–117|last1=Deutsch|first1=D.|year=1985|bibcode=1985RSPSA.400...97D|doi=10.1098/rspa.1985.0070|citeseerx=10.1.1.41.2382}} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Category:Turing machine | Category:Turing machine | ||
| 第147行： | 第121行： | ||
类别: 图灵机 | 类别: 图灵机 | ||
| − | + | ||
Category:Quantum complexity theory | Category:Quantum complexity theory | ||
2020年10月25日 (日) 21:19的版本
此词条暂由彩云小译翻译，翻译字数共303，未经人工整理和审校，带来阅读不便，请见谅。
< ! -- 基本定义 -- >
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.[1][2]:2
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)或者说通用量子计算机是一种用来模拟量子计算机效果的抽象机器。它提供了一个简单的模型，可以捕捉到量子计算的所有威力---- 也就是说，任何量子算法都可以形式化地表示为一个特定的量子图灵机。然而，计算等效量子电路是一种比较常用的模型。
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].
也就是说，一个经典的图灵机是由一个7元组来描述的。
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.[3]
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):
对于三带量子图灵机(一带保存输入，第二带保存中间计算结果，第三带保存输出) :
Informal sketch
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.[4]
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].
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 [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 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.
以上只是一个量子图灵机的概述，而不是它的正式定义，因为它留下了一些模糊的重要细节: 例如，多久进行一次测量; 例如，区别一次测量和多次测量 QFA。这个度量问题影响定义写入输出磁带的方式。
- 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].
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.
1980年和1982年，物理学家保罗 · 贝尼奥夫发表论文，首次描述了图灵机的量子力学模型。牛津大学物理学家大卫 · 多伊奇在1985年的一篇文章中进一步发展了量子计算机的概念，他提出量子门可以以类似于传统数字计算二进制逻辑门的方式运行。
- 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].
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 的推广。这使得量子测量可以在没有经典结果的情况下进行表示。
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.
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。
History
In 1980 and 1982, physicist Paul Benioff published papers[5][6] 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.[4]
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.[7]
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.[8]
See also
References
- ↑ Andrew Yao (1993). Quantum circuit complexity. 34th Annual Symposium on Foundations of Computer Science. pp. 352–361.
- ↑ Abel Molina; John Watrous (2018). "Revisiting the simulation of quantum Turing machines by quantum circuits". arXiv:1808.01701 [cs.CC].
- ↑ Fortnow, Lance (2003). "One Complexity Theorist's View of Quantum Computing". Theoretical Computer Science. 292 (3): 597–610. arXiv:quant-ph/0003035. doi:10.1016/S0304-3975(01)00377-2.
- ↑ 4.0 4.1 Deutsch, David (July 1985). "Quantum theory, the Church-Turing principle and the universal quantum computer" (PDF). Proceedings of the Royal Society A. 400 (1818): 97–117. Bibcode:1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382. doi:10.1098/rspa.1985.0070. Archived from the original (PDF) on 2008-11-23.
- ↑ Benioff, Paul (1980). "The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines". Journal of Statistical Physics. 22 (5): 563–591. Bibcode:1980JSP....22..563B. doi:10.1007/bf01011339.
- ↑ Benioff, P. (1982). "Quantum mechanical hamiltonian models of turing machines". Journal of Statistical Physics. 29 (3): 515–546. Bibcode:1982JSP....29..515B. doi:10.1007/BF01342185.
- ↑ Simon Perdrix; Philippe Jorrand (2007-04-04). "Classically-Controlled Quantum Computation". Math. Struct. In Comp. Science. 16 (4): 601–620. arXiv:quant-ph/0407008. doi:10.1017/S096012950600538X. also Simon Perdrix and Philippe Jorrand (2006). "Classically-Controlled Quantum Computation" (PDF). Math. Struct. In Comp. Science. 16 (4): 601–620. CiteSeerX 10.1.1.252.1823. doi:10.1017/S096012950600538X.
- ↑ Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 (2063): 3473–3482. arXiv:quant-ph/0412187. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005.1546. Preprint available at [1]
Further reading
- Molina, Abel; Watrous, John (2018). "Revisiting the simulation of quantum Turing machines by quantum circuits". arXiv:1808.01701 [cs.CC].
- Iriyama, Satoshi; Ohya, Masanori; Volovich, Igor (2004). "Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm". arXiv:quant-ph/0405191.
- Deutsch, D. (1985). "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer". Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. 400 (1818): 97–117. Bibcode:1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382. doi:10.1098/rspa.1985.0070. JSTOR 2397601.
Category:Turing machine
类别: 图灵机
Category:Quantum complexity theory
范畴: 量子复杂性理论
This page was moved from wikipedia:en:Quantum Turing machine. Its edit history can be viewed at 量子图灵机/edithistory