量子有限自動機

在量子计算，量子有限自动机 (QFA) or 量子状态机 是 概率自动机 或 马尔可夫决策过程的量子模拟.。它们提供了现实世界 量子计算机的数学抽象。可以定义几种类型的自动机，包括一次测量和多次测量自动机。量子有限自动机也可以理解为 有限类型子位移的量子化, 或 马尔可夫链的量子化。反过来，QFA是几何有限自动机或拓扑有限自动机的特例。

自动机通过接收有限长度的 字符串来工作 \sigma=(\sigma_0,\sigma_1,\cdots,\sigma_k) 信件数量 \sigma_i 来自有限 字母表 \Sigma, a并为每个这样的字符串分配一个 概率 \operatorname{Pr}(\sigma) 表示自动机处于 接受状态; 的概率。也就是说，指示自动机是接受还是拒绝字符串。

QFA所接受的语言不是确定性有限自动机的常规语言，也不是概率有限自动机的随机语言。对这些量子语言的研究仍然是一个活跃的研究领域。