量子有限自动机

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

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

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