Probabilities to accept languages by quantum finite automata

Andris Ambainis, Richard Bonner, Rusins Freivalds +1

We construct a hierarchy of regular languages such that the current language in the hierarchy can be accepted by 1-way quantum finite automata with a probability smaller than the c…