更改

}}

}}

== 基础定义 ==

== 基础定义 ==

'''量子图灵机 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 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|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>

通过[[过渡矩阵]]，量子图灵机可以与经典图灵机和概率图灵机相关联。Lance Fortnow证明，量子图灵机的量子概率矩阵可以被拆解成是指定矩阵与经典或概率图灵机的矩阵的乘积。<ref name="transition">{{cite journal|author=Fortnow|first=Lance|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>

==历史==

==历史==

物理学家 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>

物理学家 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|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>