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 paper, we determine the maximum probabilities achieved by QFAs for several
languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be
recognized by a QFA with probability at most 0.7726....
Research supported by Berkeley Fellowship for Graduate Studies, Microsoft Research Fellowship and NSF Grant CCR-9800024.
Research supported by Grant No.01.0354 from the Latvian Council of Science and European Commission, contract IST-1999-11234.