Exact results for accepting probabilities of quantum automata

Andris Ambainis, Arnolds Kikusts

One of the properties of Kondacs-Watrous model of quantum finite automata (QFA) is that the probability of the correct answer for a QFA cannot be amplified arbitrarily. In this pap…