58
个编辑
更改
跳到导航
跳到搜索
第7行：
第7行： − + + − − − − 第23行：
第20行： − 在基于转移矩阵的框架下，量子图灵机可以与经典图灵机和概率图灵机相关联。也就是说，可以指定一个矩阵，该矩阵与表示经典或概率机器的矩阵的乘积提供了表示量子机器的量子概率矩阵。这是由兰斯 · 福特诺展示的。<ref name="transition" />+ − − − − − == Informal sketch == +
无编辑摘要
<!-- 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>
量子图灵机计算机(QTM)又称为通用量子计算机是一种用来模拟量子计算机效果的抽象机器。它提供了一个简单的模型，但又能展现出量子计算的所有威力。也就是说，任何量子算法都可以被形式化地表示为一个特定的量子图灵机。提供等效计算能力的量子电路是一种比较常用的模型。<ref name="equivalence" /><ref name="newequivalence" />
量子图灵机计算机(QTM)又称为通用量子计算机是一种用来模拟量子计算机效果的抽象机器。它提供了一个简单的模型，但又能展现出量子计算的所有威力。也就是说，任何量子算法都可以被形式化地表示为一个特定的量子图灵机。提供等效计算能力的量子电路是一种比较常用的模型。<ref name="equivalence" /><ref name="newequivalence" />
<!-- Relation to classical computation -->
<!-- Relation to classical computation -->
=== 与经典计算的关系 ===
=== 与经典计算的关系 ===
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）证明，指定一个矩阵，其与经典或概率图灵机的矩阵的乘积提供了量子机器的量子概率矩阵。<ref name="transition" />
=== 通俗定义 ===
{{Unsolved|physics|Is a [[universal quantum computer]] sufficient to [[Algorithmic efficiency|efficiently]] [[Dynamical simulation|simulate]] an arbitrary physical system?}}
{{Unsolved|physics|Is a [[universal quantum computer]] sufficient to [[Algorithmic efficiency|efficiently]] [[Dynamical simulation|simulate]] an arbitrary physical system?}}