Improved constructions of quantum automata

We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of logp than the previously known construction.Our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.