量子图灵机 Quantum Turing Machine, QTM

量子图灵机（Quantum Turing Machine, QTM）是经典图灵机（Turing Machine, TM）在量子计算框架下的推广，它利用量子力学原理（如叠加态、纠缠和幺正演化）扩展了计算能力。下面对量子图灵机进行解析。

1. 定义与基本结构

定义

量子图灵机由以下几个核心组件构成，

量子态空间（Hilbert Space）：
经典图灵机的配置（状态、磁带内容、读写头位置）被推广为量子态，允许叠加形式：

$|\psi\rangle = \sum_i \alpha_i |q_i, \text{tape}_i, \text{head}_i\rangle$
其中 $\alpha_i$ 为复数概率幅，满足 $\sum |\alpha_i|^2 = 1$ 。

有限状态集 $Q$ ：
包含初始状态 $q_0$ 和接受/拒绝状态（测量时坍缩到这些状态）。

字母表 $\Gamma$ ：
磁带符号（含空白符号 $\#$ ），支持量子叠加的符号写入。

量子转移函数 $\delta$ ：

$\delta: Q \times \Gamma \to \mathbb{C}^{Q \times \Gamma \times \{L, R\}}$
对每个 $(q, \gamma)$ ，输出一组可能的 $(q', \gamma', D)$ 及其概率幅，需满足幺正性（即整体演化算符 $U$ 是幺正的： $U^\dagger U = I$ 。

在量子图灵机（QTM）的转移函数定义中，符号 $\mathbb{C}^{Q \times \Gamma \times \{L, R\}}$ 的数学含义和物理意义接下来分开说明。

1.1. $\mathbb{C}$ 的含义

$\mathbb{C}$ 表示复数集合。量子计算中，概率幅（probability amplitudes）是复数，而非经典概率中的实数。
量子态的演化由复数系数（如 $\alpha + i\beta$ ）描述，其模平方 $|\alpha + i\beta|^2 = \alpha^2 + \beta^2$ 表示测量时坍缩到该状态的概率。

1.2. 转移函数的完整解释

转移函数的形式：

$\delta: Q \times \Gamma \to \mathbb{C}^{Q \times \Gamma \times \{L, R\}}$
输入：当前状态 $q \in Q$ 和读到的磁带符号 $\gamma \in \Gamma$ 。

输出：一个复数赋值的映射，覆盖所有可能的：新状态 $q' \in Q$ ，写入的符号 $\gamma' \in \Gamma$ ，读写头移动方向 $D \in \{L, R\}$ （左/右）。

需要强调的是，对每个 $(q, \gamma)$ ， $\delta$ 输出一组形如 $\delta(q, \gamma) = \sum_{(q', \gamma', D)} c_{q', \gamma', D} \cdot (q', \gamma', D)$

其中 $c_{q', \gamma', D} \in \mathbb{C}$ 是转移到配置 $(q', \gamma', D)$ 的概率幅。

1.3. 为什么需要复数 $\mathbb{C}$

量子叠加与干涉

复数相位（如 $e^{i\theta}$ ）允许量子态之间发生相长/相消干涉，这是量子并行性的核心（例如Deutsch-Jozsa算法中的相位反转）。经典概率（实数）无法描述干涉现象。

幺正性（Unitarity）

量子演化必须保持概率守恒（即幺正性 $U^\dagger U = I$ ），复数系数是满足此性质的数学必需。

例如，Hadamard门的变换矩阵包含 $\pm \frac{1}{\sqrt{2}}$ ，其平方和为1。

1.4. 量子图灵机跳转示例

量子图灵机的状态转移由量子叠加和幺正演化决定，相比经典图灵机，它可以同时处理多个计算路径。以下是几个具体示例，从简单到复杂

1.4.1. 简单示例：单步确定性转移

问题：设计一个量子图灵机，初始状态为 $|q_0\rangle$ ，读取符号 0 时转移到 $|q_1\rangle$ ，读取 1 时转移到 $|q_2\rangle$ 。

定义：

状态集 $Q = \{ |q_0\rangle, |q_1\rangle, |q_2\rangle \}$

纸带字母 $\Sigma = \{0, 1\}$

初始头位置在 0。

转移规则：

$\delta(|q_0\rangle, 0) = |q_1\rangle, \quad \delta(|q_0\rangle, 1) = |q_2\rangle$

（这里假设转移是确定性的，即没有叠加态。）

运行示例：

输入纸带：0
初始状态： $|q_0\rangle$
读取 0 → 转移到 $|q_1\rangle$
最终状态： $|q_1\rangle$

输入纸带：1
初始状态： $|q_0\rangle$
读取 1 → 转移到 $|q_2\rangle$
最终状态： $|q_2\rangle$

特点：
这个例子和经典图灵机完全一致，没有量子特性。真正的量子图灵机需要叠加态和干涉。

1.4.2. 简单量子叠加态转移

问题：设计一个量子图灵机，初始状态为 $|q_0\rangle$ ，读取 0 时进入叠加态 $\frac{1}{\sqrt{2}}(|q_1\rangle + |q_2\rangle)$ ，读取 1 时进入 $|q_2\rangle$ 。

定义：

状态集 $Q = \{ |q_0\rangle, |q_1\rangle, |q_2\rangle \}$ 。

转移规则：

$\delta(|q_0\rangle, 0) = \frac{1}{\sqrt{2}} |q_1\rangle + \frac{1}{\sqrt{2}} |q_2\rangle\\ \\ \delta(|q_0\rangle, 1) = |q_2\rangle$

运行示例：

输入纸带：0
初始状态： $|q_0\rangle$
读取 0 → 进入叠加态 $\frac{1}{\sqrt{2}}(|q_1\rangle + |q_2\rangle)$
最终状态： $\frac{1}{\sqrt{2}} |q_1\rangle + \frac{1}{\sqrt{2}} |q_2\rangle$

输入纸带：1
初始状态： $|q_0\rangle$
读取 1 → 进入 $|q_2\rangle$
最终状态： $|q_2\rangle$

特点：
这里首次引入量子叠加态，使得机器可以同时进入两个状态 $|q_1\rangle$ 和 $|q_2\rangle$ ，概率各 50%。

1.4.3. 多步量子计算（Deutsch-Jozsa 问题）

问题：判断一个函数 $f: \{0,1\} \rightarrow \{0,1\}$ 是恒定（constant）还是平衡（balanced）。
（恒定： $f(0)=f(1)$ ，平衡： $f(0) \neq f(1)$ ）

量子图灵机实现：

初始状态： $|q_0\rangle |0\rangle$ （初始状态 + 纸带 0）。
第一步（叠加态构造）：
- 应用 Hadamard 门（量子并行性）：
  $|q_0\rangle |0\rangle \rightarrow \frac{1}{\sqrt{2}}(|q_0\rangle |0\rangle + |q_0\rangle |1\rangle)$
第二步（查询函数 ff）：
- 量子预言机（Oracle）计算 $|x\rangle \rightarrow (-1)^{f(x)} |x\rangle$ ：
  - 如果 $f$ 恒定，相位不变
  - 如果 $f$ 平衡， $|0\rangle$ 和 $|1\rangle$ 相位相反
第三步（干涉测量）：
- 再次应用 Hadamard 门：
  - 若 $f$ 恒定，测量结果为 $|0\rangle$
  - 若 $f$ 平衡，测量结果为 $|1\rangle$

特点：

经典计算需要 2 次查询，量子计算仅需 1 次（量子加速）。

量子图灵机通过叠加态 + 干涉实现高效计算。

1.4.4. 复杂示例：Shor 算法的量子部分（因数分解）

问题：找到一个大数 $N$ 的非平凡因数。

量子图灵机步骤：

初始状态： $|q_0\rangle |0\cdots0\rangle$ （所有量子比特置零）。
第一步（叠加态构造）：
- 应用 Hadamard 门生成所有可能的 $x$ ：
  $|q_0\rangle |0\rangle \rightarrow \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |q_0\rangle |x\rangle$
第二步（模幂计算）：
- 计算 $f(x) = a^x \mod N$ （ $a$ 是随机选择的数）：
  $\sum_x |x\rangle |0\rangle \rightarrow \sum_x |x\rangle |f(x)\rangle$
第三步（量子傅里叶变换 QFT）：
- 对 $|x\rangle$ 进行 QFT，提取周期 $r$ （使得 $a^r \equiv 1 \mod N$ ）
测量与经典后处理：
- 测量得到 $r$ ，再用经典算法求 $\gcd(a^{r/2} \pm 1, N)$

特点：

经典算法需要指数时间，量子算法仅需多项式时间;

量子图灵机通过并行计算 + 干涉高效提取周期。

1.5. 与经典图灵机的对比

经典确定性TM：
$\delta$ 输出唯一的下一个配置（如 $(q', \gamma', D)$ ），无复数系数。

经典概率TM：
输出是概率分布（实数且非负，如 $p(q', \gamma', D) \in [0,1]$ ），但无复数相位。

量子TM：
复数概率幅允许干涉和纠缠，这是量子加速（如Shor算法）的根源。

1.6. 数学验证：幺正性条件

为确保量子演化的合法性， $\delta$ 必须满足：

$\sum_{q', \gamma', D} |\delta(q, \gamma, q', \gamma', D)|^2 = 1 \quad \forall (q, \gamma)$ .
即每个输入的转移概率幅模平方和为1（类比经典概率的归一化）。

1.7 分析总结

$\mathbb{C}^{Q \times \Gamma \times \{L, R\}}$ 表示，量子图灵机的每一步演化由复数概率幅控制，支持叠加态和干涉。复数 $\mathbb{C}$ 是量子计算超越经典计算的关键数学结构，使得量子并行性和相位操作成为可能。这一形式化定义是量子计算理论的基础，与物理实现（如量子门操作）直接对应。

2. 核心性质

2.1. 量子并行性

QTM 可同时处理多个计算路径（叠加态），例如：
输入 $n$ 比特时，QTM 可同时计算 $2^n$ 个状态（指数级并行性）。

2.2. 幺正演化

每一步操作必须保持概率守恒，即转移矩阵 $U$ 是幺正矩阵。

经典TM的不可逆操作（如删除信息）在QTM中需通过辅助比特实现可逆性。【注，从非相对论独立量子系统的角度，没有什么是会消失的】

2.3. 测量与概率输出

计算结束时，对量子态进行测量，得到接受/拒绝结果的概率由 $| \alpha_{\text{accept}} |^2$ 和 $| \alpha_{\text{reject}} |^2$ 决定。

输出是概率性的（类似BQP复杂度类）。

2.4. 与经典TM的关系

经典TM是QTM的特例：当所有概率幅为0或1时，QTM退化为确定性TM。

严格更强未确定：目前已知QTM可高效解决某些经典难解问题（如Shor算法），但尚未证明 $BQP \neq P$ 。

3. 示例：Deutsch-Jozsa问题的QTM实现

问题：

判断函数 $f: \{0,1\}^n \to \{0,1\}$ 是常函数（全0或全1）还是平衡函数（一半0、一半1）。
QTM步骤：

初始化磁带为 $|{0^n} \rangle |{1}\rangle$ ，应用 Hadamard 门生成叠加态：

$\frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |{x}\rangle |{-}\rangle$

通过量子转移函数 $\delta$ 实现 Oracle 查询（相位反转）：

$|{x}\rangle |{-}\rangle \to (-1)^{f(x)} |{x}\rangle |{-}\rangle$

再次应用 Hadamard 门并测量：若结果为 $|{0^n}\rangle$ ，则 $f$ 为常函数；否则为平衡函数。
优势：QTM仅需1次查询，经典TM最坏需 $2^{n-1}+1$ 次。

4. 与量子线路模型的等价性

量子图灵机（QTM）与量子线路模型（Quantum Circuit Model）在计算能力上是等价的：

QTM → 量子线路：QTM的每一步幺正操作可分解为量子门序列

量子线路 → QTM：量子线路可通过QTM模拟，磁带存储量子门操作的历史

但量子线路更实用，因其直接对应现代量子计算机的物理实现（如超导量子比特）。

5. 复杂度与开放问题

复杂度类
BQP（Bounded-Error Quantum Polynomial Time）：
QTM在多项式时间内以高概率（≥2/3）解决的问题类（如整数分解、离散对数）。

已知关系： $\text{P} \subseteq \text{BQP} \subseteq \text{PSPACE}$ 。

未解决问题： $\text{BQP} \subsetneq \text{NP}$ 是否成立？

开放问题
量子优势的极限：是否存在 BQP-complete 问题（类似NP-complete）？

物理实现：如何构建可扩展、容错的QTM硬件？

与经典计算的关系：是否所有P问题都可被QTM高效解决（即 P = BQP）？

6. 量子图灵机小结

量子图灵机是理论模型，结合了图灵机的框架与量子叠加/纠缠特性。

优势：潜在指数级加速（如Shor算法）、并行性、解决经典难解问题。

挑战：物理实现困难（退相干、纠错）、数学基础未完全明确（如BQP与NP的关系）。

意义：为理解量子计算的极限提供了理论基础，推动算法设计（如Grover搜索、HHL线性方程求解）。

量子图灵机不仅是抽象工具，更是探索“计算本质”的桥梁——它揭示了一个可能性：在某些问题上，宇宙允许我们比经典计算机走得更快，但可能依然不是最快的可能方式。

7.附录：量子力学和量子计算的酉正变换

从非相对论独立量子系统的角度出发，量子演化遵循幺正性（unitarity），这意味着信息不会消失，量子态始终以确定性的方式演化。这一观点与经典物理中的信息守恒和量子力学的基本原理密切相关。

7.1. 幺正演化的核心思想

在量子力学中，一个封闭（孤立）量子系统的演化由幺正算符 $U$ 描述：

$|\psi(t)\rangle = U(t) |\psi(0)\rangle$
其中 $U$ 满足 $U^\dagger U = I$ ，即：可逆性：任何量子操作均可通过 $U^\dagger$ 逆转。

信息守恒：量子态的内积（即概率幅）在演化中保持不变。

推论：量子信息不会被销毁，只会被转移或重新编码。

7.2. 量子图灵机中的幺正性

量子图灵机（QTM）的转移函数 $\delta$ 必须生成幺正演化，每个配置的转移概率幅需满足归一化条件：

$\sum_{q', \gamma', D} |\delta(q, \gamma, q', \gamma', D)|^2 = 1$

（全局确定性）即使单个路径的概率幅可能干涉相消，但所有可能的演化路径总概率保持守恒。

示例：
若QTM在某步将状态 $|q\rangle$ 分裂为 $\alpha|q_1\rangle + \beta|q_2\rangle$ ，则未来可通过逆操作重新组合为原状态（假设无测量）。

7.3. "没有什么是会消失"的物理表现

（1）量子态的非定域性
量子信息可能分散到多个自由度（如纠缠态），但绝不会完全消失。
例如：一个量子比特 $\alpha|0\rangle + \beta|1\rangle$ 被编码到多个辅助比特中，信息仍存在于联合系统中。

（2）量子纠错与相干性
即使环境导致退相干（decoherence），信息实际上转移到了环境自由度中（整体系统仍幺正演化）。
量子纠错码通过主动修复，将"丢失"的信息从环境中重新提取。

（3）No-Cloning定理的互补性
量子不可克隆定理（No-Cloning）禁止完美复制未知量子态，但同时也意味着量子信息不能被完全擦除（否则可逆性被破坏）。

7.4. 与经典计算的对比

性质	经典图灵机	量子图灵机
信息处理	可擦除信息（如覆盖磁带符号）	信息必须守恒（幺正演化）
操作	允许不可逆操作（如AND门）	所有操作必须可逆（如Toffoli门）
"消失"的含义	信息可被删除（热力学熵增）	信息仅被隐藏或分散（整体系统保持幺正）