Kwantowy automat skończony

Kwantowy automat skończony (ang. Quantum Finite Automata, QFA) – abstrakcyjna maszyna o skończonej liczbie stanów, która – zaczynając w stanie początkowym – czyta kolejne symbole pewnego ciągu $\sigma =(\sigma _{0},\sigma _{1},\dots ,\sigma _{k})$ znaków $\sigma _{i}$ ze skończonego zbioru $\Sigma$ i przydziela danemu ciągowi liczbę $\operatorname {Pr} (\sigma )$ określającą prawdopodobieństwo znajdowania się maszyny w stanie akceptującym (końcowym). Czyli wskazuje na to, czy dany ciąg znaków należy do języka regularnego, do rozpoznawania którego jest zbudowana.

Kwantowe automaty skończone są kwantowym analogiem automatów probabilistycznych bądź Łańcuchów Markowa i są związane z komputerami kwantowymi podobnie jak automaty skończone z maszynami Turinga.

Zobacz też

• kwantowa maszyna Turinga
• automat skończony