  We present a simple construction of quantum automata which achieve an
exponential advantage over classical finite automata. Our automata use
\frac{4}{\epsilon} \log 2p + O(1) 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 \log p than the previously known
construction of Ambainis and Freivalds (quant-ph/9802062).
  Similarly to Ambainis and Freivalds, our construction is by a probabilistic
argument. We consider the possibility to derandomize it and present some
results in this direction.
