量子图灵机

量子图灵机( QTM ) 或通用量子计算机是一种用于模拟量子计算机效应的抽象机器。它提供了一个简单的模型，可以捕捉量子计算的所有能力——也就是说，任何量子算法都可以正式表示为特定的量子图灵机。然而，计算等效量子电路是更常见的模型。 ^{[1] [2] :2}

量子图灵机可以在基于转换矩阵的框架中与经典和概率图灵机相关联。也就是说，可以指定一个矩阵，其与表示经典或概率机器的矩阵的乘积提供了表示量子机器的量子概率矩阵。兰斯·福特诺（Lance Fortnow）展示过这一点。 ^[3]

非正式草图

理解量子图灵机 (QTM) 的一种方式是，它以量子有限自动机 (QFA) 概括确定性有限自动机(DFA) 的方式概括经典图灵机 (TM)。本质上，经典TM的内部状态被希尔伯特空间中的纯状态或混合状态所取代；转移函数被一组将希尔伯特空间映射到自身的酉矩阵所取代。 ^[4]

也就是说，经典的图灵机由 7元组描述${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$ 。请参阅图灵机的正式定义，以更深入地了解此元组中的每个元素。

对于三带量子图灵机（一个带保存输入，第二个带保存中间计算结果，第三个带保存输出）：

• 状态集${\displaystyle Q}$被希尔伯特空间所取代。
• 磁带字母符号${\displaystyle \Gamma }$同样被希尔伯特空间（通常是与状态集不同的希尔伯特空间）所取代。
• 空白符号${\displaystyle b\in \Gamma }$是希尔伯特空间的一个元素。
• 输入和输出符号${\displaystyle \Sigma }$通常被视为离散集，就像在经典系统中一样；因此，量子机的输入和输出都不需要是量子系统本身。
• 过渡函数${\displaystyle \delta :\Sigma \times Q\otimes \Gamma \to \Sigma \times Q\otimes \Gamma \times \{L,R\}}$是过渡幺半群的广义，被理解为希尔伯特空间自同构的酉矩阵的集合${\displaystyle Q}$ 。
• 初始状态${\displaystyle q_{0}\in Q}$可能是混合状态，也可能是纯状态。
• 最终或接受状态的集合${\displaystyle F}$是希尔伯特空间${\displaystyle Q}$的子空间 。

以上仅仅是量子图灵机的草图，而不是它的正式定义，因为它模糊了几个重要的细节：例如，测量的频率；例如，一次测量和多次测量 QFA 之间的区别。这个测量问题影响了输出磁带写入的定义方式。

1980 年和 1982 年，物理学家保罗·贝尼奥夫发表文章^{[5] [6]} ，首次描述了图灵机的量子力学模型。 1985 年，牛津大学物理学家戴维·多伊奇（David Deutsch）发表的一篇文章进一步发展了量子计算机的概念，他认为量子门的功能可以类似于传统数字计算二进制逻辑门。 ^[4]

Iriyama、 Ohya和 Volovich 开发了一种线性量子图灵机(LQTM) 模型。这是具有混合状态并允许不可逆转换函数的经典 QTM 的概括。这些允许表示没有经典结果的量子测量。 ^[7]

斯科特·阿伦森(Scott Aaronson) 定义了一种具有后选择功能的量子图灵机，他证明了这种机器上的多项式时间类 ( PostBQP ) 等于经典复杂度类PP 。 ^[8]

参见

• 量子模拟器§解决物理问题