1982 年，RichardFeynman 在论文“Simulating Physicswith Computers”中第一次提出了用量子力学来实现计算。之后，一些物理学家，包括来自美国Argonne National Laboratory 的Paul Benioff，从物理上也设计出了一些模型，这从能量等角度证明Richard Feynman 的设想没有问题，物理上是可以实现的。英国物理学家David Deutsch 开始思考如果这些物理学家所说的量子计算机可以实现的话，那么一定也要限定可计算的范围，也一定有一个量子版本的“Church-Turing 论题”。1985 年，David Deutsch 发表了关于“量子Turing 机”的论文。他在论文中提出的Church-Turing-Deutsch 论题，比“Church-Turing 论题”要好太多：“所有物理系统（有限的可以实现的）都可以被一台通用计算机器来模拟。”
基于量子力学理论，David Deutsch 证明了他论文中所提出的量子Tur⁃ing 机可以模拟所有物理系统，这奠定了目前利用量子计算机模拟量子系统的理论基础。David Deutsch 的量子Turing 机（Quantum Turing Machine，QTM）和Turing 的概率Turing 机（Probabilistic TM，PTM）定义非常类似，几乎可以沿用纸带模型。量子Turing 机的定义如下【56】【59】【61】。
定义6.3 量子Turing 机（QTM）是一个七元组
Q 是有限控制状态的集合；
∑⊆Γ－{b}是输入符号的集合；
Γ 是允许的磁带符号集；
δ: Q×Γ×Γ×Q×{L，R}→C 是状态转换函数，L，R 代表磁头移动方向：左L，右R；
q0∈Q 是初始状态；(www.xing528.com)
F⊆Q 是最终控制状态集；
B∈Γ 是一个空白符号。
QTM 和PTM 的最大区别就在于：
1.PTM 执行每一步后都会进行观测，从而它永远在一个确定的状态上，之前的其他信息都损失掉了，而QTM 只在最后一步进行观测，中间的可能性和信息都被包含在了最后的状态中。
2.因为概率是模平方之和为1 而不是直接相加为1，所以量子概率可以把一些可能性抵消，于是放大一些我们需要的结果。比如一个经典的例子就是进行两次哈达玛操作：如果QTM 有两个状态，∣0>和∣1>，我们可以写成向量的形式∣0>=10，∣1>=01，假设有一个哈达玛（概率）状态转移函数为12111−1，我们在状态∣0>上，那么执行这个（概率）状态转移函数两次，我们将得到一个确定的结果：
先转移到一个不确定的状态，再转移到一个确定的状态。这是使用PTM 时是难以想象的。
QTM 和非确定Turing 机（Nondeterministic TM，NTM）的区别在于：在最后的状态中，QTM 只能以一定概率取出所有可能性中的一种，而NTM 假设我们知道最后状态的所有信息。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
