“量子图灵机”的版本间的差异
跳到导航
跳到搜索
（阅读三遍） |
|||
| 第1行： | 第1行： | ||
| − | + | {{#seo: | |
| − | + | |keywords=量子计算机，量子算法，抽象机器 | |
| − | + | |description=是一种用来模拟量子计算机效果的抽象机器 | |
| − | + | }} | |
| − | |||
== 基础定义 == | == 基础定义 == | ||
| − | + | '''量子图灵机 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> | |
| − | |||
| − | |||
| − | |||
| − | |||
== 与经典计算的关系 == | == 与经典计算的关系 == | ||
| − | + | 通过[[过渡矩阵]]，量子图灵机可以与经典图灵机和概率图灵机相关联。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| | + | {{Unsolved|physics|通用量子计算机是否能够以高效模拟任意物理系统?}} |
| − | + | 我们可以通过类比确定有限自动机[[deterministic finite automaton]]到量子有限自动机[[quantum finite automaton]]的转化来理解经典图灵机 Turing machine (TM)到量子图灵机的转化。 他们的差异在于，经典图灵机讨论的状态被推广到了Hilbert空间中。Hilbert空间是完备的内积空间，是有限维欧几里得空间的一个推广。它不局限于实数的情形和有限的维数，但又不失完备性。在量子图灵机中转换函数被一组映射Hilbert空间到自身的酉矩阵 unitary matrix取代。<ref name="Deutsch1985" /> | |
| − | |||
经典图灵机的诞生是因为图灵想用机器来模拟用纸笔进行数学运算的过程，这样的过程可以被看作下列两种简单的动作： | 经典图灵机的诞生是因为图灵想用机器来模拟用纸笔进行数学运算的过程，这样的过程可以被看作下列两种简单的动作： | ||
| + | |||
* 在纸带上写上或删除某个符号； | * 在纸带上写上或删除某个符号； | ||
* 把笔尖从纸的一处移动到另一处； | * 把笔尖从纸的一处移动到另一处； | ||
| − | 现在我们假设有一条纸带无限长，并且被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。假设我们有一个执笔机器又称为读写头（''' | + | |
| + | 现在我们假设有一条纸带无限长，并且被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。假设我们有一个执笔机器又称为读写头（'''HEAD'''），它本身也可以具有一个状态。就像人今天可能因为某件事心情很好，也可能因为另一件事情很抑郁一样，它的状态会随着它的遭遇所改变。更重要的是执笔机器当前关注的纸上的某个位置的符号和当前的状态决定了下一步的动作。在遇到停止状态<math>F</math>之前执笔机器可以 | ||
| + | |||
* 1. 写入（替换）或擦除当前符号； | * 1. 写入（替换）或擦除当前符号； | ||
| 第35行： | 第31行： | ||
* 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空间的状态集； | ||
| 第57行： | 第39行： | ||
* <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> | + | * <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>的子集。 | ||
| − | + | 以上只是一个量子图灵机的草图，而不是它的正式定义，因为它的一些重要细节仍然定义模糊：例如，我们以什么样的频率执行对于状态的观测；什么是一次观测量子有限自动机 measure-once和多次观测量子有限自动机 measure-many QFA之间的区别。这些观测问题会影响我们如何定义写入和输出纸带的方式。 | |
| − | |||
==历史== | ==历史== | ||
| + | 物理学家 Paul Benioff 在1980 年和 1982 年发表的论文中，首次描述了图灵机的量子力学模型。<ref name=":0">{{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 name=":1">{{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>牛津大学物理学家 David Deutsch 在 1985 年撰写的一篇文章中进一步推广了量子计算机的概念，他提议量子门[[quantum gate]]应该以类似于传统数字计算二进制逻辑门的方式运行。<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、Ohya 和 Volovich 开发了线性量子图灵机 linear quantum Turing machine (LQTM) 模型。他们对具有混合状态并允许不可逆转换函数的量子图灵机进行了延伸。允许了在没有经典结果的情况下对量子的测量。<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> | ||
| − | |||
| − | + | 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> | |
| − | + | ==编者推荐== | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | ---- | |
| + | 本中文词条由tueryeye翻译，[[用户:薄荷|薄荷]]编辑，如有问题，欢迎在讨论页面留言。 | ||
| − | |||
| − | |||
| − | + | '''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。''' | |
| − | |||
| − | [[Category: | + | [[Category:图灵机]] |
| + | [[Category:量子复杂性理论]] | ||
2022年5月2日 (一) 13:13的版本
基础定义
量子图灵机 quantum Turing machine (QTM) 又称为通用量子计算机，是一种用来模拟量子计算机效果的抽象机器。尽管说提供等效计算能力的量子电路是一种更常用的模型，但是量子图灵机是一个简单但能展现出量子计算的所有威力的模型。就像经典图灵机可以模拟人类所能进行的任何计算过程一样，量子图灵机可以描述任何量子算法。[1][2]
与经典计算的关系
通过过渡矩阵，量子图灵机可以与经典图灵机和概率图灵机相关联。Lance Fortnow证明，量子图灵机的量子概率矩阵可以被拆解成是指定矩阵与经典或概率图灵机的矩阵的乘积。[3]
非正式草图定义
我们可以通过类比确定有限自动机deterministic finite automaton到量子有限自动机quantum finite automaton的转化来理解经典图灵机 Turing machine (TM)到量子图灵机的转化。 他们的差异在于，经典图灵机讨论的状态被推广到了Hilbert空间中。Hilbert空间是完备的内积空间，是有限维欧几里得空间的一个推广。它不局限于实数的情形和有限的维数，但又不失完备性。在量子图灵机中转换函数被一组映射Hilbert空间到自身的酉矩阵 unitary matrix取代。[4]
经典图灵机的诞生是因为图灵想用机器来模拟用纸笔进行数学运算的过程，这样的过程可以被看作下列两种简单的动作：
- 在纸带上写上或删除某个符号；
- 把笔尖从纸的一处移动到另一处；
现在我们假设有一条纸带无限长，并且被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。假设我们有一个执笔机器又称为读写头（HEAD），它本身也可以具有一个状态。就像人今天可能因为某件事心情很好，也可能因为另一件事情很抑郁一样，它的状态会随着它的遭遇所改变。更重要的是执笔机器当前关注的纸上的某个位置的符号和当前的状态决定了下一步的动作。在遇到停止状态[math]\displaystyle{ F }[/math]之前执笔机器可以
- 1. 写入（替换）或擦除当前符号；
- 2. 移动 HEAD， 'L'向左一步， 'R'向右一步或者'N'不移动；
- 3. 保持当前状态或者转到另一状态。
总的来说，经典图灵机可以被一个七元有序组所描述，[math]\displaystyle{ M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle }[/math]。
- [math]\displaystyle{ Q }[/math] 为被推广到了Hilbert空间的状态集；
- [math]\displaystyle{ \Gamma }[/math] 是输入字母表；
- [math]\displaystyle{ b \in \Gamma }[/math] 为空白符，也是唯一允许出现无限次的字符；
- 输入和输出符号 [math]\displaystyle{ \Sigma }[/math]通常是一个离散集。和经典图灵机的输入输出符号一样，它们不需要是一个量子系统。
- [math]\displaystyle{ \delta : \Sigma \times Q \otimes \Gamma \rightarrow \Sigma \times Q \otimes \Gamma \times \{L,R\} }[/math]是被推广到了Hilbert空间的转移函数。我们也可以理解它们为一些在Hilbert空间中自同构的酉矩阵。
- [math]\displaystyle{ q_0 \in Q }[/math]是起始状态，它可以是几种状态的混合也可以是一种状态；
- 停止状态[math]\displaystyle{ F }[/math]是[math]\displaystyle{ Q }[/math]的子集。
以上只是一个量子图灵机的草图，而不是它的正式定义，因为它的一些重要细节仍然定义模糊：例如，我们以什么样的频率执行对于状态的观测；什么是一次观测量子有限自动机 measure-once和多次观测量子有限自动机 measure-many QFA之间的区别。这些观测问题会影响我们如何定义写入和输出纸带的方式。
历史
物理学家 Paul Benioff 在1980 年和 1982 年发表的论文中，首次描述了图灵机的量子力学模型。[5][6]牛津大学物理学家 David Deutsch 在 1985 年撰写的一篇文章中进一步推广了量子计算机的概念，他提议量子门quantum gate应该以类似于传统数字计算二进制逻辑门的方式运行。[4]
Iriyama、Ohya 和 Volovich 开发了线性量子图灵机 linear quantum Turing machine (LQTM) 模型。他们对具有混合状态并允许不可逆转换函数的量子图灵机进行了延伸。允许了在没有经典结果的情况下对量子的测量。[7]
Scott Aaronson 定义了具有后选择功能的量子图灵机，他证明了这种机器上的时间复杂度类 (PostBQP) 等于经典复杂度 PP。[8]
编者推荐
本中文词条由tueryeye翻译，薄荷编辑，如有问题，欢迎在讨论页面留言。
本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。
- ↑ 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]