在量子计算,量子有限自动机 (QFA) or 量子状态机 是 概率自动机 或 马尔可夫决策过程的量子模拟.。它们提供了现实世界 量子计算机的数学抽象。可以定义几种类型的自动机,包括一次测量和多次测量自动机。量子有限自动机也可以理解为 有限类型子位移的量子化, 或 马尔可夫链的量子化。反过来,QFA是几何有限自动机或拓扑有限自动机的特例。
自动机通过接收有限长度的 字符串来工作 信件数量 来自有限 字母表 , a并为每个这样的字符串分配一个 概率 表示自动机处于 接受状态; 的概率。也就是说,指示自动机是接受还是拒绝字符串。
QFA所接受的 语言 不是确定性有限自动机的 常规语言 , 也不是概率有限自动机的随机语言。对这些量子语言的研究仍然是一个活跃的研究领域。