Exact quantum algorithms for promise problems in automata theory
Abuzer Yakaryılmaz · 2011
In this note, we show that quantum finite automata can be polynomially more succinct than their classical counterparts for promise problems in case of exact computation. Additionally, in terms of language recognition, the same result is shown to be valid up to a constant factor depending on how bigger the size of the alphabet is.