量子图灵机

简介

**量子图灵机**是量子计算的理论模型，是经典图灵机的量子推广。

模型定义

量子图灵机包含： 1. 无限长的量子带 2. 有限状态控制器 3. 读写头

与量子电路的关系

等价性

量子图灵机与量子电路模型在计算能力上等价

量子丘奇-图灵论题

任何物理上可实现的计算过程都可以被量子图灵机有效模拟

---

上一章: 量子电路模型 | 下一层: 算法与复杂性 (L3)