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 znaków ze skończonego zbioru i przydziela danemu ciągowi liczbę 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[1].

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ż

edytuj

Przypisy

edytuj