量子有限自动机

在量子計算，量子有限自動機 (QFA) or 量子狀態機 是 概率自動機 或 馬爾可夫決策過程的量子模擬.。它們提供了現實世界 量子計算機的數學抽象。可以定義幾種類型的自動機，包括一次測量和多次測量自動機。量子有限自動機也可以理解為 有限類型子位移的量子化, 或 馬爾可夫鏈的量子化。反過來，QFA是幾何有限自動機或拓撲有限自動機的特例。

自動機通過接收有限長度的 字符串來工作 $\sigma =(\sigma _{0},\sigma _{1},\cdots ,\sigma _{k})$ 信件數量 $\sigma _{i}$ 來自有限 字母表 $\Sigma$, a並為每個這樣的字符串分配一個 概率 $\operatorname {Pr} (\sigma )$ 表示自動機處於 接受狀態; 的概率。也就是說，指示自動機是接受還是拒絕字符串。

QFA所接受的 語言 不是確定性有限自動機的 常規語言 , 也不是概率有限自動機的隨機語言。對這些量子語言的研究仍然是一個活躍的研究領域。